4

我正在研究 B+树的索引，我试图理解的不仅仅是记住结构。据我了解，B+树的内部节点在叶子上形成一个索引，叶子包含指向数据在磁盘上存储位置的指针。正确的？那么查找是如何进行的呢？如果 B+tree 比二叉树好得多，为什么我们不到处使用 B+tree 而不是二叉树呢？

我阅读了关于 B+ 树的维基百科文章，我了解其结构，但不了解实际查找的执行方式。你能指导我一些阅读材料的链接吗？

除了数据库索引之外，B+ 树还有哪些其他用途？

4

2 回答 2

4

我正在研究 B+树的索引，我试图理解的不仅仅是记住结构。据我了解，B+树的内部节点在叶子上形成一个索引，叶子包含指向数据在磁盘上存储位置的指针。正确的？

不，索引由内部节点（非叶子）形成。根据实现，叶子可能包含键/值对或键/指向值对的指针。例如，数据库索引使用后者，除非它是 IOT（索引组织表），在这种情况下，值内联在叶子中。这主要取决于密钥的值是否非常大。

那么查找是如何进行的呢？

在根节点不是叶子的一般情况下（起初确实会发生），根节点包含一个由 N 个键和 N+1 个指针组成的排序数组。您对两个键 S0 和 S1 进行二进制搜索S0 <= K < S1（其中 K 是您要查找的内容），这将为您提供指向下一个节点的指针。

你重复这个过程，直到你（最终）点击一个叶子节点，它包含一个排序的键值对列表，并对它们进行最后的二分搜索。

如果 B+tree 比二叉树好得多，为什么我们不到处使用 B+tree 而不是二叉树呢？

  • 二叉树更容易实现。一个带有 B+Trees 的 cookie 是调整内部节点中键/指针的数量和叶节点中键/值对的数量。另一个虽然 cookie 是决定导致分组两个节点或爆炸一个节点的低水位线和高水位线。
  • 二叉树还提供内存稳定性：插入的元素在内存中根本不会移动。另一方面，在 B+Tree 中插入一个元素或删除一个元素可能会导致元素混洗
  • B+Trees 是为小键/大值的情况量身定制的。他们还要求可以复制密钥（希望便宜）。

你能指导我一些阅读材料的链接吗？

我希望我解释的粗略算法有所帮助，否则请随时在评论中提问。

除了数据库索引之外，B+ 树还有哪些其他用途？

同样：文件系统索引也有好处。

这个想法总是一样的：B+Tree 非常适合小键/大值和缓存。这个想法是让所有的键（内部节点）都在你的快速内存中（CPU 缓存 >> RAM >> 磁盘），B+Tree 通过将键推到底部来实现大型集合。由于所有内部节点都在快速内存中，每次搜索时您只有一次慢速内存访问（以获取值）。

于 2012-05-11T18:43:48.837 回答
3

B+ 树比二叉树好，所有 dbms 都使用它们，

在 B+Tree 中查找是 LOGF N 是 F LOG 的基数和扇出。查找的执行方式与二叉树完全相同，但扇出更大且高度更低，这就是为什么它更好的原因。

B+Tree 通常以在叶子中拥有数据而闻名（如果它们是非集群的，则可能不是），这意味着您不必再次跳转到磁盘来获取数据，您只需从叶子中获取数据。

B+Tree 几乎无处不在，操作系统使用它们，数据仓库（这里不多，但仍然如此），许多应用程序。

B+Tree 非常适合范围查询，只要您有唯一值（如主键或任何具有低基数的字段），就可以使用 B+Tree。

如果你能得到这本书http://www.amazon.com/Database-Management-Systems-Raghu-Ramakrishnan/dp/0072465638它是最好的之一。它基本上是任何数据库人员的圣经。

于 2012-05-11T08:32:43.987 回答