B树、B+树与磁盘索引

考点定位

本课深化 B树、B+树与磁盘索引。408作答必须同时给出数据结构表示、算法过程、不变量、复杂度和边界条件。

结构与取舍

m阶B树每结点最多m棵子树、m-1个关键字；除根外非叶结点至少ceil(m/2)棵子树。B+树数据通常集中在叶层并用链连接。

算法推演

查找在结点内定位区间后只沿一棵子树下降；插入溢出时围绕中间关键字分裂并向父结点提升，可能递归到根。

把算法写成“初始化—循环条件—状态更新—终止输出”。若使用递归、队列、堆或并查集，要指出其中保存的状态及何时失效。

正确性不变量

所有叶结点位于同一层，结点占用率下界由阶数和根例外共同决定。

初始化时不变量成立；一次迭代保持它；循环结束时它与终止条件共同推出答案。这是算法题证明的最短主线。

复杂度与边界

时间复杂度必须按输入规模和存储结构计算，不能只报结论。严格边界：B树的“阶”通常指最大孩子数，作题前仍要核对题目是否另有定义。

随课应用

5阶B树中，非根非叶结点最少有多少个关键字？

先独立计算或编码，再完成单选与多选。代码题从标准输入读取并写到标准输出，不得硬编码样例；数值题需写出中间状态。