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

EN

实际的B树和B+树实现往往有固定字节大小的节点，这些节点被选择来匹配体系结构的页面大小，或者像磁盘上的集群大小这样的其他固定设备。一个典型的值将是4096字节。

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

B+树的第二个优点是，内部节点中的密钥仅用于将搜索路由到右叶。他们只需要把左边的东西和右边的东西分开，但是它们不需要与任何实际的记录键相对应。这意味着它们通常可以被缩短，而且还意味着删除不需要从叶层传播到索引层(也就是说，一旦从叶中删除了一个键，就完成了-除了在重新平衡过程中自然发生的情况之外，不需要从内部节点删除任何内容)。

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

在B树中，间隔可能位于父节点上，因此磁盘访问将被最小化。

为了使这个理论得到休息，估计B树的内部节点中有多少键总数，叶节点中有多少键总数。这一比率告诉你，在下降到叶级之前，搜索可能会提前停止多久。注意:早出方案只适用于在树中恰好存在精确键的查询；否则，就不可避免地会出现适当的叶级。