下溢 · borrow · merge · 前驱顶替

删除的三种修复：借与合并

插入的修复只有一种形态：溢出就分裂，中位 key 交给父节点，父节点若也溢出就照样再来一次。整条路径上每个环节的动作完全相同。

删除不是。本页把三条修复路径与它们的先后顺序讲清楚，并回答「为什么删除比插入麻烦」——答案不在渐近复杂度上，两者都是 $O(h)$ 。

1 · 下溢的判据

删掉一个 key 之后，节点的 key 数可能掉到 $\lceil m/2 \rceil - 1$ 以下。 $m = 5$ 时下限是 2，删到只剩 1 个即为下溢。

下溢不是错误状态，只是暂时违反定义 1.1 的第二条。修复动作必须同时满足两件事：把这个节点补回下限，且不让被牵连的节点自己掉下去。这两条一起，就把出路收窄到三条。

根是唯一的例外：根允许只有 1 个 key（若非叶），也允许 0 个 key（若是叶，即空树）。所以整棵树在删空的过程中一直合法。

2 · 借与合并

第一条出路是从相邻兄弟借一个。左兄弟若有多于下限的 key，把它最大的那个交给父节点，父节点原来的分界 key 降下来成为下溢节点的最小 key。三方各挪一个位置，key 的总数与顺序都不变。这是一次旋转，只不过发生在多路树上。右兄弟对称。

定义 2.1（borrow 与 merge） 设下溢节点为 $c$ ，其父为 $p$ ， $c$ 在 $p$ 中的下标为 $i$ 。

borrow：若 $p$ 的第 $i-1$ 或 $i+1$ 个孩子的 key 数严格大于下限，则通过 $p$ 的分界 key 做一次三方轮转， $c$ 得到一个 key。
merge：两侧兄弟的 key 数都恰等于下限时，把 $c$ 、 $p$ 的一个分界 key、以及该侧兄弟三者合成一个节点， $p$ 随之少一个 key 与一个孩子。

顺序不能颠倒。借的代价是常数（改三个节点，不向上传播），合并的代价可能沿路径一直传到根（父节点少一个 key，可能因此下溢）。所以能借就借，借不到才合并。

合并之所以永远合法，靠的是上下限之间那个二倍关系：两个下限节点各有 $\lceil m/2 \rceil - 1$ 个 key，加上降下来的一个分界 key，共 $2\lceil m/2 \rceil - 1$ 个。 $m$ 为偶数时这是 $m - 1$ ，正好卡在上限； $m$ 为奇数时是 $m$ 减二再加一，仍小于上限。定义 1.1 的下限取 $\lceil m/2 \rceil - 1$ 而不是别的值，理由就在这一行算术里。

图 2-1 · 阶 m 的 B-tree 单步删除。蓝框是本步涉及的节点，红色虚线框是即将并进兄弟的节点，左侧文字给出这一步选了哪条修复路径。可先装满再逐个删，观察借与合并如何交替出现。

3 · 内部节点上的 key 不能直接删

B-tree 的 key 散布在全部层级，被删的那个可能落在内部节点上。这时它不只是一个数据，还是两棵子树的分界——直接抠走会让左右两棵子树失去分隔。

做法是先换一个可以删的 key 顶上它的位置：取左子树中最大的 key（也可以取右子树最小的），写进被删的位置，然后转而删除叶子里的那个。原问题化归成「删一个叶子里的 key」，回到 §2 的三条出路。

这一步是 B-tree 独有的。B+ tree 的数据全在叶子，内部节点的 key 只是路标、允许与任何实际数据不对应，删除时压根不用碰它们（见 B+ tree：数据下沉到叶子 §3）。

4 · 修复次数的实测

$m = 5$ 的树，装 1000 个乱序 key，再按另一个乱序把它删空。引擎逐次记账：

阶段	动作	次数
插入 1000 个	分裂	365
插入 1000 个	其中根分裂	4
删除 1000 个	从兄弟借	356
删除 1000 个	与兄弟合并	365
删除 1000 个	前驱顶替	296
删除 1000 个	根被掏空、树高下降	4

图 4-1 · 装满再删光的全过程记账，左侧是插入侧的分裂次数，右侧是删除侧的借、合并与前驱顶替次数。可改阶 m 与 key 总数，观察合并次数恒等于分裂次数。

合并次数 365 与分裂次数 365 完全相等，这不是巧合：树从空开始、又回到空，每一次分裂增加的那个节点，最终必须由一次合并消掉。分裂与合并在一整个生命周期里严格配对，是节点数的守恒式。

借则没有对应的配额。356 次借的每一次都只是把 key 在兄弟之间挪了挪，节点数不变。它是删除侧比插入侧多出来的那一类动作：插入永远不需要「向兄弟要一个 key」，因为溢出的节点自己就有富余。

警示 · 前驱顶替这一步在实现时踩了个坑。原本的写法是：把前驱 key 写进内部节点的位置，递归删掉叶子里的前驱，然后 t.size--。跑不变量测试才发现 size 每次都少一——递归那一层已经减过了。语义上一次删除只减一，而这段代码里「删」出现了两次（一次是逻辑上的删 key，一次是物理上的删前驱），计数挂在哪一次上必须只挑一个。这类 bug 不会被「中序遍历等于升序集合」抓到（key 集合是对的），只有单独断言 t.size 才露出来。测试里那一行 expect(t.size).toBe(model.size) 就是为它留的。

5 · 为什么工程实现常常不做完整的删除

完整的删除逻辑要处理三条借合并路径、内部节点顶替、根收缩，代码量通常是插入的两到三倍，而且每一条分支都要在并发环境下正确加锁。merge 会改动父节点与两个兄弟，锁的范围比 split 更大。

于是相当多的生产实现选择不做。PostgreSQL 的 B-tree 索引在删除时只把 tuple 标记为死，页内空间由 VACUUM 回收；页只在完全变空时才尝试从树上摘掉，且这个动作需要额外的加锁协议。InnoDB 会做页合并，但阈值可配（MERGE_THRESHOLD，默认 50%），并不严格遵守 $\lceil m/2 \rceil - 1$ 这条下限。

放弃下限的代价是树可能变得比理论值稀疏：极端的删除模式下会留下大量近乎空的页，树高不变但页数虚高，扫描代价上升。这是一笔明确的交换：用空间与偶发的重建换掉删除路径上的复杂度与锁竞争。

6 · 参考文献

Bayer, R., & McCreight, E. (1972). Organization and maintenance of large ordered indices. Acta Informatica, 1(3), 173–189.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.), §18.3: Deleting a key from a B-tree. MIT Press.
Graefe, G. (2011). Modern B-tree techniques. Foundations and Trends in Databases, 3(4), 203–402.
Lehman, P. L., & Yao, S. B. (1981). Efficient locking for concurrent operations on B-trees. ACM Transactions on Database Systems, 6(4), 650–670.