b+树树高

二叉树就是log2为底N，b+树是从二叉树变化过来的多路树。m项就有 m+1个孩子指针，从头指到尾多一个。所以 时间界就是 log(m+1)为底N，的树高。你可以通过树高计算总结点数，然后两边取对数推导得到。用归纳法证明下也行。

http://blog.csdn.net/v_JULY_v/article/details/6530142/ 3.4B树的高度     根据上面的例子我们可以看出，对于辅存做IO读的次数取决于B树的高度。而B树的高度由什么决定的呢？     若B树某一非叶子节点包含N个关键字，则此非叶子节点含有N+1个孩子结点，而所有的叶子结点都在第I层，我们可以得出： 因为根至少有两个孩子，因此第2层至少有两个结点。 除根和叶子外，其它结点至少有┌m/2┐个孩子， 因此在第3层至少有2*┌m/2┐个结点， 在第4层至少有2*(┌m/2┐^2)个结点， 在第 I 层至少有2*(┌m/2┐^(l-2) )个结点，于是有： N+1 ≥ 2*┌m/2┐I-2； 考虑第L层的结点个数为N+1，那么2*(┌m/2┐^(l-2)）≤N+1，也就是L层的最少结点数刚好达到N+1个，即： I≤ log┌m/2┐((N+1)/2 )+2； 所以 当B树包含N个关键字时，B树的最大高度为l-1（因为计算B树高度时，叶结点所在层不计算在内），即：l - 1 = log┌m/2┐((N+1)/2 )+1。 这个B树的高度公式从侧面显示了B树的查找效率是相当高的。 曾在一次面试中被问到，一棵含有N个总关键字数的m阶的B树的最大高度是多少?答曰：log_ceil（m/2）(N+1)/2 + 1 （上面中关于m阶B树的第1点特性已经提到：树中每个结点含有最多含有m个孩子，即m满足：ceil(m/2)<=m<=m。而树中每个结点含孩子数越少，树的高度则越大，故如此）。在2012微软4月份的笔试中也问到了此问题。