SQLite 内幕：WAL 机制、B-tree 结构、为什么它是最广泛部署的数据库（主题精读） 未开始

题记与说明

• 日期：2026-10-31
• 形式：主题研究（先检索 6 个来源精读，再加本地实证）
• 本次阅读的来源（全部在线精读原文）：
  1. Write-Ahead Logging — SQLite 官方文档（页面更新于 2026-08-25）
  2. Database File Format — SQLite 官方规范（更新于 2025-12-25，重点精读 §1.2–1.6 页面与 B-tree、§2 记录格式、§4 WAL 文件格式）
  3. Most Widely Deployed SQL Database Engine — SQLite 官方（更新于 2026-04-21）
  4. Appropriate Uses For SQLite — SQLite 官方
  5. How SQLite Scales Read Concurrency — Fly.io, SQLite internals 系列（2022-08-24，该系列通常署名 Ben Johnson，Litestream/LiteFS 作者）
  6. SQLite Internals: Pages & B-trees — Fly.io 同系列（2022-07-27）
• 本地实证：Windows + Python 3.12.12（bundled SQLite 3.50.4），13 项检查，输出见 §4.4。

0. TL;DR

SQLite 把"数据库"做成了一个嵌入应用进程的 C 库：没有服务器、没有网络协议，整个数据库就是一个跨平台单文件。支撑它做到"事务安全 + 高并发读 + 极致简单"的是三件事：定长页面 + 两种 B-tree（表/索引）负责数据的磁盘组织与对数级检索；WAL（写前日志）负责事务原子性与读写并发；单写者多读者 + 共享内存 wal-index 负责并发控制。官方对其地位的说法是：部署量"很可能超过其他所有数据库引擎的总和"，活跃使用的 SQLite 数据库可能超过 1 万亿个；它的竞争对手不是 PostgreSQL，而是 fopen()。

1. 核心问题

这组材料共同回答的问题是：一个没有任何服务器进程的嵌入式库，凭什么能同时做到 (a) 可靠的 ACID 事务落盘、(b) 读写互不阻塞的并发、(c) 在数十亿设备上成为部署量最大的数据库？ 拆开是三个子问题：

1. WAL 机制：SQLite 的事务原子性如何实现？为什么 2010 年引入的写前日志比最初的回滚日志（rollback journal）更快、并发更好？代价是什么？
2. B-tree 结构：数据在磁盘上到底长什么样？一个 INSERT 从回车键到字节落盘经历了什么？为什么几十 GB 的表查询仍然只要读几个页？
3. "最广泛部署"：这个说法的证据是什么？SQLite 到底在和谁竞争、为什么赢？

2. 主要主张

2.1 WAL：把"改原件存旧页"反转为"原页不动，新页追加"

• SQLite 最初用回滚日志保证原子性：改动前把原始页拷贝到 -journal 文件，再直接改主库文件；崩溃后用日志回放还原。COMMIT 的时刻 = 删除日志文件的时刻。
• WAL（3.7.0，2010-07-21）把它反转：主库文件保持不动，新版本的页追加写入 -wal 文件；往 WAL 追加了一条带 commit 标记的帧，事务即提交。原文：

"A COMMIT occurs when a special record indicating a commit is appended to the WAL. Thus a COMMIT can happen without ever writing to the original database, which allows readers to continue operating from the original unaltered database while changes are simultaneously being committed into the WAL."（wal.html §2）

• 由此得到官方列出的四大优势：更快（多数场景）、读写不互斥、磁盘 I/O 更顺序、fsync 次数更少。
• 代价：所有进程必须同机（依赖共享内存）、多 ATTACH 库事务不跨库原子、进入 WAL 后不能改 page_size、几乎只读的场景反而慢 1–2%、多了 -wal/-shm 两个伴生文件、需要关心 checkpoint。

2.2 WAL 的运行时机制：end-mark 快照、checkpoint、wal-index

• 读快照（end mark）：读事务开始时记住"WAL 中最后一条有效 commit 记录的位置"，此后只看这个位置之前的页版本 → 每个读者各自看到某个时间点的一致快照，天然 MVCC 式隔离。
• Checkpoint：把 WAL 中每页的最新版本拷回主库；默认 WAL 积到 1000 页（4KB 页时约 4MB） 自动触发。checkpoint 与读者可并发，但推进到任何读者的 end-mark 之后就必须停下——长读事务会饿死 checkpoint，使 WAL 无限增长（官方称为 checkpoint starvation）。
• wal-index（-shm 文件）：为避免读者每次扫描整个 WAL，SQLite 用 mmap 的共享文件维护"页号 → WAL 帧位置"的哈希索引。Fly.io 文章给出实现细节：32KB 块，每块含 4096 个页号列表 + 8192 个哈希槽，哈希公式 (pgno * 383) % 8192，冲突则向后找空槽，读者按 mxFrame 过滤掉快照之后的帧。因为依赖多进程共享内存，WAL 模式不能用于网络文件系统——这是官方列出的第一条劣势。
• WAL 复用：checkpoint 完成且无读者时，写者把 WAL 从头覆写（salt 值递增/随机化使旧帧失效），不截断文件——覆写比追加快。

