6.3 源码阅读：SQLite B 树与存储引擎

SQLite 最为人称道的工程特质之一，便是“单文件承载整个数据库”。不管是庞大的数据表、复杂的二级索引，还是并发事务下的原子回滚与崩溃恢复，所有持久化状态最终都会自洽地收敛在一个普通的操作系统文件里。

在单文件容器的内部，SQLite 构建了一套层次分明、职责明确的存储引擎架构。本节将自顶向下层层拆解这套存储体系：首先是由 B 树负责的逻辑记录索引与导航；中间是由 Pager 层维护的页缓存（Page Cache）与原子事务安全；底层则是配合 WAL 模块实现的高性能并发读写机制。

源码仓库：https://sqlite.org/src，Public Domain。本文基于 SQLite 3.46 版本。

1. 存储栈

SQLite 的存储子系统遵循严密的分层架构，每一层仅通过明确定义的抽象接口与紧邻的下层进行交互：

┌─────────────────────────────────┐
│         B-tree 层               │  组织数据：查找、插入、删除、遍历
│   btree.c / btreeInt.h          │
├─────────────────────────────────┤
│         Pager 层                │  页缓存 + 事务安全
│   pager.c                       │
├─────────────────────────────────┤
│         OS 层 (VFS)             │  文件读写、锁、同步
│   os_unix.c / os_win.c         │
└─────────────────────────────────┘

各层之间的协作边界异常清晰：

• B-tree 层把数据库视作由固定大小的“页面”拼装而成的树状索引。当它需要读取某页时，调用 sqlite3PagerGet()；当它需要修改页内数据时，调用 sqlite3PagerWrite() 申请标记脏页。B 树完全不关心页面最终如何落盘，也不处理底层的文件锁与崩溃恢复。
• Pager 层把数据库视作一个由页号索引的页缓存池。它并不理解页内具体存放的是 B 树的键、指针还是单元格记录，只专注于维护页面的脏状态、事务生命周期以及写日志（Journal/WAL）的先后时序，确保在任何断电突发场景下数据都能回滚到一致状态。
• OS 层（VFS）则负责抹平不同操作系统间系统调用的差异，直接对物理文件实施读写、加锁与 fsync 刷盘。

在启用预写日志（WAL）模式时，Pager 会与 WAL 模块协同运作：写入操作产生的脏页会按顺序追加到独立的 WAL 文件中，主数据库文件在事务提交前保持原样；而当上层请求某一页时，WAL 模块会判定应从 WAL 文件拉取最新的修改帧，还是直接从主数据库文件读取基准页。

2. 页式存储

页式存储

在物理层面上，整个 SQLite 数据库文件被严格划分为等长大小的数据块，称为页（Page）。在现代版本中，默认页大小通常为 4096 字节（且必须是 512 到 65536 之间 2 的幂次方）。

所有逻辑构件——不管是 B 树的内部寻址节点、叶节点单元格、超长记录的溢出链，还是未使用的空闲页链表——最终都规整地存放在这些页内。页号从 1 开始顺序编号（0 代表无效页号或空指针）。其中，第 1 页具有特殊的全局地位，其开头的 100 个字节被固定保留为整座数据库的文件头元数据：

OFFSET   SIZE    DESCRIPTION
  0       16     魔数: "SQLite format 3\000"
 16        2     页大小 (字节)
 24        4     文件更改计数器
 28        4     数据库总页数
 32        4     第一个空闲链表页
 40       60     15 个 4 字节的元数据

页大小在数据库初次创建并写入文件头后便被固化，后续读写都严格以此为对齐边界。

在内核中，BtShared 结构体代表一个打开的 B 树存储实例，由属于同一物理文件的多个逻辑连接共享。它直接持有底层 Pager 的指针以及常驻内存的第 1 页句柄：

struct BtShared {
  Pager *pPager;        /* 页缓存 */
  MemPage *pPage1;      /* 数据库第 1 页 */
  BtCursor *pCursor;    /* 所有打开的游标链表 */
  u32 pageSize;         /* 页大小 (字节) */
  u32 usableSize;       /* 每页可用字节数 */
  u16 maxLocal;         /* 索引 B 树的最大本地负载 */
  u16 minLocal;         /* 索引 B 树的最小本地负载 */
  u16 maxLeaf;          /* 表 B 树的最大本地负载 */
  u16 minLeaf;          /* 表 B 树的最小本地负载 */
  // ...
};

这里有一个不可忽视的字段：usableSize = pageSize - nReserve。SQLite 允许在每个页面的最末尾保留若干字节（nReserve）供第三方扩展使用（例如透明页面加密扩展）。因此，B 树层在计算页面内部剩余空间、分裂阈值以及单元格尺寸时，必须一律以 usableSize 为基准。

3. 两种 B 树

Table B-tree 与 Index B-tree

在 SQLite 内部，数据库中的每一张数据表和每一个用户索引，都分别对应一棵完全独立的 B 树。它们虽然混杂在同一个物理文件中分配页面，但通过系统表 sqlite_schema 中登记的各自根页号（Root Page）完全隔离。

SQLite 针对数据存储和索引检索的差异，划分了两种形态的 B 树：

类型	键	数据	用途
Table B-tree	64 位整数（rowid）	存放于叶节点	存储普通表的数据行记录
Index B-tree	任意长度的二进制有效载荷	无数据负载（键即完整信息）	存储用户创建的索引键

