实现 B-Tree

一句话

你以为这一章讲的是「分裂与合并算法」，其实那两行伪代码是全章最容易的部分。真正的工程量全在分裂之外：怎么找到父节点（答案是面包屑，不是父指针）、怎么少分裂（先向兄弟借）、顺序键怎么别浪费掉一半空间（右倾分裂）、删完的洞怎么收回来（vacuum）。这一章是把第 2 章的树形状、第 3 章的页字节，缝成一个能在生产里连跑十年而不崩不胖的实现——它是「教科书 B-Tree」和「PostgreSQL / InnoDB 里那棵 B-Tree」之间的全部差距。

Glossary · 术语表

坐标

本章是《Database Internals》Part I「存储引擎」的第 4 章，也是 Part I 里工程味最重的一章。上承第 2、3 章——第 2 章论证了 B-Tree 为什么是磁盘上的默认答案（高扇出把树压矮），第 3 章给出了一页的字节布局（槽式页、cell、空闲清单）；下启第 5 章「事务处理与恢复」，本章里每一次分裂、合并、页内压缩，到了第 5 章都得配上 WAL 才敢在崩溃面前声称正确。对应现实：PostgreSQL 的 nbtree 模块、InnoDB 的聚簇索引、SQLite 的 btree.c——本章讲的每个机制，在这三份代码里都找得到对应的实现和它们各自的取舍。

这章要解决什么

把教科书那版 B-Tree 直接搬进生产，你会连撞四堵墙。

第一堵：分裂要往上传播，而节点不知道自己的父亲是谁。叶子满了拆成两半，父节点必须多收一个分隔键；父可能也满，继续往上，最坏一路顶到根——根一分裂，树就长高一层。可页里存的只有键和子指针，没有指回父亲的路。天真的补救是存一个父指针，代价却立刻现形：节点一分裂，它名下所有子节点的父指针都要改一遍——扇出 500 的节点分裂就是 500 次额外页更新，还全得写进 WAL。

第二堵：对半分裂让你白买一半的硬件。满了就 50/50 劈开，两个新页各半满，随机插入下稳态填充率长年在 50%–70% 徘徊。给个量级：1 亿行的订单表，主键索引每条 16 字节、8 KiB 页扇出约 500，填满约 2 GB，稳态半满就是 4 GB。多出的 2 GB 不只占硬盘，它等量地挤占页缓存——本来全放得进内存的索引现在放不下，命中率一掉，延迟就抬头。

第三堵：顺序键把这笔浪费变成纯亏。主键是自增 ID 或时间戳时，每一条插入都砸在最右边那片叶子上。此时对半分裂尤其蠢：劈出来的左半页再也不会有任何新键落进去，永久半空。填充率被死死钉在 50%——而它本可以接近 100%。

第四堵：删除和更新留下的洞不会自己消失。删一条只是标记 + 挂空闲清单（第 3 章）；变长字段被 UPDATE 改长了原地放不下，就得挪走、原位留洞。洞攒够了，一页有效载荷可能只剩三成，却照样占着 8 KiB 磁盘、8 KiB 缓存，每次读还是整页搬。

表 1 · 教科书讲的 B-Tree vs 生产实现必须补的东西

核心内容，讲透

一、节点自报家门：页头、最右指针与高键

B-Tree 节点的页头除了第 3 章讲过的那些（魔数、cell 数、空闲空间边界），还得记这一页在树里的身份：叶子还是内部节点。这决定了 cell 按哪种格式解读——叶子里是「键 + 值」，内部节点里是「分隔键 + 子页 ID」。

然后是一个容易被跳过、却逼出两种流派的细节：内部节点有 N 个分隔键，却有 N+1 个子指针。把「键 + 指针」打包成 cell，最后那个指针就配不到键——它管的是「比所有分隔键都大」的那一片。两条出路：

• 最右指针（rightmost pointer）：把这个落单的指针单独塞进页头。简单直接，SQLite 就是这么干的。
• 高键（high key）：给这一页规定一个上界——「本页及其子树的键都不超过它」——最后那个指针于是也有键可配。更重要的是，高键顺手解决了并发下的大麻烦：读者读到一页，发现要找的键比这页的高键还大，立刻就知道「这页在我来的路上刚分裂过」，顺兄弟指针往右挪一步即可，全程不用加读锁。这正是 Lehman & Yao 1981 年那篇 Blink-tree 论文的核心招式，PostgreSQL 的 nbtree 直接实现了它。

兄弟指针（sibling links）是页头里的另一件事：同层相邻页互指。好处很实在——范围扫描（WHERE id BETWEEN 1000 AND 9000）沿叶子链横扫即可，不必每读完一页就爬回父节点。代价同样实在：每次分裂、合并、页删除都要额外维护左右邻居，而这几个页在并发下属于不同的 latch，顺序稍有不慎就是死锁。

二、页内二分查找：在偏移量数组上二分，返回的是「插入点」