2.3 B-tree：数据库 = 定长页组成的两种 B+ 树

• 文件全部由页构成：512B–64KB 的 2 的幂（默认 4096B），页号从 1 开始，理论最大库容量 281 TB（2³²−2 个 64KB 页）。每页用途唯一：B-tree 页（表/索引 × 内部/叶子共 4 种）、freelist 页、溢出页、ptrmap 页、锁页。
• 两种树（fileformat2 §1.6 原文）：

"Two variants of b-trees are used by SQLite. '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."

即表 b-tree = rowid 为键的 B+ 树（数据全在叶子），索引 b-tree = 任意键、无数据。页类型字节：0x02 索引内部页、0x05 表内部页、0x0a 索引叶子页、0x0d 表叶子页。

• 页 1 永远是 sqlite_schema 表的根，存着所有其他表/索引的根页号——打开数据库 = 从页 1 顺藤摸瓜。原文："The b-tree corresponding to the sqlite_schema table is always a table b-tree and always has a root page of 1."
• 页内布局：页头（8/12 字节）→ cell 指针数组（按键序）→ 未分配空间 → cell 内容区（从页尾向前生长）→ 保留区。cell 用 varint 压缩键长/载荷长，超大载荷溢出到单链溢出页。记录格式用串类型号区分 NULL/1–8 字节整数/浮点/TEXT/BLOB，ALTER TABLE ADD COLUMN 后旧记录可以缺列、按默认值补齐。
• 树高即 I/O 次数：Fly.io 的算术——4KB 内部页约存 500 个"子页号+键"条目，深度 4 的树可索引约 500³ ≈ 1.25 亿个叶子页 ≈ 476GB 数据，找任何记录最多读 4 个页：

"At a tree depth of 4, we can hold about 500³ leaf pages, or about a 476GB database. That means we only need to read 4 pages to find a given record—even in a huge database!"

2.4 为什么是最广泛部署的数据库

• 官方 quantifies："SQLite is likely used more than all other database engines combined"；每部智能手机上有数百个 SQLite 库，40 亿部在用手机 → "over one trillion (1e12) SQLite databases in active use"。覆盖 Android、iOS、Mac、Windows 10/11、Firefox/Chrome/Safari、Skype、Dropbox、PHP、Python 等。
• 官方的定位解释（whentouse.html，本主题最精辟的一句）：

"SQLite does not compete with client/server databases. SQLite competes with fopen()."

C/S 引擎卖的是"共享的企业数据中心"（并发、集中管控），SQLite 卖的是"应用本地数据存储"（零配置、可靠、单文件、离线可用）。它赢在赛道不同：所有需要"比裸文件格式更可靠的结构化本地存储"的地方都是它的市场——应用文件格式、IoT、浏览器、消息队列、数据传输容器。

• 官方对边界的表述同样清晰（决定它"不做什么"）：数据与应用跨网络 → 用 C/S；大量并发写者 → 用 C/S（"SQLite only supports one writer at a time per database file"）；数据大到不舒服地塞进单文件 → 用 C/S。除此之外 → "SQLite is almost always a better solution"。

3. 方法

各来源的论证方式不同，恰好互补成"规范—机制—实证—定位"四层：

1. 官方规范（fileformat2.html）：把文件格式定义到字节级——每个头字段给出偏移量、字节数、大小端、合法值；WAL 帧有效性判据（salt 匹配 + 累积校验和）写成算法。这是"可验证"的源头。
2. 官方机制文档（wal.html）：叙述设计动机与取舍——优势/劣势逐条列出，包括失效模式（checkpoint starvation、SQLITE_BUSY 的罕见场景、2026 年新披露的 WAL-reset bug）。
3. 从业者源码级解读（Fly.io 系列）：用 hexdump 展示真实文件的字节，把"规范"翻译成"你亲手能看到的东西"；用三明治店类比解释并发模型；用 b+ 树高算术解释"为什么大表查询也快"。
4. 官方定位论证（mostdeployed / whentouse）：先给覆盖面清单与数量级估算，再用"竞争对手是 fopen()"一句话锚定生态位。
5. 我的实证（本次新增）：在 Python 3.12.12 / SQLite 3.50.4 上建库、切 WAL、逐字节核对官方规范声称的头字段与帧结构（方法与输出见 §4.4）。