在源码实现中，这两类 B 树并不依赖不同的结构体，而是通过页头中的标志位组合来明确其节点属性：

#define PTF_INTKEY    0x01   /* 键是整数 */
#define PTF_ZERODATA  0x02   /* 无数据，只有键 */
#define PTF_LEAFDATA  0x04   /* 数据只存在叶节点 */
#define PTF_LEAF      0x08   /* 叶节点（无子页指针） */

Table B-tree 节点的页标志是 PTF_INTKEY | PTF_LEAFDATA | PTF_LEAF（叶节点）或 PTF_INTKEY | PTF_LEAFDATA（内部索引节点）。而 Index B-tree 节点的标志则是 PTF_ZERODATA | PTF_LEAF（叶节点）或 PTF_ZERODATA（内部节点）。

4. 页面格式

物理页面的内部布局是存储引擎最富巧思的环节之一。为了在单页内高效容纳大量变长记录并支持高速二分检索，SQLite 采用了经典的槽式页面（Slotted Page）架构。

B 树页面的内部布局

在内存与磁盘中，每个 B 树页面都由四个区域首尾相接地拼装而成。从低地址向高地址看，整体布局如下：

|----------------|
| 页头           |   叶节点 8 字节，内部节点 12 字节
|----------------|
| 单元格指针数组  |   每个 2 字节，按键排序，向下增长
|                |         ↓
|----------------|
| 未分配空间      |
|----------------|         ↑
| 单元格内容区    |   存放实际数据，向上增长，顺序任意
|                |
|----------------|

位于页面顶端的页头结构记录了该页面的关键几何尺寸：

OFFSET   SIZE     DESCRIPTION
  0       1      标志位 (PTF_INTKEY, PTF_LEAF 等)
  1       2      第一个空闲块的偏移
  3       2      本页单元格数量
  5       2      单元格内容区起始位置
  7       1      碎片字节总数
  8       4      最右子页指针 (仅内部节点)

这种布局的精妙之处在于逻辑排序与物理存储解耦。单元格指针数组（Cell Pointer Array）中的每个 2 字节指针都严格按照键的大小有序排列；但指针所指向的单元格真实数据，则是从页面最底端向上按需追加的。

当向页面中插入一条新记录时，存储引擎完全不需要搬移已有的庞大行数据，只需在顶部的指针数组中腾出 2 字节插入新偏移，并将实际数据塞入底部剩余空间即可。页内查找时，二分算法只在连续紧凑的 2 字节指针数组上快速寻址，兼顾了极高的插入效率与内存局部性。

当物理页面被加载进内存后，SQLite 使用 MemPage 结构体来管理该页在内存中的运行时视图：

struct MemPage {
  u8 isInit;           /* 是否已初始化 */
  u8 intKey;           /* True: table b-tree; False: index b-tree */
  u8 intKeyLeaf;       /* True: intkey 表的叶节点 */
  u8 leaf;             /* True: 叶节点 */
  u8 hdrOffset;        /* 页头偏移 (第 1 页为 100，其他为 0) */
  u8 childPtrSize;     /* leaf ? 0 : 4 */
  u16 nCell;           /* 本页单元格数量 */
  u16 cellOffset;      /* 单元格指针数组在 aData 中的偏移 */
  int nFree;           /* 空闲字节数 */
  u8 *aData;           /* 指向页面原始数据 */
  u8 *aCellIdx;        /* 单元格指针数组起始位置 */
  BtShared *pBt;       /* 所属的 BtShared */
  DbPage *pDbPage;     /* Pager 层的页面句柄 */
  // ...
};

这里 hdrOffset 字段精准映射了前文提到的特殊设计：对于普通数据页，页头从字节 0 处起始；而对于整座数据库的第 1 页，由于前 100 字节被全局文件头占据，B 树页头便顺延从偏移 100 处开始解析。

每个单元格（Cell）内部装载着一条完整的索引项或表记录：内部节点的单元格包含 4 字节的左子页号与分隔键；而叶节点的单元格则包含变长编码的键值、实际列数据以及在数据过长时指向的溢出页链表指针。这里的整数和长度广泛采用 SQLite 自研的 Varint 变长编码（最高位作为延续标志，最多 9 字节即可无损表达 64 位无符号整数），极大压榨了磁盘空间的有效载荷。

5. BtCursor：定位迭代器

在 B 树之上，所有上层子系统（包括 VDBE 的字节码指令）都必须通过游标（BtCursor）来感知和操纵底层记录。游标不仅是一个指向某页某单元格的指针，它完整封装了一次树遍历会话的上下文状态。

struct BtCursor {
  u8 eState;            /* CURSOR_VALID, CURSOR_INVALID 等 */
  Btree *pBtree;        /* 所属连接 */
  BtShared *pBt;        /* 所属文件 */
  Pgno pgnoRoot;        /* B 树根页号 */
  i64 nKey;             /* 最后访问的整数键 */
  CellInfo info;        /* 当前单元格的解析结果 */
  MemPage *pPage;                        /* 当前页 */
  MemPage *apPage[BTCURSOR_MAX_DEPTH-1]; /* 祖先页栈 */
  u16 ix;               /* 当前页中的单元格索引 */
  u16 aiIdx[BTCURSOR_MAX_DEPTH-1];       /* 祖先页中的索引 */
  i8 iPage;             /* apPage 栈的当前深度 */
  // ...
};

