如果我们知道存储在 B-Tree 中的键的数量，以及 B-Tree 的顺序（即非根节点的子指针的最大数量），是否有一个简单的对数方程来确定树的高度会是多少？
问问题
2267 次
1 回答
2
查看维基百科：
设 m 为每个节点的子节点数，高度为 h 且其所有节点完全填充的 B 树有 n=mh-1 个条目。
B树的最佳案例高度是：
ceil( log_m(n+1) )
令 d 为内部（非根）节点可以拥有的最小子节点数。对于普通的 B 树，d=⌈m/2⌉。
B树的最坏情况高度是：
floor( log_d( (n+1)/2 ) + 1 )
于 2013-10-09T23:31:17.393 回答