4. 数据与证据

4.1 关键数字（均出自所引来源）

4.2 关键原文引述（备查）

• "The WAL approach inverts this. The original content is preserved in the database file and the changes are appended into a separate WAL file."（wal.html §2）
• "WAL is significantly faster in most scenarios. / WAL provides more concurrency as readers do not block writers and a writer does not block readers. / Disk I/O operations tends to be more sequential using WAL. / WAL uses many fewer fsync() operations..."（wal.html §1 优势清单）
• "All processes using a database must be on the same host computer; WAL does not work over a network filesystem. This is because WAL requires all processes to share a small amount of memory..."（wal.html §1 劣势清单）
• "Two variants of b-trees are used by SQLite..."（fileformat2 §1.6，见 §2.3）
• "The b-tree corresponding to the sqlite_schema table is always a table b-tree and always has a root page of 1."（fileformat2 §1.6）
• "If we accidentally overwrite half the header and then the computer shuts down, we can detect that by calculating and comparing the checksum."（fly.io wal 文，解释帧校验和）
• "It's not that I dislike other databases, they're great. But SQLite is so easy to use and, more importantly, it's simple. Simplicity leads to reliability and I don't know of a more reliable database than SQLite."（fly.io btree 文）
• "SQLite does not compete with client/server databases. SQLite competes with fopen()."（whentouse.html）
• "If many threads and/or processes need to write the database at the same instant (and they cannot queue up and take turns) then it is best to select a database engine that supports that capability... SQLite only supports one writer at a time per database file."（whentouse.html）

4.3 交叉验证中发现的细节

• 官方 wal.html 与 Fly.io 文一致：数据库头字节 18/19（写/读版本）为 1=回滚日志、2=WAL；老版本 SQLite 打开 WAL 库会报 "file is encrypted or is not a database"——用版本号挡住不懂 WAL 的恢复逻辑。
• Fly.io wal 文的帧头 hexdump（00000002 00000002 ...）与 fileformat2 §4.1 帧头表逐字段对上：页号、提交后库大小（仅 commit 帧≠0）、salt×2（从 WAL 头复制，用于识别 WAL 重置后的陈旧帧）、累积校验和×2。
• 官方文档 2026 年仍在新内容：wal.html 新增"WAL-reset bug"一节——3.7.0~3.51.2 存在一个多连接并发写/checkpoint 的紧时序竞态，可致库损坏，3.51.3（2026-03-13）修复，回移至 3.44.6/3.50.7；官方称野外发生率"低于 SSD 故障/宇宙射线水平"，且开发者无法在实验室自然复现，只能加测试钩子触发。

4.4 本地实证（本次执行，非引用）

环境：Windows 10（10.0.26200），Python 3.12.12，bundled SQLite 3.50.4（注意：落在 WAL-reset bug 影响区间 3.7.0–3.51.2 内）。命令：python -I sqlite_wal_verify.py（脚本建于工作区，库文件建于其 wal_demo 子目录）。输出摘录：

[1] default journal_mode      : delete
[2] PRAGMA journal_mode=WAL   : wal
[3] wal_autocheckpoint default: 1000 pages          ← 与官方文档一致
[4] db header magic           : b'SQLite format 3\x00'
[5] header bytes 18/19        : 2 2 (1=rollback, 2=WAL)  ← 与两来源一致
[6] page size at offset 16    : 4096 bytes
[7] -wal file size            : 12392 bytes  = 32B 头 + 3×(24B 帧头+4096B 页数据)
[8] WAL magic                 : 377f0682      ← 小端校验和变体
[9] WAL format version        : 3007000       ← 16 年未变的格式版本
[11] salt-1 / salt-2          : 0xd337a56c / 0x81ebf01b
[12] frame#1: page number: 1 | db size after commit: 0 | salts copied: True
[13] reopen -> journal_mode   : wal (WAL 模式跨重连持久)

两个超出预期的实证收获：(a) [3] 直接验证 autocheckpoint 默认值 1000 页；(b) [12] 中第 1 帧的 commit 字段为 0——当场实证了"commit 标记只出现在事务最后一帧、前面帧该字段为 0"的事务边界机制（1 个 CREATE TABLE 事务写 2 帧 + 1 个 INSERT 事务写 1 帧，共 3 帧 = 实测文件大小 12392 字节精确吻合）。

5. 结论