这里展现了一个极具启发性的存储系统设计考量：在经典数据结构教材中，树节点往往包含指向父节点的指针。但若在物理磁盘页中固化“父页号”，一旦树发生分裂或再平衡，就会触发灾难性的级联修改——更新父节点会导致所有子节点的反向指针失效，造成大量无谓的脏页刷盘。

SQLite 的物理页面完全不包含任何指向父页面的指针。取而代之的是，游标在内存中维护了一组由当前路径构成的祖先调用栈（apPage[] 与 aiIdx[]）。当游标自顶向下遍历时，沿途访问的父级页面指针与槽位索引会被依次压入栈中。当需要向上回溯（例如跨页步进或触发分裂）时，调用 moveToParent 仅是一次纯内存的 $O(1)$ 出栈操作，彻底解除了物理页对父级元数据的耦合。

5.1 定位：sqlite3BtreeTableMoveto

在 Table B-tree 中依据整型 rowid 定位记录的核心函数是 sqlite3BtreeTableMoveto。它从树的根页出发，逐层向下执行页内二分：

int sqlite3BtreeTableMoveto(BtCursor *pCur, i64 intKey,
                            int biasRight, int *pRes) {
  // 优化 1：若游标已然精准停留在目标键上，直接返回
  if( pCur->eState==CURSOR_VALID && (pCur->curFlags & BTCF_ValidNKey)!=0 ){
    if( pCur->info.nKey==intKey ){
      *pRes = 0;
      return SQLITE_OK;
    }
    // 优化 2：若目标键恰好是当前键 +1（顺序追加的典型场景），尝试单步步进
    if( pCur->info.nKey+1==intKey ){
      rc = sqlite3BtreeNext(pCur, 0);
      // ...
    }
  }

  rc = moveToRoot(pCur);  // 回到根页重新下潜
  for(;;){
    MemPage *pPage = pCur->pPage;
    int lwr = 0, upr = pPage->nCell - 1;

    // 页内二分搜索指针数组
    for(;;){
      int idx = (lwr + upr) / 2;
      i64 nCellKey;
      pCell = findCellPastPtr(pPage, idx);
      // 表 B 树的叶节点单元格需要跳过负载长度 varint 才能读到 rowid
      getVarint(pCell, (u64*)&nCellKey);

      if( nCellKey < intKey )      lwr = idx + 1;
      else if( nCellKey > intKey ) upr = idx - 1;
      else {
        if( !pPage->leaf ){ lwr = idx; break; } // 内部节点仅存分隔键，进入左子树
        *pRes = 0; return SQLITE_OK;             // 叶节点命中目标
      }

      if( lwr > upr ) break;  // 当前页未找到精确匹配
    }
    if( pPage->leaf ) break;          // 已达叶节点，搜索结束
    moveToChild(pCur, childPageNo);   // 压栈并下潜到子页
  }
}

该函数融入了两处价值极高的工程特化：

1. 位置缓存快检：若游标当前指向的单元格键恰好等于目标键，无需任何遍历，直接返回成功。
2. 递增追加旁路：在自增主键的大批量插入场景中，下一个待写入的键往往正是 当前键 + 1。SQLite 会优先尝试调用轻量的 sqlite3BtreeNext() 向后探一步；若命中，便完全绕过了自根节点层层下潜的整套对数开销。

5.2 步进：sqlite3BtreeNext

当执行全表扫描或范围查询时，sqlite3BtreeNext() 负责将游标推向物理拓扑中的下一条连续记录：

int sqlite3BtreeNext(BtCursor *pCur, int flags){
  MemPage *pPage;
  pCur->info.nSize = 0;
  pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl);
  if( pCur->eState!=CURSOR_VALID ) return btreeNext(pCur);
  pPage = pCur->pPage;
  if( (++pCur->ix) >= pPage->nCell ){
    pCur->ix--;
    return btreeNext(pCur);  // 慢路径：当前页已读完，需跨页回溯
  }
  if( pPage->leaf ){
    return SQLITE_OK;         // 快路径：叶节点内递增单元格索引
  }else{
    return moveToLeftmost(pCur); // 内部节点：进入子树最左侧叶
  }
}

这里清晰地体现了快慢路径分离的优化哲学：

• 快路径：绝大多数连续步进都发生在一个包含数十或上百个单元格的叶页面内部。此时仅需将局部索引 ix 自增 1，验证未超限后立即返回 SQLITE_OK，整个过程不过区区几条汇编指令。
• 慢路径：当当前叶页面的单元格全部耗尽时，才回退触发复杂的 btreeNext()。它依靠游标内置的 apPage[] 祖先栈逐级向上回退到父节点，再转向右兄弟分支下探到新子树的最左叶节点（即标准 B 树的中序遍历）。直到回溯至根节点且再无可遍历分支时，向上返回 SQLITE_DONE。

6. 插入与分裂

数据写入最终通过 sqlite3BtreeInsert() 完成。它接收一个 BtreePayload 对象（打包了行记录或索引键），将其压入游标当前所指向的树位置：

int sqlite3BtreeInsert(
  BtCursor *pCur,
  const BtreePayload *pX,  /* 要插入的行数据 */
  int flags,
  int seekResult
){
  // 1. 若当前存在多个并发游标，预先保存它们的位置（避免树形态调整后失效）
  if( pCur->curFlags & BTCF_Multiple ){
    saveAllCursors(p->pBt, pCur->pgnoRoot, pCur);
  }

  // 2. 原地覆盖优化：若为 table b-tree 且键已存在，且新旧数据长度完全一致
  if( pCur->info.nPayload == newPayloadSize ){
    return btreeOverwriteCell(pCur, pX);
  }

  // 3. 组装新单元格，插入当前页面的槽位数组
  // 4. 若当前页面空间耗尽发生溢出，触发再平衡
  rc = balance(pCur);
}