找到一页之后还要在页里定位。第 3 章说过，槽式页里 cell 物理上乱放，但槽目录（偏移量数组）按键有序——所以二分是在这个小而连续的偏移量数组上做的：取中间的槽，顺偏移量跳过去读键，比大小，缩小区间。一页 8 KiB 装 500 个键，log₂500 ≈ 9 步到底，全程只碰这一页，不产生任何额外 I/O。

一个小设计值得点名：没找到时不能只返回「没找到」。插入要知道插在哪儿，范围扫描要知道从哪儿开始扫。所以实现普遍让二分返回插入点，并用负数编码（如 -(插入点) - 1）把两种结果塞进一个返回值：正数是命中下标，负数一变换就是插入位置。同一次二分，三种调用者都用得上。

三、分裂向上传播与面包屑：为什么不存父指针

这是全章第一个真正的工程决断。叶子分裂后父节点要收下新的分隔键；父可能也满，继续往上；一路顶到根，根分裂，树长高一层——这是 B-Tree 唯一会长高的时刻，所以它天然保持完美平衡。问题只有一个：怎么找到父节点？

直觉方案是给每个节点存父指针，Petrov 直接否掉了它：写放大——分裂时被搬进新节点那一半的子节点父指针全部作废，扇出 500 的节点分裂就是数百次额外页更新 + 数百条 WAL 记录；并发不一致——父指针散落在几百个页里，没法和分裂本身放进同一个原子操作。

真实答案是面包屑（breadcrumbs）：查找本来就是从根往下走的，那就在下行时把「经过哪一页、走的哪个槽」一路压进栈；需要往上传播时，弹栈就是父节点。妙处在于这份信息本来就白拿——你为了找到叶子，无论如何都得走这一趟。

还有一个必须处理的细节：面包屑可能过期。并发下你走到叶子的这段时间里，栈里记的父节点自己可能已经分裂，你的分隔键不再归它管。这时高键与兄弟指针第二次救场：把栈里的页读回来，发现键超过了它的高键，就沿兄弟指针右移一步再试——不必重新从根走一遍，也不必全程握着锁。

四、少分裂：先向兄弟借地方

第二个工程决断针对填充率。既然分裂又贵（写三个页 + WAL）又浪费空间（两个半满页），那就能不分就不分：节点满了先看左右兄弟，哪边有空位就把边界上的几个键挪过去，顺手更新父节点里那个分隔键——这叫再平衡（rebalancing）。

这就是 B*-tree 的思路：只有自己和兄弟都满了，才把 2 个节点拆成 3 个。算笔账：普通 B-Tree 分裂后每个节点保证至少半满，最低填充率 50%；2 拆 3 让每个节点至少装到 2/3，最低填充率提到约 66%。同样的数据，索引体积小掉四分之一，页缓存里也就多装四分之一。

代价一点不含糊：一次操作要同时改两三个页（自己、兄弟、父），并发下就是同时握两三个 latch——加锁顺序必须全局一致，否则死锁；写放大也从「改一页」变成「改三页」。这是一笔拿写路径复杂度和延迟尖刺换空间与缓存命中率的交易，不是所有引擎都愿意做。反向的合并同理：听着漂亮，但同样要动多个页，还容易和分裂来回拉锯（刚合完又满了、又分开）——这正是 PostgreSQL 干脆放弃合并半空页的原因。

五、右侧追加与批量加载：顺序键值得单开一条路

这一节最贴近日常。你的主键多半是自增 ID、时间戳或雪花 ID——它们都单调递增，于是每一条插入都砸在最右边那片叶子上。对这种负载，通用逻辑处处吃亏，值得单开快车道。

快车道一：右倾分裂。最右叶子满了别劈中间，把绝大部分键留在原页，只把最后一小撮挪进新页。理由很硬：左半页此后不可能再收到任何键（新键只会更大），对半劈就是把一半空间永久锁死。InnoDB 的实际填充率印证了这笔账——顺序插入与随机插入的差距近乎一倍，官方数字见下方实证框。

快车道二：缓存最右叶子。既然插入总落在同一页，就别每次从根走一趟。PostgreSQL 的 nbtree 缓存了上次插入命中的叶子，若它仍是最右叶、还有空位、且新键比页里首键大，就直接插进去，这条路径叫 fastpath。它自带一个刹车：所有写线程都去抢同一页的排他锁，反而会争用——所以拿不到锁就退回常规路径。

快车道三：批量加载。数据本来就有序时（导入、重建索引、LSM 的合并输出），逐条插入是纯浪费。正确做法是自底向上建树：把有序数据一页页码满写成叶子层，再取每片叶子的首键组成上一层，逐层往上直到只剩一个根。全程零分裂零查找，页可填到接近 100%，且是纯顺序写盘。MySQL 把它叫 sorted index build，创建或重建索引时默认走这条路。这也解释了那条经典建议：往空表灌数据，先灌数据、最后建索引。

六、压缩：粒度是唯一的问题

压缩能省磁盘、省 I/O，代价是每次读都要解压。Petrov 把选择压平成一个问题：粒度多大？

