B+ 树删除：页合并、借位与根收缩

2026/11/4 · Stack Frame

分类：数据库内核 · 标签：后端 存储引擎 性能优化 数据库

适用读者：删掉一半数据后发现表文件没变小的人；想知道 B+ 树删除为什么比插入复杂的人；在 InnoDB 与 SQLite 之间做选型、需要理解两者空间回收差异的人 结论先行：B+ 树删除的第一动作永远是「在叶子页里移除一个键」，真正麻烦的是移除之后页快空了怎么办。标准做法只有两种：向兄弟页借几个键（redistribute），或者把两个页合并成一个（merge）。合并会让父页少一个孩子，父页也可能因此下溢，于是这个过程可能一路递归到根。InnoDB 还把「标记删除」和「物理移除」拆成了两步，所以 DELETE 之后空间往往不会立刻回收。 阅读时间：约 16 分钟 | 难度：进阶 | 收获：删除的完整路径、借位与合并的判定、父页分隔键与根收缩、InnoDB 与 SQLite 的两套实现对照、以及碎片观测与回收办法
目录
  • 前言：删了一半数据，表为什么没变小
  • 删除的第一动作：在叶子里移除一个键
  • InnoDB：先标记，后 purge
  • 什么情况下页算「下溢」
  • 借位：从兄弟页搬几个键
  • 合并：把两个页压成一个
  • 父页的分隔键怎么改
  • 根页怎么收缩
  • SQLite 的 balance_nonroot：一次重排多个兄弟页
  • 两套实现对照
  • 为什么 InnoDB 不急着合并
  • OPTIMIZE TABLE、fill factor 与碎片
  • 怎么观测页利用率
  • 五个常见误区
  • 小结

前言：删了一半数据，表为什么没变小

一张 10 GB 的表，DELETE 掉一半行，文件大小可能几乎不变。很多人第一反应是「删除没生效」，查一遍 COUNT(*) 又确实少了。 原因有两层：
  • 第一层是 MVCC：DELETE 只是给记录打删除标记，旧版本还要留给可能存在的快照读；
  • 第二层是 B+ 树：即使记录被物理移除，页也不一定会合并，空的页也不一定会立刻还给操作系统。
第一层见 MySQL MVCC：版本链与 Read View 是怎么判可见性的。本文讲第二层：B+ 树的删除到底做了什么。

删除的第一动作：在叶子里移除一个键

不管哪套实现，删除的入口都一样：
  1. 从根页开始，按 key 比较，一路向下找到目标叶子页；
  2. 在叶子页里定位到目标键；
  3. 移除这个键和它对应的记录；
  4. 检查这个页是否还满足 B+ 树的最小填充约束；
  5. 如果不满足，进入重平衡流程；
  6. 重平衡可能影响父页，于是向上递归；
  7. 如果根页只剩一个孩子，树高减一。
第 1 到第 3 步是「局部删除」，第 4 到第 7 步才是「重平衡」。B+ 树删除的复杂度里，大部分工程细节都在第 4 到第 7 步。

InnoDB：先标记，后 purge

InnoDB 的 DELETE 不是立刻从页里抹掉记录，而是分两步：
  • 标记删除：在记录头里置上删除标记（delete mark），记录还在页里，版本链也还在；
  • purge：后台线程扫描 undo log，确认没有更早的 Read View 需要这个版本后，才真正把记录从页里移除。
第二步才会调用 B+ 树的删除逻辑，可能触发页合并。也就是说：
DELETE 语句的耗时，和「页合并」的耗时不一定是同一时刻发生的。
这带来两个直接后果：
  • DELETE 之后立刻看表大小，往往没变化；
  • 如果 purge 被长事务挡住，删除的空间会一直挂着。
SHOW ENGINE INNODB STATUS 的 History list length 持续上涨，通常意味着 purge 落后，删除的物理回收也被拖住了。

什么情况下页算「下溢」

B+ 树对每个非根节点都有最小填充要求。常见的定义是：
  • 内部节点至少有 ceil(m/2) 个孩子；
  • 叶子节点至少有 ceil(m/2) - 1 个键。