这里展现了一处针对更新操作的深度优化：当业务执行 UPDATE 修改某一行、且新旧数据的序列化字节数恰好相等时，底层会直接执行 btreeOverwriteCell() 原地覆写页面对应区间。这彻底免除了“删除旧单元格、插入新单元格、可能引爆页面分裂”的一连串繁琐连锁反应。

6.2 balance()：再平衡与三路调度

当向页面插入单元格导致未分配空间不足，或者因删除记录导致页内空闲空间超过可用大小的 $2/3$ 时，引擎会调用 balance() 实施再平衡。由于底层的变动可能向上蔓延导致父级节点同样超限，balance() 在实现上是一个依托游标祖先栈逐级向上追溯的驱动循环：

static int balance(BtCursor *pCur){
  do {
    MemPage *pPage = pCur->pPage;

    // 终止条件：既无溢出单元格，且页内空闲空间尚未超过 2/3
    if( pPage->nOverflow==0
     && pPage->nFree*3 <= (int)pCur->pBt->usableSize*2 ){
      break;
    }

    if( pCur->iPage==0 ){
      // 场景 1：根节点溢出 → balance_deeper()：向下分裂，根节点拔高
      rc = balance_deeper(pPage, &pCur->apPage[1]);
    }else{
      if( /* 快速路径条件：intkey 叶节点且溢出发生在末尾 */ ){
        // 场景 2：顺序追加快速路径 → balance_quick()：直接开辟新右兄弟页
        rc = balance_quick(pParent, pPage, aBalanceQuickSpace);
      }else{
        // 场景 3：通用路径 → balance_nonroot()：在当前页与最多 2 个兄弟页间重平衡
        rc = balance_nonroot(pParent, iIdx, ...);
      }
    }
    // 游标出栈退回父节点，在下一轮循环中检查父节点是否也超限
    pCur->pPage = pCur->apPage[--pCur->iPage];
  } while( rc==SQLITE_OK );
}

SQLite 针对不同分裂形态设计了三个各具特长的平衡例程：

• balance_deeper()：专门用于处理根页溢出。在 SQLite 中，根页的页号是写入元数据系统表的固定标识，物理位置不可改变。因此当根页填满时，它不能像普通页那样分裂并产生一个新的独立根；相反，它会开辟一个全新的子页面，把自身所有单元格拷贝到子页中，自身则降级为一个仅包含子节点指针的内部导航节点。这是 SQLite B 树层高增长的唯一方式。
• balance_quick()：针对自增主键追加写入的专属快速路径。当一个整型主键表在页末尾追加记录并溢出时，完全没有必要将该页的历史数据打散重组；它直接分配一个全新的空白右兄弟页接收该单元格，原页面保持不动。
• balance_nonroot()：处理普通内部节点或叶节点分裂/合并的通用大一统例程。它会同时锁定当前页以及相邻的最多 2 个兄弟页，将这些页面的所有单元格聚合在一起，随后均摊写入新开辟或重排的页面中，并在父节点中同步更新或插入新的分隔键。

7. Pager 层：页缓存与崩溃安全

如果说 B 树层负责在内存中搭起数据的骨架，那么真正为 SQLite 构筑起事务原子性（Atomicity）与持久性（Durability）铁壁的，则是中间的 Pager 层。

Pager 是整个系统的守门人。它把物理磁盘文件抽象为一个能够按需换入换出的页面缓存池，并运用精密的有限状态机来严守事务的生命周期：

Pager 状态机

Pager 的运行严格受控于一组单向演进的状态迁移图：

OPEN → READER → WRITER_LOCKED → WRITER_CACHEMOD → WRITER_DBMOD → WRITER_FINISHED → READER
                                                                                      ↑
任何 WRITER 状态 ————→ ERROR ————→ OPEN ————————————————————————————————————————————————┘

每个状态对应着明确的文件锁权限与 I/O 行为：

状态	对应文件锁	行为与职责
OPEN	无锁	初始空闲状态，未持有任何系统文件锁
READER	SHARED（共享锁）	允许并发读取页缓存或物理文件，禁止写入
WRITER_LOCKED	RESERVED（保留锁）	准备开启写事务，提示其他连接即将修改，但尚未动笔
WRITER_CACHEMOD	EXCLUSIVE（排他锁）	内存页缓存已被篡改，回滚日志文件已创建并同步
WRITER_DBMOD	EXCLUSIVE（排他锁）	脏页数据已开始刷入物理数据库文件
WRITER_FINISHED	EXCLUSIVE（排他锁）	数据库落盘完毕，等待提交或解除写状态
ERROR	-	遭遇不可恢复的底盘 I/O 错误，锁定拒绝后续操作直至回滚

在经典的传统回滚日志模式下，修改必须历经这一整套线性状态流转；而在 WAL 模式下，由于所有写入都流向了日志，Pager 根本不会触碰 WRITER_DBMOD 与 WRITER_FINISHED，大幅缩短了排他锁的持有周期。

