【SQLite 内核】B-Tree 遍历与分裂：表 B-Tree、索引 B-Tree 与 cell 布局

Pager 与 Page Cache 已经能把页从磁盘搬进内存、按脏页契约安全落盘。但页本身只是一段字节数组，真正决定 SELECT ... WHERE id=? 能否在对数次页访问内命中目标行的，是页内如何组织 key、插入一条记录时要不要搬移已有内容，以及页写满之后如何长高——这一层是 btree.c 实现的 B-Tree 模块。

一个常见误解是把 SQLite 的「B-Tree」直接等同教科书 B-Tree。官方 File Format For SQLite Databases 明确区分两种变体：table b-tree 用 64 位有符号整数 key，数据只放在叶子；index b-tree 用任意长度 key，不存数据。前者的「数据只在叶子」特征，实质上更接近 B+Tree，而不是 Bayer & McCreight 原始论文里数据可以出现在任意层的经典 B-Tree。本文只钉三件事：

1. table b-tree 与 index b-tree 的字节布局差异，以及 WITHOUT ROWID 表如何借用 index b-tree。
2. cell pointer array 如何让「逻辑有序」与「物理位置」解耦，插入时不搬移已有 cell 内容；overflow 阈值如何保证最小 fanout。
3. 查找路径与 balance() 触发分裂/合并的真实条件，用 btree.c 的函数名而不是编出来的行号钉证据。

本文是「SQLite 内核」系列第 4 篇（共 17 篇）。→ 系列目录

篇目	核心内容
第 3 篇 · Pager 与 Page Cache	读改写契约、脏页与缓存边界
第 4 篇 · B-Tree 遍历与分裂	table/index b-tree、cell 布局、overflow、分裂平衡
第 5 篇 · VDBE 字节码执行	sqlite3_step 执行循环与寄存器

版本锚定：官方 File Format For SQLite Databases（sqlite.org，第 1.6–1.7 节 B-tree Pages / Cell Payload Overflow Pages）。源码函数签名以 btree.c 为准：sqlite3BtreeTableMoveto、sqlite3BtreeIndexMoveto、balance、balance_nonroot、balance_deeper、balance_quick；这一组签名自 SQLite 3.36.0（2021-06-19 check-in 3b0d34e5e5，将此前的单一函数 sqlite3BtreeMovetoUnpacked 拆分为两个）起稳定，覆盖本系列锚定的 3.45.x–3.46.x 及本机实测的 3.53.2。奠基论文：Bayer, R. & McCreight, E. Organization and Maintenance of Large Ordered Indexes, Acta Informatica, 1972；背景教材：Knuth, The Art of Computer Programming, Vol. 3，第 471–479 页（file format 文档自身的参考）。本文不展开 FTS5 / R*Tree 等扩展模块的自定义 B-Tree 变体。

一、两种 B-Tree：table b-tree 与 index b-tree

官方 file format 文档第 1.6 节把两种变体的差异写得很直接：

“Table b-trees” use a 64-bit signed integer key and store all data in the leaves. “Index b-trees” use arbitrary keys and store no data at all.

1.1 Table b-tree：key 是 rowid，数据只在叶子

每个 rowid 表在文件里对应一棵 table b-tree。叶子 cell 的结构是「varint payload 长度 + varint rowid + payload 前缀 + 可选 overflow 指针」；内部节点的 cell 只有「4 字节子页指针 + varint rowid」，不带任何 payload——因为表的实际列值只出现在叶子。sqlite_schema（曾用名 sqlite_master）本身也是一棵 table b-tree，根页固定为页 1。

INTEGER PRIMARY KEY 列是 rowid 的别名：这一列在记录里以 NULL 序列类型存储，SQLite 引用该列时直接用 b-tree key（也就是 rowid），不会去解码记录里的 NULL 值。

1.2 Index b-tree：key 任意，没有单独的数据区

