B树的最大深度
如何计算 B 树的最大深度？
假设您有一个阶数为 1625 的 B 树，这意味着每个节点有 1625 个指针和 1624 个元素。
如果树包含 85,000,000 个键，它的最大深度是多少？
How do you figure out the maximum depth of a B-tree?
Say you had a B-tree of order 1625, meaning each node has 1625 pointers and 1624 elements.
What is the maximum depth of the tree if it contains 85,000,000 keys?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
m 阶 B 树的最坏情况高度是 logm/2n。
请参阅：http://en.wikipedia.org/wiki/B-tree#Best_case_and_worst_case_heights
The worst case height for a B-Tree of order m is logm/2n.
See: 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。
如果必须拆分所有节点，则会发生最糟糕的情况，因此平均保留 order/2（无舍入）指针。最坏情况的计算类似，我们只需除以 order / 2 ，即我们的例子中的 812.5 ，产生 104,616 个叶节点，叶节点上方的 129 个非叶节点，最后一个根来跟踪这些节点129 个非叶节点。
Assuming
the understanding of the order defined in the question
Specifically that we can count on having 1625 pointers per node (some meanings of order define it as the maximum number of keys or pointers, which would then potentially increase the tree size computed below)
... this tree would have a minimum depth of 3, i.e. it would have a root node, one layer of non-leaf nodes, and the layer of leaf nodes.
... this tree would have a maximum depth of 3 as well.
To compute the depth in the most optimal case:
take the total number of records, 85,000,000, divide by the order, 1,625
this gives the count of leaf-rows : 52,308
take this number of leaf-rows, divide by the order
this gives 33; this number is less than the order then we can stop dividing, this is the number of pointers in the root node. Had this number been more than what one node can hold we'd have an extra level and would continue dividing.
We made two divisions so the tree depth is 3.
The worse case would happen if all nodes had had to be split, hence holding on average the order/2 (no rounding) pointers. The calculation for the worse case is similar, we just divide by order / 2 , i.e. 812.5 in our case, producing 104,616 leaf-nodes, 129 non-leaf nodes at the level above the leaves, and finally one root to keep track of these 129 non-leaf nodes.
B树是平衡的，最坏情况下的检索受其高度的限制。容量顺序的B树中的每个节点都有d。最大深度 = 最坏情况
d=1624/2=812
高度 <= logd+1 ((n+1)/2)+1
答案是 log812+1 ((85,000,000+1)/2)+1
B tree is a balanced , the worst case retrieval is bounded by its height.Each node in a Btree of capacity order has d. Maximum depth = worst case
d=1624/2=812
Height <= logd+1 ((n+1)/2)+1
the answer is log812+1 ((85,000,000+1)/2)+1
最大深度取决于用于操纵树的算法，以及它们最坏情况的行为是什么（抱歉，我不知道具体细节）。假设完美平衡，近似深度为 log(N)/log(1625)。
B+ 树可能会稍微深一点，因为只有叶子保存键，但差异可能可以忽略不计。如果您认为每个非叶节点只需要保存指针，它也可能会更浅。
Maximum depth depends on the algorithms used to manipulate the tree, and what their worse-case behavior is (I don't know the specifics, sorry). The approximate depth is log(N)/log(1625), assuming perfect balancing.
A B+-tree might be slightly deeper because only the leaves hold keys, but the difference is probably negligible. It also might be shallower if you consider that each non-leaf node only has to hold pointers.
Can Berk Güder 已经给出了 ab 树最大深度的公式。
在你的情况下 m = 1625
但是拥有奇数个指针和偶数个键可能不是一个好主意
因为在这种情况下，当节点已满时，您将不得不不均匀地分割节点。
相反，您应该为每个节点保留奇数个键和偶数个指针，以实现节点的统一分裂。
The formula for max depth of a b tree has already been given by Can Berk Güder.
In your case m = 1625
But having odd number of pointers and even number of keys may not be a good idea
because in that case, you will have to unevenly split a node when it is full.
Rather you should keep odd number of keys and even number of pointers per node for uniform splitting of nodes.
这是针对B+的，不确定B。
在最好的情况下，85,000,000条记录记录在ceiling(85m/1624)=52340个叶子中。这是底层，这就是为什么我们使用元素数量而不是指针数量。
为了找到有多少层，我们将继续将找到的叶子编号除以顺序，并沿途取上限：上限（52340/1625）= 33。这次我们使用指针的数量，因为我们已经确定了存储元素的底层，现在使用指针来指向元素叶子。
由于这个数字不大于订单本身，我们就到此为止，因为这是根；顶级。 Root 有 33 个指针，最多可以指向 33x1625 (53625) 个叶子，这种差异不应让您感到困惑，因为并非所有元素叶子都可以填充到最大值。 53625 个叶子最多可以存储 53625x1624 (87,087,000) 个元素，这足以容纳我们的示例。
回到问题，只有根，元素在它下面离开，所以深度是2。
希望这有帮助。
This is for B+, not sure about B.
85,000,000 records, in best case, are recorded in ceiling(85m/1624)=52340 leaves. This is the bottom level, and it is why we are using number of elements rather than number of pointers.
To find how many levels there are, we'll keep dividing the leaf numbers we find to the order, taking the ceiling along the way: ceiling(52340/1625)=33. This time we are using the number of pointers, because we already determined the bottom level, where elements are stored, and now working with pointers to point to element leaves.
As this number is not greater than the order itself, we stop there, because this is the root; top level. Root has 33 pointers that can point to a max of 33x1625 (53625) leaves, the difference shouldn't confuse you as not all of the element leaves could be filled to the max. 53625 leaves can store at most, 53625x1624 (87,087,000) elements in them, which is more than enough to hold our example.
Back to the question, there is only the root, and the element leaves below it, so the depth is 2.
Hope this helps.