其中 m 是 B+ 树的阶。换成更直观的说法：非根页大约要保持半满。 删除一个键后，如果页里的键数低于这个下限，就叫「下溢」（underflow）。下溢本身不是错误，页里仍然能读，只是空间利用率变差；但 B+ 树必须通过重平衡来维持「树高不会因为删除而虚高」的性质。 这里要区分两个概念：
  • 页内碎片：页里已经删除但还没整理的空间；
  • 页间碎片：相邻页都没满，却没有合并。
前者靠页内整理（compact）解决，后者靠借位或合并解决。

借位：从兄弟页搬几个键

借位（redistribute / borrow）的前提是「隔壁页比较富余」。做法是：
  1. 找到下溢页的左兄弟或右兄弟；
  2. 如果兄弟页的键数高于下限，就从兄弟页搬一个或几个键过来；
  3. 同时更新父页里对应的分隔键；
  4. 下溢页恢复到达标，父页的孩子数量不变。
借位的好处是不改变树的结构，父页只需要改一个分隔键，代价很小。坏处是它要求兄弟页「有余粮」。如果左右兄弟都刚好半满，就借不到，只能合并。

合并：把两个页压成一个

合并（merge）的前提是「两个页的键能装进一个页」。做法是：
  1. 把下溢页和左兄弟或右兄弟合并；
  2. 从父页里删掉指向被合并页的那一项；
  3. 被合并页回收进 freelist；
  4. 父页少了一个孩子，可能因此下溢；
  5. 对父页重复上述流程，直到某一层不再下溢，或者到达根。
合并的代价比借位大：它要移动记录、改父页、可能递归、还可能释放页。但它能真正减少页数，提高空间利用率。 一个容易忽略的点：合并的触发条件不是「页低于半满」，而是「两个页能装进一个页」。如果两个页都接近半满，合起来超过一页容量，即使某一页略低于下限，也只能借位，不能合并。这个条件比「半满」更严格，也是 InnoDB 删除后页数下降不明显的原因之一。

父页的分隔键怎么改

B+ 树的内部页存的是「子页的最小键 + 页号」。删除会动摇这个分隔键：
  • 如果删掉的不是子页的第一个键，分隔键不变；
  • 如果删掉的正好是子页的第一个键，父页的分隔键要改成子页新的第一个键；
  • 如果发生借位，父页的分隔键要跟着兄弟页搬走的键更新；
  • 如果发生合并，父页要删掉一个「键 + 页号」项。
这一步最容易被实现细节坑住：分隔键不是「随便存一个键」，它必须是子页下界的一个合法代表。改错了，后续查找会走错分支。

根页怎么收缩

根页是唯一允许低于半满的节点。删除一路递归到根时，会出现两种情况：
  • 根页还有至少两个孩子：树高不变；
  • 根页只剩一个孩子：把这个孩子提升为新的根，树高减一。
树高减一是删除操作对查询性能的唯一正面影响：原来三层树，现在两层，每次查找少一次页访问。 但树高不会无限下降。只要还有足够多的键，根页就会保持至少两个孩子。

SQLite 的 balance_nonroot：一次重排多个兄弟页

SQLite 的 B+ 树删除走的是另一条路线。sqlite3BtreeDelete 最终会调用 btreeDeleteRow，删掉单元格后再调用 balance()。 balance() 的核心是 balance_nonroot：
  1. 把下溢页和它左右最多两个兄弟页一起拿出来；
  2. 把这些页里的所有单元格重新排序；
  3. 按新的分布重新装页，尽量让每页填充均匀；
  4. 需要时新建页或释放页；
  5. 更新父页的分隔键。
它的特点是一次处理「最多三个兄弟页」，而不是只借一个、只合一个。这样能同时解决多个页的碎片问题，重排后的填充率更均匀。 如果根页溢出，SQLite 用 balance_deeper 创建一个新的根；如果根页只剩一个孩子，用 balance_shallower 把子页内容搬回根页并降低树高。 SQLite 的页头里有三个关键计数：
  • nCell：当前单元格数量；
  • nFree：空闲字节数；
  • nFrag：碎片字节数。
nFrag 就是「页内碎片」的直接度量，balance_nonroot 会把它一起整理掉。

两套实现对照