每个 CREATE INDEX（含 UNIQUE / PRIMARY KEY 隐式生成的索引）对应一棵 index b-tree。索引项的 key 由「被索引列 + 表行 key」拼成一条 record：对普通 rowid 表，后缀是 rowid；对 WITHOUT ROWID 表，后缀是主键列。因为一行在表里唯一，索引里的 key 天然唯一。

WITHOUT ROWID 表没有独立的 table b-tree：它整表就是一棵 index b-tree，key = PRIMARY KEY 列（按声明顺序）+ 剩余列，没有 rowid，也没有另一份「数据 b-tree」。这是本节最容易被误解的一点——很多人以为 WITHOUT ROWID 只是「省了一个隐藏列」，实际上它换了存储范式：从 table b-tree 切到 index b-tree。

flowchart TB
  subgraph tbt ["Table b-tree (rowid tables)"]
    TI["Interior cell:<br/>child pointer + rowid<br/>no payload"]
    TL["Leaf cell:<br/>rowid + full row payload"]
    TI --> TL
  end
  subgraph ibt ["Index b-tree (indexes, WITHOUT ROWID tables)"]
    II["Interior cell:<br/>child pointer + key payload"]
    IL["Leaf cell:<br/>key payload only<br/>(indexed cols + row key suffix)<br/>no separate data"]
    II --> IL
  end

1.3 一句历史回链

FoundationDB 早期 SSD storage engine 是「modified version of SQLite」（SIGMOD 2021 §2.3.2）：它拿走了 SQLite 的 B-Tree 页与索引查找逻辑，剥掉了 SQL 解析、查询计划与语句级事务 API，磁盘上留下的是未版本化的纯页式索引结构——细节见 foundationdb/12 Redwood。这是分布式 KV 对页式引擎的取用史，不是本篇要重写的内容。

二、页内布局：cell pointer array 与 cell 内容区

一个 b-tree 页从头到尾分六段：100 字节数据库头（仅页 1）→ 8 或 12 字节页头 → cell pointer array → 未分配空间 → cell content area → 保留区。页头的关键字段：

2.1 逻辑有序、物理可乱序

cell pointer array 紧跟页头，是 K 个 2 字节偏移量，按 key 顺序排列（最小 key 在前）。但文档明确写道：

All keys within the same page are logically organized in ascending order from left to right. (Again, this ordering is logical, not physical. The actual location of keys within the page is arbitrary.)

也就是说：真正决定”谁在前谁在后”的是 pointer array 里 2 字节偏移的排列顺序，而不是 cell 字节在页内的物理位置。SQLite 把新 cell 尽量塞进 content area 靠页尾的空闲字节，只需要在 pointer array 里插入一个新偏移（并把该位置之后的偏移整体挪动几个字节）——已经写好的 cell 内容不需要搬移。这正是”cell content 只增量分配、内部整理靠 freeblock/defragment 而不是逐条搬移”的关键：

flowchart TB
  A["Before insert:<br/>K cells, pointer array sorted by key"] --> B["Allocate new cell bytes<br/>from the tail of free space<br/>(existing cell bytes untouched)"]
  B --> C["Insert one 2-byte offset<br/>into the pointer array<br/>at the sorted position"]
  C --> D["After insert:<br/>K+1 cells,<br/>only the pointer array shifted"]

代价是页会逐渐产生 freeblock（被删除 cell 留下的空洞）与碎片字节；SQLite 需要时会整页 defragment，把所有 cell 重新紧靠页尾排列，清空 freeblock 链——但这是显式的整理操作，不是每次插入都做。

页内 cell 的具体字段布局见站内既有图 （数据库头、页头、pointer array、cell content area 的相对位置）。

2.2 四种 cell 格式

table b-tree 的 interior cell 没有 payload 列——这就是为什么”表 b-tree 内部节点从不溢出”：没有 payload，就没有可溢出的东西。

三、Overflow：payload 何时溢出到额外页

设 (U) 为页的可用大小（usable size，页大小减保留字节），(P) 为 cell 的 payload 字节数。file format 文档给出两组阈值：

