从零构建最小关系型数据库：B树索引、WAL日志与查询解析器

从零构建一个最小关系型数据库是一个极具教育意义的工程实践。它不仅能帮助开发者深入理解数据库系统的内部机制，还能揭示存储、索引和查询优化的本质。本文聚焦于三个核心组件：B 树索引、WAL 日志和查询解析器。通过这些组件的实现，我们可以构建一个支持基本 CRUD 操作的单表数据库，支持有限的 SQL 语法，并在内存与磁盘间高效管理数据。不同于商业数据库的复杂性，我们的实现强调简洁性和可落地性，适用于学习和原型开发。

B 树索引：高效数据检索的基础

B 树（B-Tree）是关系型数据库中标准索引结构的设计核心，尤其适合磁盘存储环境。其核心观点是：通过平衡的多叉树结构，实现 O (log n) 时间复杂度的搜索、插入和删除操作，同时最小化磁盘 I/O 次数。在构建最小数据库时，B 树用于组织表数据和索引，确保主键查询的快速定位。

证据来源于经典的数据库教程，如 SQLite 的实现原理。B 树将数据分解为固定大小的页（通常 4KB），每个页作为一个节点。根节点指向子节点范围，内部节点存储键值用于路由，叶子节点存储实际数据。对于一个 n 键的 B 树，高度通常不超过 4-5 层，即使存储 TB 级数据也能高效检索。例如，在一个分支因子为 100 的 B 树中，3 层即可容纳 100 万条记录，只需 2 次磁盘读取即可定位。

可落地参数与清单：

• 页大小：设置为 4096 字节，匹配常见文件系统块大小。每个页包含页类型（内部 / 叶子）、键数、子指针和键值对。
• 节点容量：内部节点最多容纳 m-1 个键（m 为阶数，建议 m=512，确保至少 m/2 键以保持平衡）。叶子节点类似，但存储完整行数据。
• 实现步骤：
  1. 定义页结构：使用结构体存储页头（类型、键数）、键数组和值指针。
  2. 搜索操作：从根页开始，二分查找键范围，递归到叶子。伪代码：find_leaf(key) 通过父指针导航。
  3. 插入：定位叶子，若满则分裂（split_node），向上传播更新父节点键。分裂阈值：键数 > 最大容量时触发。
  4. 删除：合并或借键，保持平衡。监控阈值：键数 < 最小容量时处理。
• 优化点：使用游标（cursor）抽象层，支持范围扫描。初始根页为叶子，插入第一条记录后分裂为内部根。
• 风险控制：避免深度递归，使用迭代实现搜索；磁盘页缓存上限设为 100 页，LRU 淘汰。

通过这些参数，一个简单的 B 树索引可在单机上支持 10 万 + 条记录的快速查询，证明了其在最小数据库中的实用性。

WAL 日志：保障事务持久性和崩溃恢复

WAL（Write-Ahead Logging）是事务性数据库的耐久性基石。其观点是：在应用变更到主数据结构前，先将变更日志追加到持久化文件中，确保即使崩溃也能回放日志恢复一致性。这避免了直接覆盖旧页的风险，支持原子提交。

在 SQLite 等系统中，WAL 通过日志文件记录所有修改，提交时 fsync 确保日志持久化。证据显示，WAL 允许读写并发：读者访问旧检查点，写者追加到 WAL，减少锁竞争。崩溃后，重放 WAL 日志应用未完成变更，恢复时间 O (日志大小)，远优于全扫描。

可落地参数与清单：

• 日志格式：WAL 文件以二进制追加模式，每条日志记录包括事务 ID、页号、旧页校验和、新页内容。头帧记录 WAL 版本和检查点。
• 提交阈值：每 1000 条变更或 1MB 日志后 fsync 一次。检查点阈值：WAL 大小 > 数据库大小时，应用日志到主文件并清空 WAL。
• 实现步骤：
  1. 初始化：创建 WAL 文件，预分配 1MB 空间。
  2. 写操作：修改 B 树页前，追加 “预写” 日志（旧页快照），然后修改页，最后追加 “提交” 帧。
  3. 事务管理：BEGIN 事务时标记日志起点，COMMIT 时 fsync WAL 并更新检查点。ROLLBACK 回放日志逆操作。
  4. 恢复：启动时扫描 WAL，从检查点应用日志，校验和验证完整性。
• 并发参数：单写线程追加日志，多读线程从主文件或 WAL 快照读。锁粒度：WAL 尾部互斥锁。
• 风险控制：日志轮转上限 2GB，避免单文件过大；使用校验和（CRC32）检测损坏，回滚策略：丢弃无效事务。

在最小数据库中，WAL 确保了 ACID 的 D（Durability），即使电源故障也能恢复 99.9% 数据，极大提升可靠性。

查询解析器：从 SQL 到执行的桥梁

查询解析器将用户 SQL 转换为可执行指令，其观点是：通过分层处理（词法分析、语法分析、代码生成），实现有限 SQL 的支持，而不需完整编译器。针对最小数据库，我们聚焦简单语句如 INSERT、SELECT，支持单表无 JOIN。

证据来自 SQLite 前端：Tokenizer 分解 SQL 为令牌，Parser 构建抽象语法树（AST），Code Generator 产生虚拟机字节码。字节码如 OP_INSERT（参数：行数据）驱动后端 B 树操作。简单实现可处理 “SELECT * FROM table WHERE id=1”，避免复杂子查询。

可落地参数与清单：

• 支持语法：仅 CRUD，WHERE 限于等值主键。列类型：INT (4 字节)、TEXT (变长)。
• 解析深度：递归下降解析器，状态机处理令牌流。
• 实现步骤：
  1. Tokenizer：扫描 SQL 字符串，识别关键字（SELECT/INSERT）、标识符、数字、操作符。缓冲区大小：1KB。
  2. Parser：构建 AST 节点，如 Statement {type: SELECT, table: "users", where: Condition {col: "id", op: "=", val: 1}}。
  3. Code Generator：遍历 AST 生成字节码数组，例如 [OP_BEGIN, OP_FIND_BY_KEY (1), OP_RETURN]。
  4. 执行：虚拟机循环执行字节码，调用 B 树 API。栈大小：64 项，溢出报错。
• 优化点：预编译语句缓存字节码，参数绑定避免重复解析。错误处理：行号报告语法错。
• 风险控制：输入长度限 512 字符，防注入（虽简单，但转义引号）；测试覆盖率 > 90% 基本语句。

此解析器使数据库支持交互式查询，如 REPL 提示 “db>”，输入 SQL 后输出结果，提升用户体验。

集成与扩展建议

将三组件集成：查询经解析器生成字节码，VM 调用 B 树修改，变更经 WAL 持久化。整体架构：前端（解析器）→ VM → B 树 → Pager（页管理）→ WAL → OS。初始数据库文件：单页元数据（页数、根页 ID）。

扩展清单：

• 添加多表支持：字典映射表名到根页。
• 并发：读写锁于页级。
• 性能监控：日志 I/O 次数，阈值 > 1ms/page 时警报。
• 测试：单元测试插入 / 查询，集成测试崩溃恢复。

此最小数据库虽简单，却体现了核心原理：B 树优化检索，WAL 保障安全，解析器桥接用户。实际开发中，可用 C/Go 实现，代码量 < 5000 行。

资料来源：

• cstack.github.io/db_tutorial/ （SQLite 克隆教程，覆盖 B 树和解析器）
• Build Your Own Database From Scratch （书籍，Go 实现持久化和索引）