推导B树的最大高度和最小高度得出B树的高度范围

前提条件：n>=1，则对于任意一棵包含n个关键字、高度为h、阶数为m的B树。

一、最小高度：

对于任意树类型的数据结构，如果其每层节点能够分布的足够满，其高度也会随之变得足够的低。基于这个思路，对于B树无外乎也是一种树，B树的关键字数以及儿子节点个数满足这样的条件(ceil代表向上取整)：

//根节点   
儿子节点个数[2, m]
关键字个数[1, m-1]

//非根节点
儿子节点个数[ceil(m/2), m]
关键字个数[ceil(m/2)-1, m-1]

为了使得B树高度最低，也就是每层的节点数达到最大，看如下的计算过程：

在这里插入图片描述

二、最大高度：

要使得B树的高度达到最大，也就意味着在每个节点中，关键字的个数达到最小，这样在容纳相同个数的关键字的B树中，其高度可以达到最大。

在这里插入图片描述

有了上边我们对最小关键字大小把控，下面来推到B树的最大高度：

在这里插入图片描述

总结：

由一和二可知，通过寻找B树的两种极限的存在，推出B树的高度范围为：logm(n+1)<= h <=log(ceil(m/2)) (n+1)/2 + 1