Table b-tree 叶子 cell：

\[X = U - 35\]

若 (P X)，payload 全部内嵌；否则计算

\[M = \left\lfloor \frac{(U-12) \times 32}{255} \right\rfloor - 23, \qquad K = M + \big((P-M) \bmod (U-4)\big)\]

若 (K X)，内嵌 (K) 字节，剩余溢出；否则只内嵌 (M) 字节，剩余全部溢出。

Index b-tree（叶子与内部）cell：(X) 换成

\[X = \left\lfloor \frac{(U-12) \times 64}{255} \right\rfloor - 23\]

(M)、(K) 的定义与上面相同。

这组看起来繁琐的公式服务一个明确目标，文档原话：

The overflow thresholds are designed to give a minimum fanout of 4 for index b-trees.

即：无论 key 多长，index b-tree 内部页至少能塞下 4 个 key（对应至少 4 个子指针），避免树因为个别超长 key 退化成近似链表。table b-tree 的整数 key 不会长到需要溢出，所以这条约束只对 index b-tree 的 key 生效；table b-tree 叶子的 payload（行内容）仍可能溢出，但走的是上面第一组阈值。

溢出内容存放在独立的 overflow page 链上：每页前 4 字节是下一个 overflow page 的页号（0 表示链尾），剩余字节存内容。overflow 链本身没有索引结构，只能顺序读——这是”大 BLOB/TEXT 列会拖慢范围扫描”的字节级原因：命中一条溢出记录后，还要多几次页 I/O 才能拿到完整 payload。

四、查找路径：从根页二分到叶子

以官方 Architecture of SQLite 的定位：「An SQLite database is maintained on disk using a B-tree implementation found in the btree.c source file. Separate B-trees are used for each table and each index in the database.」查找的骨架是标准的自顶向下 B-Tree 检索：

1. 从根页开始，在当前页的 cell pointer array 上做二分查找，用目标 key 与每个 cell 的 key 比较。
2. 如果是 interior 页，二分结果决定走哪个子指针，读取对应子页，重复第 1 步。
3. 到达 leaf 页后，在该页的 cell pointer array 上再做一次二分，命中则返回该行（table b-tree）或该索引项（index b-tree）；未命中则返回”应该插入的位置”。

table b-tree 的 key 是 64 位整数，比较是简单整数比较；index b-tree 的 key 是任意长度 record，比较要按列、按 collation 逐列展开（memcmp 或 NOCASE/RTRIM 等内建 collation）。这个差异反映在源码接口上：btree.h 声明了两个独立入口，sqlite3BtreeTableMoveto(BtCursor*, i64 intKey, int bias, int *pRes) 处理整数 key 的表查找，sqlite3BtreeIndexMoveto(BtCursor*, UnpackedRecord *pUnKey, int *pRes) 处理任意 key 的索引查找。

这组接口本身有一段可核对的历史：在 SQLite 3.36.0 之前，两种查找共用一个函数 sqlite3BtreeMovetoUnpacked()；2021-06-19 的 check-in 3b0d34e5e5（作者 drh）把它拆成上述两个函数，提交说明是「since we usually know the type of btree in advance. This results in less branching and better performance」——一次纯粹为减少分支预测开销做的工程重构，不改变查找语义。这也是本文不采用 PLAN 草稿里旧函数名的原因：旧名字在当前锚定版本（3.45.x 之后）已经不存在，继续引用会与源码事实脱节。

常见误解

1. 「SQLite 的 B-Tree 就是教科书 B-Tree」 Table b-tree 的数据只在叶子，行为上是 B+Tree；index b-tree 完全没有 payload，是纯 key 结构。Bayer & McCreight 原始定义里数据可以出现在任意层，与 SQLite 的两种变体都不完全重合。

2. 「cell 在页里的物理顺序等于 key 的逻辑顺序」 文档原话已经否定：物理位置任意，顺序全靠 cell pointer array 的偏移排列。dump 页的十六进制内容时，不能假设”从前往后就是从小到大”。