1. WAL 是 SQLite 并发与性能的分水岭：一次反转（旧页保护 → 新页追加）同时换来了顺序写、更少 fsync、读写并存三大收益；读者靠 end-mark 各自持有快照，写者单线程追加，checkpoint 负责收敛。工程代价集中在一处——共享内存依赖（同机、非网络盘）与 checkpoint 饥饿风险。
2. B+ 树 + 定长页是"大库快查"的全部秘密：数据组织成以 rowid 为键的表树和任意键的索引树，树高 3–4 层即覆盖 GB–TB 级数据；sqlite_schema 固定在页 1 使"打开库"变成一次 O(1) 的元数据寻址。
3. "最广泛部署"是一个生态位命题而非性能命题：SQLite 赢在把自己定位成"更好的 fopen()"——零管理、单文件、离线可靠、嵌入一切设备；它明确放弃多写者并发与跨网络场景，换取在数十亿端侧设备上的不可替代性。简单性（130KLOC）是它敢承诺"never corrupt"的资本。
4. 可靠性文化有其边界：2026 年披露的 WAL-reset bug 表明，即便在以测试强度著称的项目里，紧时序竞态也可能潜伏 16 年。

6. 局限

• "1 万亿数据库"是数量级估算：官方自己承认 "Precise numbers are difficult to obtain"，由手机保有量 × 每机库数推算；"仅次于 libz"也是 "best guess" 加评论者推测（statically linked 使每机多实例）。引用时应作量级而非精确值。
• 来源视角偏"规范与讲解"，未读实现：未精读 btree.c/wal.c 源码与 arch.html（VFS/pager 分层），对"锁如何升级、busy retry 如何实现"只有机制级理解。Fly.io 系列是 2022 年文章，个别数字（如树高算术、内部页 500 条目）是按典型记录长度的估算，非硬保证。
• 性能主张多为定性："significantly faster in most scenarios" 无基准数字；1–2% 的只读场景劣势是官方唯一给出的量化。checkpoint 开销、大事务行为等只有描述性说明。
• 我未做的验证：高并发读写时序、checkpoint 饥饿复现、WAL-reset bug 触发（需要多连接精确竞态）；varint/记录格式的逐字节解码实证也未做。本机 SQLite 3.50.4 处于 WAL-reset bug 影响区间，官方评估野外风险极低，但生产环境值得确认版本 ≥3.51.3 或已回移补丁。
• 网络依赖：本次联网成功，全部结论来自在线精读的 6 个来源 + 本地实证，不存在"仅凭已有知识"的部分；但 Fly.io 文章作者署名在不同渠道不一致（wal 一篇普遍署名 Ben Johnson，btree 一篇检索结果有异说），笔记按系列归属 Fly.io 处理。

7. 对我的启发

1. 选型先问生态位，再问性能："SQLite competes with fopen()" 是本主题最值得带走的一句话。给我自己的项目（Agent 记忆、工具状态、本地数据集）做存储决策时，先判断数据是否与应用同机、写并发是否低——是，则 SQLite+WAL 几乎总是对的；跨网络/多写者才升级 C/S。
2. 追加式日志是并发与性能的通用杠杆：WAL 的套路（原数据不动 + 变更追加 + 定期合并回写 + 快照读）与 LSM-tree、Kafka、Redis AOF、Raft log 同构；其中"读事务记住 end-mark 就是 MVCC 的最小实现"，理解了 SQLite 的 WAL，就拿到一把理解所有写前日志系统的钥匙。
3. 学存储系统要下到字节：fileformat2.html 证明"把格式定义到偏移量"才能真正可验证；我这次的 13 项实证（尤其是帧 commit 字段=0 的意外发现）比读十篇二手解读更踏实。以后读任何存储引擎，都值得写一个 hexdump 脚本对照规范。
4. 简单性是可靠性的前提，也是约束设计：130KLOC 做到 95% 的功能，靠的是明确放弃（多写者、网络盘、改 page_size）。做系统设计时，"列出我不做什么"和"列出我做什么"同样重要——官方 whentouse 页就是一份模板。
5. 警惕长读事务：checkpoint starvation 是 WAL 模式最现实的坑（监控 WAL 文件大小、给读者留间隙、必要时用 RESTART/TRUNCATE checkpoint），这条可以直接进生产 checklist。

附：来源链接汇总

1. https://www.sqlite.org/wal.html （WAL 官方文档，2026-08-25 更新，含 WAL-reset bug）
2. https://www.sqlite.org/fileformat2.html （文件格式规范：页/B-tree/记录格式/WAL 格式）
3. https://www.sqlite.org/mostdeployed.html （部署量论证）
4. https://www.sqlite.org/whentouse.html （适用场景与生态位）
5. https://fly.io/blog/sqlite-internals-wal （Fly.io：WAL 内幕，帧格式/shm 哈希索引）
6. https://fly.io/blog/sqlite-internals-btree （Fly.io：页与 B-tree，hexdump 实证）