7.4 综合题：估算B树高度

估算最小高度用最大扇出，估算最大高度用最小占用。根至少2孩子（非叶时），其余内部至少ceil(m/2)孩子；再结合叶或关键字容量计数。

手工推演

4阶B树高3时，最大结点层容量1,4,16；每结点最多3键，总键最多63。最少结构需按根与非根下界分别算，不能统一乘2。

结构与代码

外存题更关心查找访问的结点层数，即I/O次数；结点内比较通常在内存完成。

正确性

每升一层可覆盖的关键字范围按扇出倍增，所以高度是对数级。

错解反馈

所有结点都按最大占用算最大高度；把高度边数和层数混用；根也强制半满。

迁移训练

4阶B树三层最多多少关键字？答案(1+4+16)×3=63。