B树插入与分裂

从一次容器误用开始

先看场景：对最小度2的树插入序列并逐次输出层次。数据结构不是节点图鉴，而是调用者依赖的操作语义、内部表示和复杂度承诺。遇到结果错误、死循环、内存泄漏或性能陡降时，第一问不是“这是什么结构”，而是哪个公开操作违反了契约，哪条表示不变量首次失效，或哪种输入让原先的复杂度假设不成立。
（长段唯一锚点：DS-11-03-B树插入与分裂。）

本节核心机制是：向叶插入，满节点分裂并把中键提升父节点，根分裂增加高度。请把它拆成输入状态、操作步骤、输出/异常和保持的不变量。若只能说“用链表更快”“哈希是O(1)”，说明还没有把操作、前提和成本模型说完整。（唯一锚点：数据结构11-3《B树插入与分裂》。）
（长段唯一锚点：DS-11-03-B树插入与分裂。）

先写ADT契约与表示不变量

在纸上列公开值域、操作、前置条件、正常后置条件、失败后状态和迭代顺序。再列内部字段及不变量，例如size与可达节点数一致、数组有效区间连续、双链相邻互指、BST满足祖先范围、堆满足父子序、哈希探测不会在墓碑提前停止。调用者只能依赖契约，测试则要主动查看内部不变量。
（长段唯一锚点：DS-11-03-B树插入与分裂。）

关键边界是：分裂索引和孩子分配错一位会破坏键范围，重复键策略也需明确。把它改成最小操作序列：写出初态，每一步调用及返回，再画操作后的内部状态。边界测试不是额外装饰，而是验证空结构、单元素、重复值、容量临界、退化高度或非法索引下仍守住同一契约。（契约锚点：DS-11-03。）
（长段唯一锚点：DS-11-03-B树插入与分裂。）

分三轮把本节真正实现出来

第一步，先构造B树插入与分裂的最小表示，写出字段、初态和验证器，并用“对最小度2的树插入序列并逐次输出层次”中的最小正常输入跑通一条操作链。接着，依据“向叶插入，满节点分裂并把中键提升父节点，根分裂增加高度”逐指针、逐索引或逐父子关系执行变换，每一步记录size、容量、头尾、根、桶、父指针或候选集合，不允许直接跳到最终输出。最后，加入“分裂索引和孩子分配错一位会破坏键范围，重复键策略也需明确”对应的失败序列，检查返回值、异常、结构不变量和复杂度计数；修复后用不同规模和操作顺序再跑一次。（推进链唯一锚点：B树插入与分裂-11-3。）
（长段唯一锚点：DS-11-03-B树插入与分裂。）

跟我做一次操作与成本推演

固定输入和状态后，先画操作前结构，再为每个比较、索引、指针改写、元素移动或节点访问计数。假设本节有11个元素、每个元素触发5次题设基本操作，在不含扩容、缓存和对象分配的简化模型下共有 11×5=55 次。然后再问真实算法是否只访问全部元素一次、沿高度走一条路径，还是因嵌套/搬移访问平方数量。
（长段唯一锚点：DS-11-03-B树插入与分裂。）

Big-O必须对应操作和输入分布。最坏、均摊、期望、构建和查询成本不能混写。常数与缓存虽被渐进式隐藏，却会决定数组与链表在相同O(n)扫描下的真实差异。（推演锚点：B树插入与分裂。）

可运行实现与测试

代码题从标准输入读取操作日志并输出稳定结果，使用Python或C++17；不调用目标结构的标准库实现冒充核心算法。每题至少四组测试：正常、空/单元素、边界或退化、回归。测试既比较公开结果，也要让实现内部验证size、链接、范围、堆序、桶状态或分量数量。
（长段唯一锚点：DS-11-03-B树插入与分裂。）

你要补第五组测试，优先选择重复键、非法位置、扩容、删除后再插入、深链、相同优先级、非连通图或版本化恢复。随机性质测试需保存操作序列，不能靠不可复现的随机运行。（实现锚点：B树插入与分裂。）

常见错误与故障注入

主动打断一次更新：只改一半链接、扩容搬到一半、删除后留下墓碑错误、旋转后漏接父节点或迭代中修改结构。预测哪个不变量先失败，再让验证器定位。不要只在最终崩溃处修补；首个错误通常发生在更早的指针/索引写入顺序。

遇到性能问题也要做故障注入：给BST有序输入、哈希同桶键、动态数组固定增量扩容、图的稠密/稀疏极端。用操作计数而不是墙钟偶然波动证明复杂度变化。（错误锚点：B树插入与分裂。）

与前后结构建立联系

向前追问本节依赖的ADT、数组、链接或递归不变量，向后追问它怎样支持算法、索引、图或容器库。画三条因果箭头并注明操作复杂度。例如动态数组提供堆的连续完全树表示，堆提供优先队列语义，优先队列又成为后续图算法的候选边界。

同一个需求常有多个候选结构。列决策表比较查询、插入、删除、顺序、内存、缓存和最坏保证，不要只挑一个最小Big-O。（连接锚点：B树插入与分裂。）

在线练习与严格验收

每节至少绑定单选、多选和计算题，逐章另有真实实现题。单选先圈ADT操作与输入条件，多选逐项构造反例，计算题写原始操作计数，代码题通过全部测试并补退化序列。章节卷、期中、期末、实现与复杂度专项使用独立题池。

错题按契约、边界、不变量、指针/索引顺序、复杂度类型、迭代失效或键语义分类。更换数据规模和操作顺序重做，能在新序列下维护不变量才算学会。（练习锚点：B树插入与分裂。）

下课前闭卷自检

一，写B树插入与分裂的ADT操作。二，列内部字段和至少三个表示不变量。三，手推“向叶插入，满节点分裂并把中键提升父节点，根分裂增加高度”的更新顺序。四，为“对最小度2的树插入序列并逐次输出层次”补退化测试。五，解释“分裂索引和孩子分配错一位会破坏键范围，重复键策略也需明确”。六，分别写单次最坏与操作序列成本。七，说明何时应换另一种结构。
（长段唯一锚点：DS-11-03-B树插入与分裂。）

若答案仍是“用树更快”“哈希O(1)”“标准库有”，回到契约、状态图和操作计数。合格不是认出结构，而是能从空实现写出、验证、分析并迁移到真实工作负载。（自检锚点：B树插入与分裂。）