• 整个文件：压缩率最高，但没法定位单个页——B-Tree 靠「第 n 页在哪 = n × 页大小」寻址，一压全文件这条前提就没了。基本出局。
• 按页：主流折中。页仍可寻址，读一个 cell 要先解压整页——反正本来就得整页读。麻烦在压缩后长度不定，得额外记录每页压完占多少、放在哪。
• 按 cell / 行：粒度最细、解压最省，但压缩率最差——可参考的上下文太短，几十字节里榨不出多少冗余。

还有一条不改布局的省法：去重。PostgreSQL 13 起的 B-Tree deduplication 就是典型——一个键值重复很多次时（比如给低基数的 status 列建索引），把它们合并成一条「键 + 一串行指针」的 posting list，键只存一次，既省体积又顺带推迟叶子页分裂。

七、碎片、vacuum 与页的回收

最后是维护。两个来源持续制造死空间：删除（标记 + 挂空闲清单，第 3 章）与更新（变长值改长了原地放不下，只能挪走、原位留洞）。结果是页里有效载荷越来越低，页数却一个不少——磁盘、页缓存、每次整页读，成本一分不减。对策分两层：页内把存活 cell 重新紧密码到一起（代价是整页重写），页间把完全空掉的页摘下来放进全局空闲页清单供分裂复用——注意后者通常不缩小文件，只是让空间可复用。

这里有一个必须知道的现实差异。PostgreSQL 只回收「完全变空」的页——只剩几个键的页继续占着，于是「一个区间里绝大多数键最终被删掉」这种模式会长期浪费空间。InnoDB 走另一条路：填充率跌破 MERGE_THRESHOLD 就跟邻页合并，代价是两页都在阈值附近时「合了又分」地抖动。同一个问题，两种权衡，两家都在官方文档里诚实写下了自己的代价（原文见下方实证框）。

关键权衡与选型

表 2 · 怎么找到父节点

表 3 · 节点满了怎么办：四种分裂策略

表 4 · 留白与回收：各家的真实默认值

为什么重要 / 落到真实系统

选主键时说得出理由。「UUID v4 当主键为什么慢」不是玄学：随机键让插入均匀砸向每一片叶子，每片都得读进页缓存、改脏、写回，分裂遍地开花；换成时间有序的 ID（自增、UUID v7、雪花 ID），插入集中在最右一页，走右倾分裂与 fastpath——索引体积近乎减半，页缓存里放得下的索引近乎翻倍。这条结论有官方文档背书，不是传闻。

导数据时选得对路。往空表灌一亿行：边灌边维护 5 个索引，等于一亿次「走根到叶 + 可能分裂 + 写 WAL」；先灌数据、最后 CREATE INDEX，走的是排序 + 自底向上批量建树，纯顺序 I/O、零分裂、页填到接近满。

排障时找得到方向。「表只有 3 GB，索引却 12 GB，VACUUM 之后一点没小」——多半就是第七节那件事，要真收回来得 REINDEX。反过来，InnoDB 上写延迟周期性抖动，就该想到 MERGE_THRESHOLD 附近的合并—分裂拉锯。

易错点与争议

• 以为「B-Tree 保证至少半满」是好消息。它是下界保证，不是目标值——真实负载下稳态填充率常年在 50%–70%，意味着你为索引买的硬盘和内存有三分之一到一半在装空气。本章大半篇幅（再平衡、右倾分裂、批量加载、去重）都在跟这个数字较劲。
• 以为分裂是罕见事件。随机键 + 高写入下，分裂是常态。一次叶子分裂至少改 3 个页（原叶、新叶、父）并写进 WAL；PostgreSQL 在 checkpoint 后首次改动一页时还要写整页镜像。逻辑上「插一行」，落到磁盘上可以是几十 KiB。
• 把父指针当理所当然。内存里的树几乎都存父指针，磁盘上的 B-Tree 几乎都不存。差别只在一处：内存里改一个指针是几纳秒，磁盘上改一页要走 WAL、进页缓存、最终落盘。同一个数据结构换个介质，最优实现就完全不同。
• 以为删除会让索引变小。不会。页内空间挂进空闲清单等待复用，页级回收也只是把空页还给全局清单，文件大小往往一动不动。真要缩得 REINDEX / VACUUM FULL，代价是重建。
• 把 fillfactor 一律调到 100。诱惑很大（索引最小、缓存命中最高），但静态表之外这么做等于把所有留白都退掉，之后每一次中间插入都可能立刻触发分裂。PostgreSQL 把默认定在 90 而非 100，正是这个道理。
• 时代局限与争议。本章整套算计建立在「块设备 + 原地更新 + 改页要写 WAL」之上，三个方向正在动摇它：LSM-tree（第 7 章）放弃原地更新，把分裂 / 碎片换成后台合并问题；Bw-tree 等无锁变体（第 6 章）用增量记录 + 映射表绕开页内原地修改，本章的 latch 与分裂传播全得重写；NVMe / 持久内存让「随机 I/O 昂贵」这条公理松动，扇出、页大小、分裂策略的最优点都会跟着漂移。而 PostgreSQL 拒绝合并半空页，是为并发正确性与实现简单付出的空间代价，社区争论多年至今未改；InnoDB 选了另一边，也如实写下了抖动代价。没有对错，只有两张不同的账单。

要点