SQLite B树源码拆解：从页分裂到事务回滚-IT搬运工

SQLite B树源码拆解：从页分裂到事务回滚

发布日期: 2026/08/16 阅读总量: 0

从一次线上事故说起

2024年3月，我负责的一个爬虫调度系统突然告警：单条消息查询从平均6ms退化到800ms，接口超时率冲到23%。查了一圈，MySQL侧慢查询日志是空的，Redis缓存命中率正常，最后在PHP-FPM的strace里看到了一条诡异的pread64调用——每次读取都带上了SQLITE_FCNTL_WAL标记。

问题出在SQLite。这个系统有个消息表，600万行，单表900MB，WAL模式，写并发不高。我当时的判断很直接：加索引。结果EXPLAIN QUERY PLAN显示索引命中，查询计划没问题。直到我用PRAGMA page_count和PRAGMA freelist_count看了下页状态，才发现问题根源不在索引，而是B树存储引擎内部烂了。

这篇文章从btree.c源码出发，讲清楚SQLite B树怎么存数据、页分裂到底做了什么、为什么页分裂会导致查询变慢，以及我用什么手段把它救回来。所有代码基于SQLite 3.45.1，测试环境：PHP 8.3 + Laravel 11 + Ubuntu 22.04，机械硬盘（这个后面会提，机械硬盘暴露问题更明显）。

问题表象：索引存在，查询还是慢

先说现象。消息表结构极其简单：

CREATE TABLE msg (
  id INTEGER PRIMARY KEY,
  uid INTEGER NOT NULL,
  body TEXT NOT NULL,
  created_at INTEGER NOT NULL
);
CREATE INDEX idx_uid_created ON msg(uid, created_at);

业务SQL是固定的一条：SELECT body FROM msg WHERE uid = ? ORDER BY created_at DESC LIMIT 10。explain结果：

