作为n的函数，Btree的最大高度是多少？

Question

我有以下问题：

为1度的B树，什么是最大高度的树作为 树按键的数量n的功能？

我认为，因为树的顺序是1，这意味着键的数量可以在1和2之间。因此，我拿了一棵树，每个节点只有一个键，所以我可以有最大高度。添加我得到的每个级别的节点数

2^0 + 2^1 + 2^2 + ... + 2^h = n，其中n是节点的数量，h是高度树 并解决它我得到的高度是log（n + 1），但我不确定这是正确的答案。 任何想法？

Answer 1

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

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

Answer 2

身高二叉树h=log(n+1)-1

这里是推导

我在这里假设根的高度是零

所以

n=2^0+2^1+2^2........2^h 

应用几何进展形式乌拉&得到

h=log(n+1)-1. 

这里登陆基地为2 所以当有每一级只有单个节点。我们可以得到log（2）base 2，n次SO最大高度变成

h=n-1