维度 InnoDB SQLite
删除时机 先标记删除，purge 时物理移除 删除语句内直接移除单元格
重平衡范围 通常与一个兄弟页借位或合并 最多三个兄弟页一起重排
合并条件 两个页的记录能装进一个页 重排后按容量重新分布
父页更新 改分隔键或删一项 改分隔键或删一项
根收缩 根只剩一个孩子时提升孩子 balance_shallower
空间回收 依赖 purge + OPTIMIZE TABLE 依赖 VACUUM
页内碎片 PAGE_GARBAGE 等计数 nFrag 计数
两套实现的共同点是：删除的局部操作很简单，重平衡才是复杂度所在；不同点是「一次处理几个页」和「什么时候真正回收空间」。

为什么 InnoDB 不急着合并

InnoDB 的删除合并相对保守，原因有几层：
  • 合并本身有成本：要移动记录、改父页、可能递归，还要考虑并发锁；
  • 合并可能立刻被拆开：如果业务是「删了又插」，刚合并的页可能马上又分裂，白做一次；
  • MVCC 还在用旧版本：purge 没清完之前，记录不能真正移除；
  • 顺序插入的局部性好：保留一些半满页，反而给后续插入留了空间，减少分裂。
所以 InnoDB 的策略更像「延迟整理」：删除时尽量少动结构，把空间回收交给 purge 和重建。这个策略在写多读少的 OLTP 里通常划算，但在「大批量删除后表再也不会增长」的场景里，就需要手动重建。

OPTIMIZE TABLE、fill factor 与碎片

OPTIMIZE TABLE 对 InnoDB 来说，本质是重建表： 
OPTIMIZE TABLE events;
它会创建一个新表、按主键顺序把数据插进去、重建所有索引、再替换旧表。效果是：
  • 消除页内碎片；
  • 重新分配页，提高填充率；
  • 可能降低树高；
  • 回收未使用的空间。
代价是：
  • 需要额外的磁盘空间；
  • 期间可能锁表或影响写入（取决于算法与版本）；
  • 大表耗时长。
innodb_fill_factor 控制「建索引时每页填多满」，默认 100。它作用于索引构建（CREATE INDEX、OPTIMIZE TABLE 重建），不作用于运行时的页分裂。把它调低会留下更多空间给后续插入，但索引会变大。 innodb_page_size 决定页大小，默认 16 KB。页越大，单页能装的键越多，树越矮；但页内碎片和单页 IO 的代价也更大。

怎么观测页利用率

几个可用入口： 
-- 表的空闲空间（不是页内碎片）
SELECT table_name, data_length, index_length, data_free
FROM information_schema.TABLES
WHERE table_schema = 'your_db';
data_free 是「已分配但未使用的空间」，它不等于「页内碎片」。要区分：
  • data_free 大：可能有整页空闲，或者表空间没回收；
  • 表大小没降但 data_free 不大：更可能是页内碎片或页间未合并。
想看页级细节，可以用 innodb_ruby 导出索引页，观察：
  • PAGE_N_RECS：页内记录数；
  • PAGE_GARBAGE：已删除记录占用的字节；
  • PAGE_FREE：空闲链表；
  • 每页的填充率。
SQLite 则可以直接读页头的 nCell、nFree、nFrag，或者用 PRAGMA page_count、PRAGMA freelist_count 看页数与空闲页数。

五个常见误区

误区一：「DELETE 之后空间会立刻回收」。InnoDB 不会，要等 purge，页合并也不保证发生。 误区二：「页低于半满就一定会合并」。不一定，合并要求两个页能装进一个页；装不下就只能借位。 误区三：「OPTIMIZE TABLE 只是整理碎片，不影响业务」。它要重建表，会占额外磁盘、可能锁表，大表要安排窗口。 误区四：「树高只会在插入时增加」。删除也会改变树高，只是方向相反：根收缩时树高减一。 误区五：「data_free 就是页内碎片」。不是。data_free 是表空间层面的空闲，页内碎片要看 PAGE_GARBAGE 或 SQLite 的 nFrag。

小结

问题 答案
删除第一步做什么 在叶子页里移除键
页快空了怎么办 借位或合并；合并可能递归到根
父页要改什么 分隔键或孩子项
树高什么时候降 根只剩一个孩子时
InnoDB 为什么空间不立刻回收 先标记删除，purge 才物理移除；合并也保守
怎么真正回收 OPTIMIZE TABLE 重建；SQLite 用 VACUUM
相关阅读

专题：数据库内核 — B+ 树、WAL、MVCC 与存储引擎的实现细节