c++ - 使用 B 树和 B+-树的范围查询

Question

我正在编写一个程序来检索给定范围内的对象数量，并且我正在使用 B 树数据结构来实现我的解决方案，因为对象数量无法容纳在 RAM 中。我看到几篇文章说 B+ 树在范围查询方面比 B 树优越得多，并且被所有主要的数据库实现所使用。我无法理解为什么 B+ 树优于 B 树，因为所有数据都存储在叶子上，并且需要 h(树的高度)磁盘访问来检索节点并执行范围查询，而在 B 树中间隔可能位于父节点上，因此磁盘访问将被最小化。此外，如果我有一个查询，例如 return # of objects of a particular key，那么我可以在 B+ 树中一直下降到叶子之前找到该键。那么为什么他们说 B+ 树比范围查询的 B 树更有效呢？如果我必须编写一个程序来执行范围查询，B 树不应该是正确的数据结构吗？提前感谢您的回复!

Answer 1

实际的 B 树和 B+ 树实现往往具有固定字节大小的节点，这些节点被选择为与体系结构的页面大小或其他固定装置(如磁盘上的簇大小)相匹配。典型值为 4096 字节。

B+ 树可以将更多的键放入内部节点，因为记录数据不需要空间。这提供了更高的扇出(更低的树高度)和更好的缓存利用率，因为一组给定的索引页(内部节点)“覆盖”了比 B 树更多的查询。

B+ 树的第二个优点是内部节点中的键只需要将搜索路由到右叶。他们只需要将左边的东西和右边的东西分开，而不必对应于任何实际的记录键。这意味着它们通常可以被缩短，也意味着删除不必从叶层传播到索引层(即，一旦你从叶中删除了一个键，你就完成了 - 不需要从内部节点删除任何东西，除了在重新平衡期间自然发生的事情)。

此外，在典型的 B+ 树中，叶节点具有指向其左右兄弟节点的指针。这意味着您可以通过遍历页面的链接列表来迭代一系列记录，而不必使用 B 树典型的棘手迭代逻辑。

in the B tree the interval may be located on parent nodes and the disk accesses would be thus minimized

为了让该理论得到休息，估计总共有多少键位于 B 树的内部节点中，以及总共有多少键位于叶节点中。该比率告诉您在一直下降到叶级别之前搜索可以提前停止的频率。注意:早出方案仅适用于 exact 键恰好出现在树中的查询；否则体面到叶子级别是不可避免的。