B树的最大深度

Question

你怎么弄清楚B树的最大深度？

假设您有一个1625阶的B树，这意味着每个节点有1625个指针和1624个元素。

如果树包含85,000,000个密钥，那么树的最大深度是多少？

Answer 1

假设

• 理解问题中定义的顺序 具体来说，我们可以指望每个节点有1625个指针（一些命令的含义将它定义为键或指针的最大数量，这可能会增加下面计算的树大小）
• 叶节点将存储1625条记录（或指向这些记录的指针）这一事实

...该树的最小深度为3，即它将具有根节点，一层非叶节点和叶节点层。 ......这棵树的最大深度也是3。

要在最佳情况下计算深度：

• 取记录总数85,000,000，除以订单1,625 这给出了叶子行数：52,308
• 取这个叶子行数，除以顺序 这给了33;这个数字小于我们可以停止分割的顺序，这是根节点中的指针数量。如果这个数字超过了一个节点可以容纳的数量，我们就会有一个额外的水平并继续分裂。

我们做了两个分区，因此树深为3。

如果必须拆分所有节点，则会发生更糟糕的情况，因此平均保持订单/ 2（无舍入）指针。最坏情况的计算是相似的，我们只是按顺序/ 2，即在我们的情况下为812.5，在叶子上方生成104,616个叶节点，129个非叶节点，最后一个根用于跟踪这些129个非叶节点。

Answer 2

m阶B树的最坏情况高度是logm / 2n。

见：http://en.wikipedia.org/wiki/B-tree#Best_case_and_worst_case_heights

Answer 3

B树是平衡的，最坏情况下的检索受其高度的限制。容量顺序的Btree中的每个节点都有d。最大深度=最坏情况

d =2分之1624= 812

高度<= logd + 1（（n + 1）/ 2）+1

答案是log812 + 1（（85,000,000 + 1）/ 2）+1

Answer 4

最大深度取决于用于操纵树的算法，以及它们最糟糕的行为（我不知道具体细节，抱歉）。假设完美平衡，近似深度为log（N）/ log（1625）。

B +树可能会稍微深一些，因为只有叶子有按键，但差异可能微不足道。如果您认为每个非叶节点只需要保持指针，它也可能更浅。

Answer 5

CanBerkGüder已经给出了b树最大深度的公式。在你的情况下，m = 1625

但是具有奇数个指针和偶数个键可能不是一个好主意，因为在这种情况下，您必须在节点满时不均匀地分割节点。

相反，你应该为每个节点保持奇数个键甚至指针数，以便统一分割节点。

Answer 6

这是B +，不确定B.

在最好的情况下，85,000,000条记录记录在上限（85米/ 1624）= 52340条叶子中。这是底层，这就是为什么我们使用的是元素数而不是指针数。

为了找到有多少级别，我们将继续将我们找到的叶子数量除以顺序，沿途采取上限：上限（52340/1625）= 33。这次我们使用了指针的数量，因为我们已经确定了存储元素的底层，现在使用指向元素叶的指针。

由于这个数字不大于订单本身，我们就在那里停止，因为这是根;顶层。 Root有33个指针可以指向最多33x1625（53625）个叶子，差异不应该让你感到困惑，因为并非所有元素叶子都可以填充到最大值。 53625个叶子最多可以存储53625x1624（87,087,000）个元素，这足以说明我们的例子。

回到问题，只有根，元素留在它下面，所以深度是2。

希望这可以帮助。