在物理对象上，Pager 结构体聚合了数据库主文件描述符 fd、回滚日志描述符 jfd、内存换入缓存句柄 pPCache，以及一张关键的位图 Bitvec *pInJournal。这张位图精准记录了在当前事务中，哪些页号的原始版本已经被安全沉淀到日志文件中。

7.1 获取页面：sqlite3PagerGet

当 B 树层欲探访某个具体页码时，它调用 sqlite3PagerGet(pPager, pgno, &pPage, flags)。Pager 内部通过函数指针分发，默认由 getPageNormal() 承接。它会优先在内存缓存哈希表 PCache 中搜寻；若未命中，则分配一个空闲的 PgHdr 槽位，并调用 VFS 的 sqlite3OsRead() 从磁盘文件中把整页数据拉入内存。

7.2 标记脏页：sqlite3PagerWrite 的前置日志铁律

在 B 树层对任何已载入内存的页面动哪怕一个字节之前，必须先显式调用 sqlite3PagerWrite() 申请写权限：

static int pager_write(PgHdr *pPg){
  Pager *pPager = pPg->pPager;

  // 1. 若当前尚未打开日志文件，先创建日志
  if( pPager->eState==PAGER_WRITER_LOCKED ){
    rc = pager_open_journal(pPager);
  }

  // 2. 将页面挂载至脏页链表
  sqlite3PcacheMakeDirty(pPg);

  // 3. 回滚日志模式的核心守则：先写原始数据到日志（仅在首次修改该页时触发）
  if( pPager->pInJournal!=0
   && sqlite3BitvecTestNotNull(pPager->pInJournal, pPg->pgno)==0 ){
    if( pPg->pgno <= pPager->dbOrigSize ){
      rc = pagerAddPageToRollbackJournal(pPg);  // 写入原始页面
    }
  }

  // 4. 赋予 PGHDR_WRITEABLE 标记，上层此时方可安全修改
  pPg->flags |= PGHDR_WRITEABLE;
  return rc;
}

这段逻辑体现了数据库系统中最核心的预写日志（Write-Ahead Logging / Undo Logging）铁律：永远在内存修改真正发生之前，把受损前的“快照原貌”安全固化在磁盘日志中。如果系统随后发生突发断电，这些预存的旧页面就是唯一的救命解药。

7.3 崩溃恢复：pager_playback

回滚日志的崩溃恢复

如果在事务提交前夕系统突然断电或崩溃，下一次任何连接尝试打开数据库时，Pager 会检测到文件系统残留的未解热日志（Hot Journal），并立即挂载 pager_playback() 启动逆向急救：

1. 打开残留的回滚日志文件，读取头部的全局快照尺寸与页数记录；
2. 顺着日志序列，逐一读出其中暂存的旧版原始数据页；
3. 将这些旧页原样覆盖写回物理数据库文件的对应偏移处；
4. 调用文件截断，将数据库物理大小复原至事务开启时的 dbOrigSize；
5. 最后，安全删除日志文件（或将其头部全置为 0）。

在传统的单文件日志模式下，日志文件的物理删除或归零，正是整个 ACID 事务的原子提交点。日志一旦消失，意味着上一任事务已合法生效；反之，只要日志依旧矗立在磁盘上，任何重启的节点都会强制回放日志、抹平未提交的痕迹。

8. WAL 模式

传统的回滚日志机制虽然逻辑直观，但其致命瓶颈在于写操作与读操作的互斥性：写者在将脏页刷盘时必须持有排他锁，所有读者必须完全退避等待。为了从根本上解锁高并发读写的潜能，SQLite 引入了预写日志（WAL，Write-Ahead Logging）模式。

8.1 核心机制：追加写与帧解耦

WAL 协议

在 WAL 模式下，主数据库文件在日常修改中几乎退化为一个“只读基线镜像”，所有新产生的脏页都会以帧（Frame）为单位连续追加到独立的日志文件（-wal）尾部。

• 顺序追加写入：脏页不覆写主数据库文件，而是顺序写入 WAL 末尾。每个帧由 24 字节的帧头（记录目标页号、提交时的数据库页数 nTruncate、盐值与校验和）及后续完整的页面数据组成。
• 快照读路由：当读取某一页时，引擎会先去检索 WAL 中是否存在该页的更新版本。若存在且符合当前事务的可见性，则从 WAL 文件中提取；否则回退读取主数据库文件。
• 极速提交：提交事务仅仅意味着向 WAL 追加一个带有 nTruncate > 0 标记的提交帧，并对 WAL 文件执行一次单向 fsync。完全省去了对主数据库文件的随机刷盘。
• 定期检查点：当 WAL 累积到一定规模（默认 1000 帧）时，后台触发检查点，将 WAL 中的最新页按顺序回写覆写至主数据库，回收 WAL 空间。

在内核中，Wal 结构体维系了数据库文件与 WAL 文件的双重句柄、多级读写锁，以及最关键的 WAL 索引（WalIndexHdr 与共享内存映射 apWiData）。

8.2 读写互不阻塞的并发奥秘

WAL 之所以能够做到“读者不阻塞写者、写者亦不阻塞读者”，核心在于其类似 MVCC（多版本并发控制）的快照隔离机制：

当一个读事务启动时（walTryBeginRead），它会探查当前 WAL 的最大有效提交帧号，并将其固化在自身的读标记 mxFrame 中。在整个读事务持续期间，该读者仅能感知帧号小于等于 mxFrame 的历史版本。后续即便有并发写者向 WAL 追加了成千上万个新帧，由于其帧号全部大于该读者的快照水位，对该读者完全不可见。

