B 树、B+ 树与外存索引

本课针对 408 全真卷中的 B 树、B+ 树与外存索引。目标是既能在两分单选中快速排除，也能在十分综合题中保留完整过程。

考纲模型

多路平衡查找树用更高分支降低树高；B+树数据记录集中在叶层，叶结点按序链接，适合范围查询。

先定义变量、单位、初始状态与不变量。遇到结构题画字段，遇到时序题画时间线，遇到算法题写输入输出和终止条件。结论必须由题设推出，不能依赖背过的某一道题。

综合推演

m 阶 B 树每个结点至多 m 个孩子；除根外非叶结点至少有 ceil(m/2) 个孩子。查找代价要区分磁盘读块与块内比较。

书写顺序固定为：规则或公式、参数代入、中间状态、最终结论。计算完成后做数量级与边界检查；代码实现还要验证空图、不可达、重复访问和最小规模。

高频失分点

B树的阶、关键字数、孩子数上下界必须按教材定义统一；不能把B树和二叉搜索树套用同一高度公式。

全真训练中，选择题最多用反例与量词检查；综合题即使最后数值错误，也要保留可评分的中间式、状态表和复杂度。代码题必须真运行，不接受只覆盖样例的硬编码。

课后验收

完成本课单选、多选和综合应用题。单选解释三个错误项，多选不得漏选；计算保留单位，文本按要点作答，代码必须通过四个独立测试。次日遮住答案重做，并记录耗时。