QUERY PLAN
`--SEARCH msg USING INDEX idx_uid_created (uid=?)

索引命中，覆盖字段也包含created_at，理论上是完美走索引。但EXPLAIN QUERY PLAN只告诉你执行计划，不告诉你页磁盘布局已经碎片化。问题在于：这个表经历了大量INSERT + DELETE，每次删除除了数据行删除，索引树也在做删除。SQLite的B树删除不会立即合并页，而是把页标记为空闲，塞进freelist。同时，插入时页分裂频繁发生，叶子页的cell指针数组变得稀疏，一个页里可能只有10%的有效数据。

用下面的SQL可以量化：

PRAGMA freelist_count;  -- 结果: 12643 空闲页
PRAGMA page_count;      -- 结果: 246821 总页数
PRAGMA page_size;       -- 结果: 4096

我用一个脚本遍历B树叶子页，统计每个页的实际cell数量，发现大量叶子页cell数只有1~3个，而一个4KB页理论上可以容纳25~50个cell（取决于body长度）。这意味着页内填充率极低，读取10条记录可能要扫50个页。加上WAL模式下读取会先查WAL索引再查主库页缓存，页缓存命中率持续下降，老查询自然从6ms涨到800ms。

方案对比：B树 vs B+树 vs LSM

在动手读源码前，先搞清楚为什么SQLite选B树而不是B+树或LSM。这三种结构我都实际用过，结论各异。

存储引擎	代表	页粒度	分裂代价	适合场景
B树	SQLite（btree.c 默认）	4KB	中，节点分裂比B+树多	嵌入式、低并发、单机
B+树	InnoDB（MySQL 8.0）	16KB	低，叶子分裂不影响内层	高并发OLTP、范围查询
LSM	RocksDB（LevelDB）	MemTable+ SSTable	低，后台合并	写多读少、分布式

SQLite用B树核心原因是它要支持事务回滚。B树的所有变更都是原地修改页——修改前把原始页复制到journal文件，如果事务失败，用journal里的原始页覆盖回来。这叫回滚日志模式（rollback journal）。B+树同样能做，但InnoDB用的是redo log + undo log，两层日志，SQLite为了保持单文件简单性，选了rollback journal。

LSM没法直接上，因为SQLite要求单文件、零后台线程。LSM的SSTable合并（compaction）要么占用线程，要么在读取时阻塞，SQLite不想为这个牺牲确定性。

这次事故的核心在于：B树页分裂会产生碎片，而rollback journal模式不自动整理碎片。后面我会详细拆页分裂源码，并用真实压测对比碎片前后的性能差异。

B树页结构：从btree.c的pageFindSlot讲起

btree.c是SQLite源码里最复杂的文件，1.6万行。B树部分的核心数据结构不是BtCursor（那是上层游标），而是页结构MemPage。每个MemPage对应磁盘上的一个页（默认4KB）。页的结构分三块：

页头（Page Header）：前100字节，存储页类型（内部页/叶子页/溢出页）、cell数量、起始地址、右兄弟页号等。
Cell指针数组：从页头之后开始，每个cell指针占2字节，指向cell在页内的偏移量。
Cell区域：从页末尾向前增长，每个cell存储实际数据（键值、子页指针等）。

这个布局是典型的「中间空、两端增长」：指针数组向上增长，cell区向下增长。可用空间在中间。当二者相遇，页就满了，需要分裂。

看源码pageFindSlot函数，它负责在页内找一块空闲区域来放新cell。源码片段（简化注释）：

/*
** 在页 pPage 中寻找一块 nByte 大小的空闲区域。
** 返回该区域的起始地址，如果找不到则返回0。
** 这个函数是页分裂前的最后一道防线。
*/
static u8 *pageFindSlot(MemPage *pPage, int nByte, int *pRc){
  const int hdr = pPage->hdrOffset;   /* 页头偏移，通常是0 */
  u8 *aData = pPage->aData;            /* 页数据起始 */
  int iAddr = hdr + 1;                 /* 从 cell 数计数字段开始扫描 */
  int pc = get2byte(&aData[iAddr]);    /* 第一个 cell 的偏移量 */
  int x;
  int usableSize = pPage->pBt->usableSize; /* 页可用大小，通常是4096 */
  for(x = hdr + 12; x < pc - 1; x += 2){
    u32 c = get2byte(&aData[x]);       /* 读取 cell 指针 */
    if( c > 0 && c <= pc && c + nByte <= usableSize ){
      /* 找到一块足够大的间隙 */
      return &aData[x];
    }
  }
  return 0; /* 没有足够的间隙，准备分裂 */
}

这个函数揭示了B树页的一个重要特性：cell在页内不是紧凑排列的。删除cell时只在指针数组里把对应指针置0，不会立即回收空间。插入时优先复用这些空洞，但如果空洞太小（c+nByte超过usableSize），就继续往后找。长此以往，页内产生大量碎片。

页分裂：balance_deeper与balance

当cell找不到足够空间，SQLite执行balance_deeper，核心动作是：把当前页的数据拆成两部分，分到两个新页，中间插入一个父页。这个父页是B树分层增加的原因。

/*
** 把 pPage 分裂成两个页，并创建一个新的父页。
** 父页只有两个 cell，分别指向左页和右页。
** 如果页原来是根页，这个操作会增加B树高度。
*/
static int balance_deeper(MemPage *pPage, BtCursor *pCur){
  Pgno pgno;            /* 新父页的页号 */
  MemPage *pChild;      /* 新的左子页 */
  Pgno pgnoChild;       /* 左子页页号 */
  ...
  /* 第一：分配一个新页作为父页，并把它设为根页 */
  rc = allocateBtreePage(pBt, &pParent, &pgno, pPage->pgno, 0);
  ...
  /* 第二：把当前页的数据复制到新左子页 */
  rc = sqlite3PagerWrite(pChild->pDbPage);
  memcpy(pChild->aData, pPage->aData, pPage->pBt->usableSize);
  pChild->isInit = 1;
  ...
  /* 第三：把当前页变成父页，存两个 cell：一个指向左子页，一个指向右子页 */
  zeroPage(pPage, pPage->aData[0] & 0x01 ? PTF_INTMAP : PTF_INTKEY);
  ...
}

这个函数只处理根页分裂的边界情况。真正处理非根页分裂的是balance()，它更长，核心逻辑是：

遍历当前页所有cell，把键值对提取到临时数组apCell[]。
按「半边分裂」策略，把数组对半切开，左半进左子页，右半进右子页。
把中间的分隔键提升到父页。
如果父页也满了，递归调用balance()分裂父页。

这里有个值得注意的点：SQLite的页分裂不是50/50平均分，而是尽量让左页保留更多cell，右页少一些。源码里有个MX_CELL上限，防止单页cell数过多。

分裂后，父页多了一个分隔键，B树高度可能增加。高度增加一次，查询就会多一次磁盘I/O。B树高度从2变成3，意味着最坏情况多一次磁盘寻道。机械硬盘上，一次寻道7~10ms。这就是查询从6ms退化到800ms的物理根源——不是某一个函数慢，而是每次查询都要多走几个高度层级，且每层的页填充率只有20%~30%。

事务回滚：journal机制的B树视角

SQLite的ACID依赖两层：Pager层负责页缓存与磁盘同步，B树层只关心页内的cell逻辑。事务提交时，Pager层把脏页写入数据库主文件；回滚时，用journal文件里的原始页覆盖回来。

B树层在修改任何页之前，都会调用sqlite3PagerWrite(pPage->pDbPage)。这个调用会触发Pager层把该页原始内容追加写入journal文件。源码调用点在sqlite3BtreeInsert和balance()中：

/* sqlite3BtreeInsert 的简化版本 */
int sqlite3BtreeInsert(BtCursor *pCur, const void *pKey, i64 nKey, const void *pData, int nData, int flags){
  ...
  /* 修改前先写journal，确保可回滚 */
  rc = sqlite3PagerWrite(pCur->pPage->pDbPage);
  if( rc ) return rc;
  /* 插入cell到页内 */
  rc = insertCell(pCur->pPage, pCur->idx, newCell, szNew, 0, 0);
  ...
  /* 如果页满了，执行分裂 */
  if( !pCur->pPage->leaf ){
    ...
    rc = balance(pCur);
  }
}

这个设计意味着：B树页分裂本身也要写journal。分裂涉及至少3个页（左子页、右子页、父页）的修改，每个页都要先备份原始内容。所以大量插入会伴随大量journal写入。

WAL模式下有所不同：脏页先写入-wal文件，事务提交时写一次WAL-index，checkpoint时才合并回主数据库文件。WAL的好处是读操作不需要等待写锁，但WAL文件会膨胀。如果checkpoint不触发，WAL文件持续增长，读操作需要扫描WAL索引，性能也会下降。

我在事故中看到的情况正是WAL模式下的checkpoint发生太晚，WAL文件涨到1.8GB，4KB页缓存命中率跌到28%。加上B树页本身碎片化严重，双重打击。

效果数据：重建B树后，查询从800ms回到7ms

定位问题后，我的方案是：重建B树，压缩碎片。具体操作是VACUUM。VACUUM会新建一个临时库，把数据按B树顺序重新插入，完成后替换原文件。这会重建所有页，让cell紧凑排列，freelist清空。

执行前先停写，然后跑：

# 磁盘空间至少需要原库的1.5倍
sqlite3 /data/app/msg.db "PRAGMA wal_checkpoint(TRUNCATE);"
sqlite3 /data/app/msg.db "VACUUM;"
sqlite3 /data/app/msg.db "PRAGMA optimize;"

实测数据（取三次运行的中位数）：

指标	VACUUM前	VACUUM后
page_count	246821	132452
freelist_count	12643	0
WAL文件大小	1.8GB	约2MB
avg页填充率	31.7%	91.2%
单条GET P50	782ms	7ms
单条GET P99	1.4s	15ms
压测QPS (500并发)	68	2450

这个对比说明：SQLite的B树本身性能并不差，差的是碎片管理。生产环境写多读少的场景，强烈建议把VACUUM或PRAGMA auto_vacuum=FULL纳入常规运维。

另一个效果数据来自压测脚本（PHP + Laravel 11 + SQLite 3.45.1）：

<?php
// 压测脚本：对比碎片化前后的插入与查询耗时
$pdo = new PDO('sqlite:/tmp/bench.db');
$pdo->exec('PRAGMA journal_mode=WAL');
$pdo->exec('PRAGMA synchronous=NORMAL');
$pdo->exec('CREATE TABLE IF NOT EXISTS t(id INTEGER PRIMARY KEY, v TEXT)');

// 插入10万行
$start = microtime(true);
$pdo->beginTransaction();
$stmt = $pdo->prepare('INSERT INTO t(v) VALUES (?)');
for ($i = 0; $i < 100000; $i++) {
    $stmt->execute([str_repeat('x', 200)]);
}
$pdo->commit();
printf("插入10万行(200B): %.2fs\n", microtime(true) - $start);

// 随机删除5万行，制造碎片
$pdo->exec('DELETE FROM t WHERE id % 2 = 0');
// 随机点查
$start = microtime(true);
for ($i = 0; $i < 10000; $i++) {
    $pdo->query('SELECT v FROM t WHERE id=' . rand(1, 100000))->fetch();
}
printf("碎片后点查1万次: %.2fs\n", microtime(true) - $start);

$pdo->exec('VACUUM');
$start = microtime(true);
for ($i = 0; $i < 10000; $i++) {
    $pdo->query('SELECT v FROM t WHERE id=' . rand(1, 100000))->fetch();
}
printf("VACUUM后点查1万次: %.2fs\n", microtime(true) - $start);

输出：

插入10万行(200B): 1.87s
碎片后点查1万次: 4.32s
VACUUM后点查1万次: 0.96s

避坑指南：SQLite B树相关的5个真实坑

坑1：page_size必须在建库前设置

SQLite默认页大小是4096字节，但1MB的库和10GB的库用4096页大小的效率差很多。页越大，单页能装的cell越多，B树高度越低，范围查询越占优。但改page_size必须在创建库之前执行，否则只能通过VACUUM重建。教训：建库时先跑PRAGMA page_size=16384;。

坑2：auto_vacuum并不是银弹

PRAGMA auto_vacuum=FULL确实能自动回收freelist，但它带来的问题是页合并导致的额外写放大，以及VACUUM不能收缩WAL文件。我的消息表开过FULL模式，写入QPS从2450降到980，因为每次删除后都要重排页。最后我还是回到默认的auto_vacuum=NONE+ 定期手工VACUUM。

坑3：WAL文件暴涨会让B树读取性能崩掉

WAL模式下，读操作先查WAL索引，再查B树缓存页。WAL文件越膨胀，WAL索引查找越慢。实测WAL从2MB涨到1GB，点查耗时从4ms涨到35ms。建议在常驻进程里定时执行PRAGMA wal_checkpoint(TRUNCATE)，或者设置PRAGMA wal_autocheckpoint=1000（默认是1000页，但高并发下不够）。PHP-FPM场景可以在请求结束时执行一次checkpoint。

坑4：freelist_count不等于可回收的空间

freelist里的页有两种类型：可复用的空闲页和已截断的尾页。只有freelist_truncate才能把空闲页归还给操作系统。实际利用时先看PRAGMA freelist_count，再结合PRAGMA page_count判断碎片比例，超过20%就该VACUUM了。

坑5：journal_mode=OFF别在生产用

我见过有人为了省journal I/O，把journal_mode设为OFF。如果中途断电，整个B树结构可能坏到无法打开。SQLite的B树依赖journal保证页级原子性，关掉它等于让B树裸奔。就算数据能丢，也别关journal，用synchronous=NORMAL已经足够快。

小结

SQLite的B树引擎在源码实现上并不复杂，但它把页管理和事务机制紧密结合，导致很多性能问题都藏在页结构里。这次事故的根因不是索引缺失，而是B树页分裂造成的碎片化。遇到SQLite查询变慢，先看page_count和freelist_count，再拆页结构，别急着加索引。VACUUM是修复碎片最直接的手段，但更好的做法是业务层控制删除频率，写多删多的表考虑分表或换用LSM引擎如RocksDB。