写者写入时，只需获取互斥的排他写锁以防止多个写者并发交错追加 WAL 尾部，完全无须等待正在阅读旧快照的读者退出。

static int walFrames(Wal *pWal, int szPage,
                     PgHdr *pList, Pgno nTruncate,
                     int isCommit, int sync_flags) {
  // 1. 若 WAL 为空，初始化 32 字节的 WAL 文件头
  if( pWal->hdr.mxFrame==0 ){
    rc = sqlite3OsWrite(pWal->pWalFd, aWalHdr, sizeof(aWalHdr), 0);
  }

  // 2. 将脏页链表逐页组装为帧并顺序追加
  for(p=pList; p; p=p->pDirty){
    iFrame++;
    // 写 24 字节帧头与页面物理数据
    rc = walWriteOneFrame(&w, p, nTruncate, iOffset);
    iOffset += szFrame;

    // 同步更新共享内存（WAL Index）中的哈希查找表
  }

  // 3. 事务提交时，对 WAL 文件执行物理刷盘同步
  if( isCommit && sync_flags ){
    rc = sqlite3OsSync(pWal->pWalFd, sync_flags);
  }

  // 4. 原子更新共享内存中的全局最大帧号 mxFrame
}

为了避免读者每次查页时都要在长达数兆的 WAL 文件里顺序从后向前扫，SQLite 引入了 WAL 索引（通常映射在同名的 .shm 共享内存文件中）。这是一个基于哈希表的高性能内存索引，记录了“物理页号 $\to$ 其在 WAL 中的最新帧号”的映射。读者通过哈希查找即可在微秒级确认某一页在 WAL 中的具体落点。

8.3 检查点机制与四种回写策略

随着写入持续累积，WAL 文件不可能无节制膨胀。检查点（Checkpoint）的核心任务，就是把 WAL 中已经提交的数据页回刷到主数据库文件中。

SQLite 在 sqlite3WalCheckpoint() 中引入了优化的写盘策略：它并非按照帧的写入先后盲目回刷，而是通过 WalIterator 预先按目标页号进行排序，将零散的修改转化为对主数据库文件的纯线性顺序 I/O，极大释放了机械磁盘或 SSD 的吞吐潜能。

检查点支持四种灵活的运行策略：

模式	协作策略与行为
PASSIVE	尽力而为模式。不阻塞任何并发读写，仅回写当前不受活跃读者快照影响的帧，可能只完成部分同步
FULL	等待当前活跃写者结束，将所有提交帧回写至主库；但若有老读者仍在读取 WAL，则不等待其离开
RESTART	在 FULL 的基础上，阻塞等待所有慢读者彻底退出旧快照，随后将 WAL 的写入游标重置回第 1 帧
TRUNCATE	与 RESTART 一致，并在重置游标后调用文件系统接口将 WAL 文件物理截断为 0 字节

8.4 WAL 模式下的完整读取路径

理清上述组件后，WAL 模式下任意一个读页请求的决策链路便一览无余：

1. 提取当前读事务在启动时锁定的快照水位 mxFrame；
2. 在共享内存的 WAL 索引哈希表中，探查该 pgno 是否拥有最新帧号记录；
3. 若命中且其帧号 $\le \text{mxFrame}$，直接依据帧偏移从 -wal 文件中读取最新数据并返回；
4. 若未命中，或虽然命中但帧号大于该读者的快照水位，则安全穿透回主数据库文件，从基线物理页中提取数据。

9. 习题

9.1 巩固

#50615

⚡2⏳2

建一个库，执行 CREATE TABLE users(id INTEGER PRIMARY KEY, name TEXT, age INTEGER); 并插入三行，然后按 §2 的字段表手工核对文件头：

1. 用 od -A d -t x1 -N 100 test.db（PowerShell 用 Format-Hex）把前 100 字节贴出来，逐字段标出偏移：魔数、页大小、文件更改计数器、数据库总页数、空闲链表页、schema cookie、schema 格式、文本编码、版本号。把每个字段的字节与十进制值列成表。
2. 用 §4 的页头格式读第 2 页：标志字节、第一个空闲块偏移、单元格数量、单元格内容区起始位置、碎片字节数。把标志字节拆成 PTF_* 位，说明它是什么类型的页。
3. 建一个索引 CREATE INDEX users_age ON users(age);，用 SELECT type, name, rootpage FROM sqlite_schema; 找到索引的根页，读它的标志字节与页内单元格数量。它和表 B 树的标志差哪几位？
4. 把表填到 500 行，再读一次表根页的标志字节，说明它为什么变了。

验收：文件头各字段与 PRAGMA 查询一致（page_size、page_count、freelist_count、encoding）；第 2 问标志为 0x0D，拆成 0x01|0x04|0x08；第 3 问索引叶页为 0x0A（PTF_ZERODATA|PTF_LEAF），比表叶少 PTF_INTKEY 与 PTF_LEAFDATA；第 4 问根页变成 0x05（去掉 PTF_LEAF）。

#50616

⚡3⏳2

§4 说单元格由「可选的左子页号、varint 长度、负载、可选的溢出页号」组成，记录自身又有「头部 + serial type + 数据」。写一个程序 record.c（只用 fopen/fread 与手写的 varint 解码）打印第 2 页每个单元格的字段：

