问B+树查找编号oF记录
EN

Stack Overflow用户

提问于 2016-01-31 05:18:15

回答 1查看 2.4K关注 0票数 0

最近我在学习的时候遇到了这样一个问题

B+树和B树索引的最低级别为5000键，B+树节点(P)的顺序为10。(假设P是可以存储在B+树节点中的最大指针)

我计算了Btree，它恰好是4个级别。在尝试B+树时，我最终陷入了困惑。所讨论的顺序是内部节点顺序还是叶节点顺序。如果是内部节点顺序，那么如果不知道叶节点的顺序，如何才能计算所需的级别数。有人能帮我吗？

发布于 2016-02-01 12:33:59

你说得对，这个问题应该提到叶节点的容量。

不管是什么--让我们称它为L --所需的叶节点数量显然是ceiling(N / L)，因为叶节点层必须包含所有数据。如果每个叶节点最多能容纳10个记录(数据项)，那么我们得到的最小叶节点数为500。一旦您有了所需的叶节点数，您就可以像往常一样计算B树索引部分的所需高度。

在我们的示例中，内部节点的最低层(即B+树索引部分的最底层)需要至少500个传出指针才能到达每个叶。ceiling(log(500)/log(10))为3，这给出了序列集之上索引级别的最小数目。因此，在这种情况下，B+树至少有4个级别，就像普通的B树一样。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/35110607

复制

相似问题

问B+树查找编号oF记录EN