3. 「表覆盖率高，插入就不会触发分裂」 balance() 的判断条件只看当前页的 overflow cell 数量与剩余空闲空间比例，与查询计划或索引覆盖率无关；即便是纯 append 的插入模式，只要页写满就会走到 balance_quick/balance_nonroot。

4. 「WITHOUT ROWID 只是省了一个隐藏 rowid 列」 它把整张表从 table b-tree 换成了 index b-tree：没有独立数据区，主键列本身就是 key 的前缀，存储范式变了，不只是少一列。

五、分裂与平衡：页满或页空时如何调整

balance() 是分裂与合并共用的入口，触发条件在源码注释里写得很明确（btree.c，balance() 函数体的判断分支）：

No rebalance required as long as: (1) There are no overflow cells (2) The amount of free space on the page is less than 2/3rds of the total usable space on the page.

反过来说，只要满足下面任一条件就会触发 rebalance：

• 页上有 overflow cell（插入/更新导致页装不下，即将写满）；
• 页上没有 overflow cell，但空闲空间超过可用空间的 2/3（页太空，可能需要与邻居合并）。

也就是说 balance() 是分裂与合并的统一判断点，不是”只在插入时触发”的单向操作。根据具体场景，balance() 会派给三个不同的子过程：

• balance_deeper(MemPage *pRoot, MemPage **ppChild)：当根页本身 overfull，分配一个新子页，把根页当前内容（含 overflow cell）整份拷贝进子页，根页重写成只有一个右指针的空页——这是树”长高一层”的唯一方式，源码注释称为”A new child page is allocated and the contents of the current root page … are copied into the child”。
• balance_nonroot(...)：常规路径，重新分配”当前页 + 最多两侧各一个兄弟页”之间的 cell，让参与balance 的页空闲空间大致相当；源码注释写明兄弟数量会视情况增减一到两个（“The number of siblings of the page might be increased or decreased by one or two”），不是固定的二分裂。
• balance_quick(MemPage *pParent, MemPage *pPage, u8 *pSpace)：批量右端追加（新记录总是当前树里最大的 key）时的快路径，直接给右端加一个新页存放这一条 overflow cell，不去动其它兄弟——源码注释承认这会让树右端”略微不平衡”，但假设后续还会继续追加，很快会被填满。

flowchart TB
  full["Page has overflow cell(s)<br/>or free space > 2/3 usable"] --> check{"Is this page<br/>the root page?"}
  check -->|"yes, root overfull"| deeper["balance_deeper()<br/>push root down,<br/>tree grows one level"]
  check -->|"no"| quick{"Single append at<br/>the extreme right edge?"}
  quick -->|"yes"| bq["balance_quick()<br/>allocate one new<br/>right-hand sibling"]
  quick -->|"no"| nonroot["balance_nonroot()<br/>redistribute cells across<br/>page + up to 2 siblings"]
  deeper --> cont["balance() loop continues<br/>on the (former root) child page"]

这条链路只回答”何时调整、往哪个方向调整”，不回答”分裂之后写放大是多少”——本系列没有跑过针对性 benchmark，PLAN 的实验台账把这一项标注为”待执行”，本文不编造具体数字。

六、学术谱系、工程间隙与开放问题

谱系：Bayer & McCreight（Acta Informatica, 1972）定义了有序索引在页式存储上维持平衡的一般方法，是页式索引这一范式的奠基 work；Knuth 在 TAOCP Vol. 3 第 471–479 页给出了背景描述，SQLite file format 文档本身在 1.6 节直接引用这段作为背景。SQLite 的具体实现（4/8/12 字节页头、cell pointer array、payload fraction 阈值）是工程规范层，不是论文原文的直接映射——例如”最小 fanout 4”是 SQLite 自己选的设计参数，不是 Bayer & McCreight 论文里的结论。