1. 解出每个单元格的负载长度、rowid、负载前 4 字节（记录头长度与第一个 serial type）。
2. 按记录头解出全部 serial type，再按类型取出各列的值。对下面这张表验证：

CREATE TABLE m(id INTEGER PRIMARY KEY, i INTEGER, r REAL, t TEXT, b BLOB, n TEXT);
INSERT INTO m VALUES(1, -5, 2.5, 'hi', x'00ff', NULL);
INSERT INTO m VALUES(2, 300, NULL, 'hello', x'', 'world');

3. 列出两行的 serial type，说明 -5、300、2.5、'hi'、x'00ff'、NULL 各对应哪个类型号，'hi' 与 x'00ff' 的类型号差在哪一位。
4. 对同一段字节写一个 varint 编码器，验证 1、127、128、16383、16384、2³⁵、2⁶³ 的编码长度分别为 1、1、2、2、3、6、9 字节。为什么第 9 个字节只有 8 位有效数据？

验收：两行的 serial type 依次为 [0,1,7,17,16,0] 与 [0,2,0,23,12,23]（id 是 rowid，记录里对应 NULL 占位，具体值以你实测为准）；值全部解对；varint 长度序列正确，并说明 64 位整数用 9 个 7 位组放不下，所以最后一字节让出 1 位。

#50617

⚡3⏳3

写一个 WAL 文件解析器 walhdr.c：开一个空库，执行 PRAGMA journal_mode=WAL 与 PRAGMA wal_autocheckpoint=0，建表并插入 100 行，然后直接读 -wal 文件。

1. 解出 32 字节文件头：魔数、格式版本、页大小、检查点序号、两个 salt、两个校验和。魔数 0x377f0682 与 0x377f0683 的区别是什么？
2. 按「帧偏移 = 32 + (n−1) × (24 + 页大小)」逐帧解出帧头：页号、提交后的数据库页数、两个 salt、两个校验和。打印每帧的 pgno 与 dbsize。
3. 指出哪几帧是提交帧，依据是哪一个字段。再把建表和插入放进同一个事务（先 BEGIN 再执行两条语句），重新建库解析：帧数变成几个，为什么少了？
4. 用 PRAGMA wal_checkpoint(TRUNCATE) 清空 WAL，再插 100 行，重新解析。文件头里的检查点序号与 salt 有什么变化？为什么变了？

验收：建表单事务、插入单事务时共 3 个帧（页 1 一帧、页 2 两帧），第 2、3 帧的 dbsize 都是 2、第 1 帧为 0；建表与插入合在一个事务时只有 2 帧（页 1 与页 2 各一帧），因为 sqlite_schema 与表根页在同一提交里写出。TRUNCATE 之后 WAL 大小为 0，下一次写入的文件头检查点序号加 1、salt 改变。第 3 问说明 dbsize 为 0 表示普通帧、非 0 表示提交帧及其后的数据库页数。

#50618

⚡3⏳3

§4 的页头里有两个容易忽略的字段：第一个空闲块偏移（偏移 1 的 2 字节）与碎片字节数（偏移 7 的 1 字节）。

1. 建一张 100 行的 users 表，DELETE FROM users WHERE id % 2 = 0;，然后读第 2 页：nCell、单元格内容区起始位置、第一个空闲块偏移。沿空闲块链表走一遍，打印每个块的偏移、下一个块、块大小。
2. 空闲块大小之和与「碎片字节数」是什么关系？碎片是怎么产生的（提示：被删除的单元格小于 4 字节时无法登记成空闲块）。
3. 再插入两行长度与原行相同的记录，观察第一个空闲块偏移与内容区起始位置是否变化，解释 SQLite 优先从哪块空间分配。
4. 把表删到只剩几行、页数不变的情况下，页内空闲空间如何变化？此时为什么整页没有被回收（提示：与文件头的空闲链表页字段有关）。

验收：能解出完整空闲块链并求和；第 2 问说明小于 4 字节的碎片不登记，且新块按偏移顺序插入链表、相邻块会合并；第 3 问实测短记录优先用空闲块（第一个空闲块的 14 字节缩到 4 字节，但块仍在链表里、偏移不变），长记录放不进空闲块时从内容区顶端分配、内容区起始位置前移；第 4 问区分页内空闲（块链与碎片）与整页空闲链表（文件头偏移 32 的 trunk 与偏移 36 的计数），删除整页后页进入空闲链表，PRAGMA freelist_count 增加。

9.2 编程

#50619

⚡4⏳3

不看 SQLite 的 btree.c，只用 §2、§3、§4 的格式说明写一个只读遍历器 walk.c，把一个 Table B 树的所有 rowid 按升序打印出来。

1. 打开数据库文件，读文件头拿到页大小与页数。
2. 从 sqlite_schema 里查出目标表的根页号（可以用 SQLite 命令行先查好写死在程序里，也可以自己解析第 1 页的记录）。
3. 写递归函数：内部节点先遍历每个单元格的左子页，再遍历最右子页；叶节点依次输出每个单元格的 rowid。注意内部节点页头是 12 字节、单元格以 4 字节子页号开头；叶节点页头是 8 字节、单元格以 varint 负载长度开头。
4. 用 500 行的表验证：输出 500 个 rowid，严格递增、无重复，且与 SELECT id FROM users ORDER BY id 的结果逐行相同。
5. 故意把内部节点页头的 12 改成 8，重跑。解释为什么会读到垃圾页码，以及你用什么检查让程序在越界时停下来而不是崩溃。

