标签: b-tree

b树和b +树只能在他们的叶子上存储数据吗？我假设他们使用内部节点来搜索所需的数据.

是这种情况还是他们在每个节点中存储数据？

我正在观看有关 B+ 树基础知识的视频，他提到 B+ 树叶子存储在磁盘上，除了root存储在main memory. 我的教授在课堂上提到索引存储在 中main memory，并且leaves包含指向磁盘的数据指针。

见下图：

我的问题是所有索引到底存储在哪里？

• 我们是否只将根存储在主内存中？
• 所有索引都存储在主存中？

我已经浏览了几个链接，但没有人明确提到这部分？谁能澄清我的问题。谢谢

我想在磁盘文件中保存一个Btree(不确定二进制文件).然后将其读入内存.某些Level-order遍历可能是二进制Btree的好方法.但如果它不是二元的那个.我将叶子节点中的Btree构建到内存中的rootnode.我相信我必须在磁盘文件中定义一些结构并输出树节点.使用一些额外的标签来识别文件中的节点？如何遍历可能是这里的关键问题.我不知道保存节点和指针的好方法.然后阅读它.在记忆中构建树.有什么好主意吗？非常感谢.

如果我有一个包含数据的表列并在此列上创建索引,索引是否会占用与列本身相同的磁盘空间量？

我很感兴趣,因为我试图理解b-tree是否真的保留了叶子节点中列数据的副本,或者它们以某种方式指向它？

对不起,如果这是"Java会取代XML吗？" 善意的问题.

更新:

使用单个GUID列创建了一个没有索引的表,添加了1M行--26MB

与主键相同的表(聚簇索引) - 25MB(甚至更少!),索引大小 - 176KB

具有唯一键的相同表(非聚集索引) - 26MB,索引大小 - 27MB

因此,只有非聚簇索引占用的空间与数据本身一样多.

所有测量都在SQL Server 2005中完成

如何在innodb中物理表示非叶子 b树节点？

回想一下,b树(更具体地说是b +树)具有叶节点和非叶节点.在b +树中,所有叶节点都位于非叶子或"内部"节点的树下面,并指向实际包含行数据的页面.

我知道非叶节点存储在非叶节点段中,并使用类似数据页的页面.我已经找到了关于如何物理存储数据页面的大量文档,但是我无法找到关于非叶索引页面的内容.

什么是B*树？他们只是意味着二元搜索树吗？

我的C++指针存在问题,如果有人能够与我分享他们的专业知识,那就太棒了!

我得到的输出是:

1:
2:
END: C
1:C
2:E
END: E

我期待的输出是:

1:
2:
END: C
1:C
2:C
END: E

相关代码是这样的:

我的test.cpp

tree.insert('C');
tree.insert('E');

插入功能:

template <typename T> pair<typename btree<T>::iterator, bool> btree<T>::insert(const T& elem) {
  cout <<  "1:" << this->rbegin_->value() << endl;
  btree_node<T> node(elem);
  cout <<  "2:" << this->rbegin_->value() << endl;
  rbegin_ = &node;
  iterator itr;
  pair<typename btree<T>::iterator, bool> p(itr, false);
  cout << "END: " << this->rbegin_->value() << endl;
  return p;
}

btree_node的构造函数(基本上是空的):

template <typename T> btree_node<T>::btree_node(const T& elem) : value_(elem), …

由于数据库数据在B树中以8k页组织,并且对于PK信息信息同样如此,因此数据库中的每个表应该可以计算B树的高度.从而揭示了达到某些数据所需的跳跃次数.

由于行大小和PK大小都非常重要,因此很难计算,因为例如 varchar(250)不需要占用250个字节.

1)有没有办法从SQL Server中获取信息？2)如果没有,是否可以使用分析数据库表的一些代码进行粗略估计？

我正在尝试根据Lehman 和 Yao 在本文中建议的数据结构（B^链接树）和算法来实现数据库索引。在第 2 页，作者指出：

磁盘分区为固定大小的部分（物理页；在本文中，这些对应于树的节点）。这些是进程可以读取或写入的唯一单元。[强调我的](...)

(...) 允许进程锁定和解锁磁盘页面。这个锁赋予该进程对该页面的独占修改权；此外，进程必须锁定页面才能修改该页面。(...)锁 不会阻止其他进程读取锁定的页面。[强调我的]

我不完全确定我的解释是正确的（我不习惯阅读学术论文），但我认为可以从强调的句子中得出结论，作者的意思是读取和写入页面的操作被假定为“原子” ，从某种意义上说，如果进程 A 已经开始读取（相应地写入）页面，则另一个进程 B 可能不会开始写入（相应地读取）同一页面，直到 A 完成其读取（相应地写入）操作. 多个进程同时读取同一个页面当然是一个合法的条件，因为多个进程同时在不同的页面上执行任意操作（页面 P 上的进程 A，页面 Q 上的进程 B，页面 R 上的进程 C，等等。 ）。

1. 我的解释正确吗？

2. 我可以假设 POSIX'read()和write()系统调用在上述意义上是“原子的”吗？我是否可以依靠这些具有一些内部逻辑的系统调用来根据文件描述符的位置和要读取或写入的块的指定大小来确定是否应该暂时阻止特定read()或write()调用？

3. 如果上述问题的答案是“否”，我应该如何推出自己的锁定机制？

我在Golang中遇到问题,我需要能够查找大约5,000,000个字符串的字符串键,每个字符串只包含az(小写)和0-9个字符.与uint32和uint64类似的问题作为键.

地图(哈希表)是完美的,但它使用了太多的RAM.

对于这种类型的东西必须有已知的方法,我一直在研究B-Tree,但我不确定它是最有效的机制.

我的问题的一些特殊性,可以导致更有效的解决方案,是:

1. 键只需要是a-z0-9或简单uint值的字符串.
2. 一旦构建,它只需要是只读的.

因为它只需要是只读的,所以在我看来,将它作为带有一系列索引的预排序列表,可能会运行良好.我一开始以为我可能只能在每个级别(即字符)中使用36(26个字母+10个数字)索引进行切片...但当然这意味着36 ^无论哪个最终与...相反高效.然后我想也许我可以为每个级别只放一个36的索引,但最后我需要交叉一组数组/切片来获取结果的ID.

我想我正在寻找某种非常具体的B-Tree实现,但更多地关注我的目的(没有B.)

有谁知道我所建议的任何存在的东西？