如何计算 B 树的最大深度？
假设你有一个 1625 阶的 B 树，这意味着每个节点有 1625 个指针和 1624 个元素。
如果树包含 85,000,000 个键，它的最大深度是多少？
问问题
23355 次
6 回答
5
m 阶 B-Tree 的最坏情况高度是 log m/2 n。
见：http ://en.wikipedia.org/wiki/B-tree#Best_case_and_worst_case_heights
于 2010-04-05T22:25:40.340 回答
5
假设
对问题中定义的顺序的理解
具体来说，我们可以指望每个节点有 1625 个指针（顺序的某些含义将其定义为键或指针的最大数量，这可能会增加下面计算的树大小）
- 叶节点也将存储 1625 条记录（或指向这些记录的指针）的事实
... 这棵树的最小深度为 3，即它有一个根节点、一层非叶节点和一层叶节点。...这棵树的最大深度也为 3。
要在最佳情况下计算深度：
取记录总数，85,000,000，除以顺序，1,625
这给出了叶行数：52,308
取这个叶行数，除以顺序
这给出了 33；这个数字小于顺序那么我们就可以停止划分，这是根节点中的指针数量。如果这个数字超过了一个节点可以容纳的数量，我们就会有一个额外的级别，并且会继续划分。
我们做了两个划分，所以树的深度是 3。
如果所有节点都必须被拆分，则更糟糕的情况会发生，因此平均持有 order/2（无舍入）指针。最坏情况的计算是类似的，我们只是除以 order / 2 ，即在我们的例子中为 812.5，产生 104,616 个叶节点，129 个在叶之上的非叶节点，最后一个根来跟踪这些129 个非叶节点。
于 2010-04-05T22:35:11.667 回答
1
B树是平衡的，最坏情况的检索受其高度限制。容量顺序B树中的每个节点都有d。最大深度 = 最坏情况
d=1624/2=812
高度 <= log d+1 ((n+1)/2)+1
答案是对数812+1 ((85,000,000+1)/2)+1
于 2014-12-30T14:02:50.993 回答
0
最大深度取决于用于操纵树的算法，以及它们的最坏情况行为是什么（我不知道具体情况，抱歉）。假设完美平衡，近似深度为 log(N)/log(1625)。
B+-树可能稍微深一些，因为只有叶子持有密钥，但差异可能可以忽略不计。如果您认为每个非叶节点只需要保存指针，它也可能会更浅。
于 2010-04-05T22:24:04.773 回答
0
这是针对B+的，不确定B。
85,000,000 条记录，在最好的情况下，记录在天花板（85m/1624）=52340 个叶子中。这是底层，这就是我们使用元素数量而不是指针数量的原因。
为了找出有多少层，我们将继续将找到的叶子编号按顺序除以沿途的上限：上限（52340/1625）=33。这次我们使用指针的数量，因为我们已经确定了存储元素的底层，现在使用指针指向元素叶子。
由于这个数字不大于订单本身，所以我们停在那里，因为这是根；顶层。Root 有 33 个指针，最多可以指向 33x1625 (53625) 个叶子，差异不应让您感到困惑，因为并非所有元素叶子都可以填充到最大值。53625 个叶子最多可以存储 53625x1624 (87,087,000) 个元素，这足以容纳我们的示例。
回到问题，只有根，元素在它下面，所以深度是2。
希望这可以帮助。
于 2013-06-16T19:35:39.877 回答
0
Can Berk Güder 已经给出了 ab 树的最大深度的公式。在你的情况下 m = 1625
但是拥有奇数个指针和偶数个键可能不是一个好主意，因为在这种情况下，当节点已满时，您将不得不不均匀地拆分它。
相反，您应该为每个节点保留奇数个键和偶数个指针，以统一分割节点。
于 2012-04-26T07:08:28.743 回答