与 O’Neil et al. 的 LSM-Tree（Acta Informatica, 1996）对照：LSM 把随机写变成顺序写、把索引更新推迟到 compaction，代价是读路径要合并多层；页式 B-Tree（本篇的对象）把更新直接做在原地页上，代价是随机写触发的分裂/合并会立即发生。这条分叉在 rocksdb 系列 是主战场，本篇不重复展开，只标出边界：SQLite 站在页式一侧。

工程间隙：论文与 file format 文档描述的是”稳态”下的平衡算法；文档没有承诺具体的写放大倍数，balance_nonroot 的兄弟数量调整策略（增减一到两个）是可读的启发式，不是可证明最优的分裂策略。生产环境里，页大小（PRAGMA page_size）、auto_vacuum 模式、以及是否频繁在中间 key 插入（而非追加）都会显著改变实际触发 balance_nonroot 还是 balance_quick 的比例，但这属于需要专门实验才能下结论的问题，本文按 PLAN 的实验台账标注为未执行，不代入具体数字。

开放问题：SQLite 官方长期坚持”单写者、文件级锁”而不是”页级锁”（详见第 9–10 篇），这直接影响 balance() 期间是否需要额外的并发保护——因为同一时刻只有一个写事务在跑，balance_nonroot 不需要处理并发分裂。如果未来要支持更细粒度的写并发，balance 算法本身要不要重新设计（例如借鉴 B-link Tree 之类允许并发分裂的结构），是社区没有定论的方向；本系列按官方现状写，不预判答案。

七、小结

1. Table b-tree 用 64 位整数 key、数据只在叶子（近似 B+Tree）；index b-tree 用任意 key、不存数据；WITHOUT ROWID 表本质是”整表变成一棵 index b-tree”，不是省一列。
2. Cell pointer array 把”逻辑顺序”和”物理位置”解耦：插入只需要分配新 cell 字节 + 调整 pointer array，已有 cell 内容不搬移；overflow 阈值的设计目标是保证 index b-tree 至少 4 路 fanout。
3. balance() 是分裂与合并的统一判断点（overflow 或空闲超 2/3 都会触发），具体走 balance_deeper（长高）、balance_nonroot（常规重分布）还是 balance_quick（右端追加快路径），由页在树中的位置和插入模式决定；写放大倍数留给专门实验，本文不编数字。

参考资料

规范与官方文档（A 级）

1. SQLite Documentation, File Format For SQLite Databases，第 1.6 节 B-tree Pages、第 1.7 节 Cell Payload Overflow Pages（sqlite.org）。
2. SQLite Documentation, Architecture of SQLite，B-Tree 一节（sqlite.org）。

源码（A 级）

3. sqlite/sqlite 仓库 src/btree.c：balance()、balance_nonroot()、balance_deeper()、balance_quick() 的函数体与注释；src/btree.h：sqlite3BtreeTableMoveto、sqlite3BtreeIndexMoveto 声明。
4. SQLite check-in 3b0d34e5e5（2021-06-19，作者 drh）：拆分 sqlite3BtreeMovetoUnpacked() 为 sqlite3BtreeTableMoveto() / sqlite3BtreeIndexMoveto()。

论文与教材（A 级）

5. Bayer, R. & McCreight, E. Organization and Maintenance of Large Ordered Indexes. Acta Informatica, 1972。
6. Knuth, D. E. The Art of Computer Programming, Volume 3: Sorting and Searching，第 471–479 页。
7. O’Neil, P., Cheng, E., Gawlick, D. & O’Neil, E. The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica, 1996（对照轴）。

站内

8. SQLite 内核系列 index、PLAN.md。
9. Pager 与 Page Cache、VDBE 字节码执行。
10. FoundationDB 内核 · Redwood（SQLite B-Tree 派生历史）、RocksDB 内核（LSM 对照轴）。
11. （页内字段相对位置图，来自站内既有性能单篇）。

上一篇：Pager 与 Page Cache 下一篇：VDBE 字节码执行