验收：500 个 rowid 与 SQL 查询完全一致；输出顺序即中序遍历顺序；第 5 问能指出页头少了 4 字节的「最右子页指针」，并说明在访问前检查 pgno >= 1 && pgno <= 页数。

#50620

⚡4⏳4

做一个崩溃恢复实验，验证 §7.2 与 §7.3 的「先写日志，再改数据」。

1. 写一个程序 crash.c：BEGIN 后插入若干行，写完但不 COMMIT，用 _Exit(0)（C11，<stdlib.h>）直接结束进程，让日志留在文件系统里。先不关数据库，也不要调用任何清理函数。
2. 在两种时机各做一次：插入少量行（脏页还在缓存里）、插入大量行并把 cache_size 调小、同时把页大小设成 512（脏页已溢出到主文件）。每种都保留 -journal 文件，用 od 看它开头 28 字节，记录魔数、nRec、原始页数。
3. 用命令行工具重新打开每个库，执行 SELECT count(*) 与 PRAGMA integrity_check。比较两种时机下结果与日志文件的状态，指出哪种情况日志真的是「热」的（提示：hasHotJournal 只看日志文件第 1 个字节是否为 0）。
4. 把第 2 步的日志文件删掉再打开。如果结果与保留日志时相同，说明为什么（提示：日志未同步完成时主文件是否已经改过；溢出时主文件确实被改过，但打开时的 PRAGMA page_count 取的是文件头里的页数）。
5. 回答：Pager 状态机在 BEGIN 前、写入后、COMMIT 后各处于哪个状态？日志文件在提交成功后被做了什么？

验收：少量插入时日志头的魔数可能是全 0（未完成同步），重新打开后行数为 0；大量插入且页已溢出时日志头有完整魔数 d9 d5 05 f9 20 a1 63 d7，重新打开后行数同样为 0、integrity_check 为 ok，文件头里的数据库页数回到事务开始前的值（本例为 2 页）。删掉日志后结果不变，因为文件头记录的页数没有把溢出的脏页算进去。恢复成功后日志文件被回放并解除「热」状态（首字节为 0，再次打开时直接当作残留删除）。第 5 问对应 WRITER_LOCKED、WRITER_CACHEMOD 与提交后回到 OPEN、日志被删除。

9.3 综合与挑战

#50621

⚡5⏳4

用一个 512 字节页的库观察 §6 的三种平衡例程，并把页形状与插入顺序联系起来。

1. 写程序用 PRAGMA page_size=512 建表，逐行顺序插入 20 行，每插一行记录：PRAGMA page_count、表的根页号、根页标志字节、根页 nCell。找出根页从叶节点变成内部节点的那一行，前后各贴一次根页的十六进制转储。
2. 读分裂后的根页：几个单元格、每个单元格的子页号与分隔键、最右子页号。叶页的 nCell 是多少？左页保留了多少旧行？这对应 balance_deeper、balance_quick 还是 balance_nonroot？
3. 把插入顺序改成随机顺序（打乱 40 个键），重新建库，比较页数与各叶页的 nCell 分布。为什么顺序插入时右叶只有 1 个单元格，而随机插入时两三个叶页比较均匀？
4. 再做一个「根页溢出」以外的分裂：把 40 行装进两三个叶页后继续插入，指出哪一次分裂由 balance_nonroot 处理，并说明它最多收集几个页的单元格。

验收：512 字节页、每行 20 字节文本时，第 19 行触发根分裂（实测根页 0x0D 变 0x05，页数 2 变 4，左叶 18 个单元格、右叶 1 个）；顺序插入的页数少于随机插入或至少分布更偏；第 4 问指出非根页溢出时 balance_nonroot 收集当前页与最多 2 个兄弟页，必要时把新页插进父页。

#50622

⚡6⏳5

用 PRAGMA wal_checkpoint(mode) 测量 §8.3 的四种模式，回答「谁在挡住检查点」。

1. 建 WAL 库，关掉自动检查点，写入 100 行（一个事务），再打开第二个连接并 BEGIN 后读一次表，让这个读者持有一个快照。
2. 第一个连接再写 100 行。依次执行 PASSIVE、FULL、RESTART、TRUNCATE，每次记录三列返回值（busy、日志帧数、已回写帧数）、-wal 文件大小、主库文件大小。每次之间不要关闭读者。
3. 让读者 COMMIT 并关闭，再执行 PASSIVE 与 TRUNCATE，记录变化。
4. 换一种顺序重做：先让写者提交，再由第二个连接 BEGIN 并读取。此时 FULL 会不会阻塞？RESTART 会不会？用「读者的读标记 mxFrame 是否早于需要回写的帧」解释差异。
5. 结合返回值说明：PASSIVE 为什么不阻塞；FULL 等的是写者还是读者；RESTART 与 TRUNCATE 多等的条件是什么；为什么 TRUNCATE 之后 -wal 变成 0 字节而主库文件反而变大。

验收：第 2 步 PASSIVE 返回 busy=0，FULL/RESTART/TRUNCATE 在 busy_timeout 到期后返回 busy=1；第 3 步 PASSIVE 把未回写的帧补齐，TRUNCATE 把 WAL 截到 0；第 4 步 FULL 返回 busy=0 而 RESTART 仍返回 busy=1。五个问题都能落到 §8.2 的读标记与 §8.3 的模式表上。