7.4.1 B树

m阶B树每结点最多m个孩子、m-1个关键字；除根外至少ceil(m/2)个孩子，所有叶在同层。结点内关键字有序并分隔子树范围，降低外存I/O。插入到叶，溢出则按中间键分裂并向上提升；删除不足则借兄弟或合并。

手工推演

4阶B树结点最多3键。叶[10,20,30]插25得4键，分裂并提升中间键（具体取法按约定），形成两个合法结点；若根分裂，高度加1。

结构与代码

一次结点访问内可折半定位分支。树高按每结点最少分支数呈对数，磁盘页通常对应一个结点。

正确性

分裂后左右键范围被提升键分隔；借与合并恢复最少占用且保持所有叶同层。

错解反馈

把阶m当最多m个关键字；叶不等深；删除下溢不修复；把B树称二叉树。

迁移训练

5阶B树非根结点最少几个孩子和关键字？答案3个孩子、2个关键字。