SQLite 内核

世界上部署最广的数据库引擎——SQL 编译器 + VDBE 虚拟机 + B-Tree 存储 + Pager 层。

概念

SQLite 是一个嵌入式关系数据库，整个数据库是一个单一的 .db 文件。它的”内核”是一套精巧的分层架构：SQL 文本进入，经过词法/语法分析 → 字节码生成 → 虚拟机执行 → B-Tree 操作 → Pager 缓存 → OS 文件 I/O。SQLite 是”如何用纯 C 构建一个工业级引擎”的最佳教材。

核心组件

组件	职责	关键特征
Tokenizer	词法分析: SQL 字符串 → token 流	手写词法分析器, 无 yacc/lex
Parser	语法分析: token 流 → AST (语法树)	Lemon LALR(1) 解析器生成
Code Generator	AST → VDBE 字节码	语义分析 + 优化合并
VDBE	字节码虚拟机: 执行 SQL 操作指令	类似汇编语言的 200+ 条操作码
B-Tree	数据组织: 每表一个 B-Tree, 每个索引一个 B-Tree	变长页面 (512~65536 字节)
Pager	页面缓存 + WAL 日志 + 事务锁	LRU 淘汰策略
OS 抽象层	平台无关 I/O: 文件读写, 锁, 内存映射	VFS (Virtual File System)

SQL 编译流水线

SQL: "SELECT name FROM users WHERE age > 18 ORDER BY name"

    |        Tokenizer (tokenize.c)
    v
Tokens: SELECT, name, FROM, users, WHERE, age, >, 18, ORDER, BY, name

    |        Parser (parse.y → parse.c by Lemon)
    v
AST: SelectStmt
       ├── columns: [Expr(ColumnRef "name")]
       ├── from: [SrcTable "users"]
       ├── where: BinaryExpr(">", ColumnRef "age", Integer 18)
       └── orderBy: [OrderBy(ColumnRef "name", ASC)]

    |        Code Generator (select.c, where.c)
    v
VDBE Bytecode:
    0:  Init       0, 15, 0
    1:  OpenRead   0, 2, 0       // 打开 users 表 (cursor 0)
    2:  OpenRead   1, 3, 0       // 打开排序索引 (cursor 1)
    3:  Rewind     0, 10, 0      // 移到表头
    4:    Column   0, 2          // 读取 age 列
    5:    Ge       18, 9         // age >= 18? 否跳转到9
    6:    Column   0, 1          // 读取 name 列
    7:    MakeRecord 1, 0        // 生成排序 key
    8:    IdxInsert 1, 0         // 插入排序索引
    9:  Next       0, 4          // 下一行, 跳回4
    10: Close      0, 0
    11: Sort       1, 14
    12:   Column   1, 0
    13:   ResultRow 0, 1
    14: Next       1, 12
    15: Halt       0, 0

VDBE 虚拟机

// VDBE 执行循环 (sqlite3VdbeExec 简化)
struct Vdbe {
    Op *aOp;           // 字节码指令数组
    Mem *aMem;         // 内存寄存器数组
    int pc;            // 程序计数器
    Cursor *aCursor;   // B-Tree 游标 (表的"指针")
};
 
// 每条指令有 5 个操作数: P1, P2, P3, P4, P5
// 例如: OpenRead P1=cursor_id, P2=root_page, P3=opflags, P4=table_name

B-Tree 存储层

表 "users" 的内部存储:
    B-Tree 根页 (Table 1, Root Page 2):
        Interior Page (内部节点, 存储 key + 子页指针):
            [key: 100, child: page3] [key: 200, child: page4] [key:300, child: page5]

        Leaf Page (叶子节点, 存储实际数据):
            [Cell 0: rowid=100, payload=(name:"Alice", age:22)]
            [Cell 1: rowid=101, payload=(name:"Bob",   age:35)]
            ...

索引 "idx_users_age" 的 B-Tree:
    Leaf Page:
        [Cell 0: key=(age:18, rowid:105)]
        [Cell 1: key=(age:22, rowid:100)]
        ...

Pager 层 + WAL

传统回滚日志 (Rollback Journal):
    写事务前复制旧页到 journal 文件
    提交时删除 journal
    崩溃恢复时回滚 journal

WAL (Write-Ahead Log):
    写操作不直接修改主数据页
    而是追加到 WAL 文件末尾
    读操作首先检查 WAL 中是否有更新
    达到 checkpoint 阈值后合并 WAL 到主数据文件

WAL 优势:
    读写不互斥 (reader 不阻塞 writer)
    写入顺序追加 (磁盘友好)
    崩溃恢复简单 (只收尾 WAL)

---