m 阶 B 树的最坏情况高度是 log m/2 n。
请参阅：http : //en.wikipedia.org/wiki/B-tree#Best_case_and_worst_case_heights
假设
理解问题中定义的顺序
具体来说,我们可以指望每个节点有1625个指针(一些命令的含义将其定义为键或指针的最大数量,这可能会增加下面计算的树大小)
...此树的最小深度为3,即它将具有根节点,一层非叶节点和叶节点层.......这棵树的最大深度也是3.
要在最佳情况下计算深度:
取记录总数85,000,000,除以订单1,625
这给出了叶子行数:52,308
取这个叶子行数,除以顺序
这给了33; 这个数字小于我们可以停止分割的顺序,这是根节点中的指针数量.如果这个数字超过了一个节点可以容纳的数量,我们就会有一个额外的水平并继续分裂.
我们做了两个分区,因此树深为3.
如果必须拆分所有节点,则会发生更糟糕的情况,因此平均保持订单/ 2(无舍入)指针.最坏情况的计算是相似的,我们只是除以order/2,即在我们的情况下为812.5,在叶子上方生成104,616个叶节点,129个非叶节点,最后一个根用于跟踪这些129个非叶节点.