从SQL解析到B+树索引：C/C++实现miniSQL

简介：miniSQL 是浙江大学数据库设计课程的期末大程成果，面向希望从零理解关系数据库内部机制的高校学生与 C/C++ 开发者，可用于课程设计参考、数据库引擎入门及 SQL 执行流程学习。压缩包共 29 个文件、约 885KB，含 9 个 cpp、9 个 h、9 个 txt，以及 1 份 pdf 设计报告和 1 个 exe 可执行程序；源码覆盖 API、解释器、缓冲管理、记录管理、目录与 B+ 树索引等模块，报告记录项目目标、设计决策、实现细节、问题及测试结果。已有 1532 人学习下载。读者可直接运行 myMiniSQL.exe 验证建表、增删改查与索引操作，也可结合测试文件和源码梳理 SQL 语句从解析到执行的链路，理解 ACID、查询优化和索引结构在迷你数据库中的落地方式；报告与代码相互印证，便于复盘模块划分、接口设计和调试思路，同时可借助测试用例检查功能完整性，适合作为数据库课程项目与系统设计入门的实践样本。

1. 从一份期末大程说起：miniSQL 到底要交付什么

miniSQL 这类数据库期末大程，真正难的不是写一条CREATE TABLE，而是让 SQL 解析、记录管理、B+ 树索引和执行器在同一套页式存储上闭环。答辩现场最常被问的往往不是“B+ 树多难”，而是“为什么这条 SQL 走了全表扫”“删完记录后索引里为什么还能查到”。这套方案面向的是一份可运行的 C/C++ 单机数据库：支持建表、增删改查、建索引、按索引检索，最后用脚本跑通一致性验证。读者如果是做课程设计、毕设前期原型，或者想用 C++ 练一遍存储引擎，这套结构可以直接对照着搭；从业者也能把它当成一个最小数据库的模块划分参考。

2. 需求拆解与技术选型：为什么用 C/C++ 手写而不是套框架

2.1 功能边界：DDL、DML、索引三条主线

miniSQL 的功能边界要先钉死，不然后面每加一个语法都像在补漏。通常的做法是把需求拆成三条主线：DDL 负责表与索引的生命周期，DML 负责记录读写，索引负责加速等值与范围查询。三条主线共享同一套系统目录，任何一条没闭环，验收时都会露馅。

DDL 至少覆盖CREATE TABLE、DROP TABLE、CREATE INDEX、DROP INDEX。表定义里常见的字段类型是int、float、char(n)，约束至少支持主键、唯一、非空。DML 覆盖INSERT、DELETE、UPDATE、SELECT，SELECT先做单表，条件支持=、<>、<、<=、>、>=和AND，聚合与连接可以作为加分项，但不要在第一版塞进去。索引主线要求 B+ 树能跟着记录插入、删除、更新同步维护，并且能回答两类问题：等值查找和范围扫描。

这里有个容易被忽略的边界：索引不是“建完就完事”，它要和记录管理器共享 RID。RID 通常由页号加槽号组成，记录一旦搬家，索引里的 RID 就失效。所以需求里要明确一条：变长字段更新导致记录重分配时，索引必须同步更新，或者干脆限制更新只改定长部分。我一般会在需求文档里写一句“首版不支持更新主键”，能省掉大量边界讨论。

功能边界还要写清楚“不做什么”。比如不做完整事务、不做多表连接、不做并发控制，这些不是偷懒，而是把验收范围收窄。课程设计最怕的是功能列表很长，现场一跑就崩。把单表 CRUD、索引维护、错误提示做扎实，比堆十个半成品算子更有说服力。

2.2 技术选型：C++11 及以上 + 页式文件 + 手写 B+ 树的取舍

用 C/C++ 实现 miniSQL，核心取舍在“自己写到哪一层”。用现成的 SQLite 当然快，但课程设计要展示的是存储、索引、执行器的连接关系，套壳就失去意义。用第三方 B+ 树库也不合适，索引维护本身就是答辩重点。比较稳的选型是：C++11 及以上、标准库容器做内存结构、文件 I/O 自己封装成页式存储、B+ 树手写。

页大小通常取 4KB，和大多数文件系统块大小对齐，调试时也容易按页号定位。缓冲池用 LRU 替换，每个页框记录 pin 计数和脏页标记。B+ 树的阶数不写死，按页大小和 key 长度算出来：内部节点存n个 key 和n+1个孩子指针，叶子节点存 key 与 RID 列表。这样换页大小或换 key 类型时不用改树结构。

为什么不直接用std::map做索引？内存索引跑测试很快，但一关机就没了，而且无法展示页分裂、节点合并这些过程。课程设计要的是“能落盘、能恢复、能解释清楚”。手写 B+ 树还有一个好处：你能在答辩时画出一次插入分裂前后的页布局，这比背概念管用。

工程上建议用 CMake 或 Makefile 统一构建，Debug 构建开-O0 -g，Release 构建开-O2。测试 SQL 放在test/sql/下，期望输出放在test/expected/下，跑完用 diff 比对。这个习惯后面验收章还会展开。

2.3 工程约束：构建、调试与可复现环境

miniSQL 这种项目，代码量不大但模块多，最容易翻车的地方是“本机能跑，换台机器就崩”。血泪经验是：从第一天就把构建脚本和测试脚本写进仓库，不要等到答辩前才补。目录可以按下面这样分，头文件和源文件分开，测试数据独立存放：

miniSQL/ ├── CMakeLists.txt ├── include/ │ ├── parser/ # 词法、语法、AST │ ├── catalog/ # 系统目录与元数据 │ ├── storage/ # 页、缓冲池、记录管理 │ ├── index/ # B+ 树 │ └── executor/ # 算子与执行计划 ├── src/ ├── test/ │ ├── sql/ # 回归 SQL 脚本 │ └── expected/ # 期望输出 └── tools/ └── check_index.cpp # 索引与记录一致性检查

构建脚本里至少有两个目标：miniSQL主程序和check_index校验工具。主程序负责交互式输入和脚本输入，校验工具负责扫表比对索引项。参数上，数据库文件路径、页大小、缓冲池页数都从命令行或配置文件读，不要硬编码在源码里。这样答辩时换一个数据目录就能重跑，不用改代码重新编译。

调试阶段建议开 AddressSanitizer 和 UBSan，尤其是解析器和记录序列化部分。很多“玄学崩溃”其实是越界读或未初始化内存，普通 gdb 不一定能立刻定位。把-fsanitize=address,undefined加进 Debug 构建，跑一遍回归脚本，能提前发现一批问题。

3. 总体架构与存储层设计：六个模块如何各管一段

3.1 分层架构与调用链

miniSQL 的调用链可以按“SQL 进来、结果出去”来切：Parser 把文本变成 AST，Analyzer 查系统目录做语义检查，Planner 生成执行计划，Executor 调算子，算子通过 Record Manager 读写记录，Record Manager 通过 Buffer Pool 拿页，Buffer Pool 最终落到 Disk Manager。Index Manager 横在 Executor 和 Record Manager 之间，负责索引项的增删查。

这张表建议贴在项目 README 里，答辩时按调用链讲，比按文件讲清楚得多。模块之间的依赖要单向：Executor 依赖 Record/Index，Record 依赖 Buffer，Buffer 依赖 Disk，Catalog 被 Parser 之后的 Analyzer 和 Executor 使用。不要让 Buffer Pool 反向调用 Executor，否则后面加功能会缠成一团。

3.2 页式存储与缓冲池管理

页是磁盘和内存之间的最小单位。一个页里通常放页头、槽目录和记录数据。页头记录页类型、槽数量、空闲空间偏移、下一条页号；槽目录存每条记录的偏移和长度；记录数据从页尾向前长。删除记录时只把槽标记为空，空间留给后续插入复用。

// 页头结构：固定在页起始位置，字段按 4 字节对齐 struct PageHeader { uint16_t page_type; // 0=数据页, 1=索引页, 2=目录页 uint16_t slot_count; // 当前槽数量 uint16_t free_offset; // 空闲区起始偏移，从页尾向前增长 uint16_t free_space; // 剩余连续空闲字节数 int32_t next_page; // 下一条页号，-1 表示无 int32_t prev_page; // 上一条页号，-1 表示无 }; // 槽目录项：记录在页内的位置 struct Slot { uint16_t offset; // 记录起始偏移 uint16_t length; // 记录长度 uint8_t flags; // 0=空槽, 1=有效, 2=已删除 };

free_offset和free_space要一起维护：插入时从空闲区分配，删除时把槽置为已删除但不立即合并，等页内碎片超过阈值再做一次紧凑化。紧凑化会移动记录位置，所以必须同步更新槽目录和索引里的 RID；如果首版不想处理这个复杂度，可以只做“删除后空间复用”，不移动已有记录。

缓冲池的核心是 pin 计数。fetchPage(page_id)先查页表，命中就把 pin 加一返回；未命中就找一个未 pin 的页框，脏页先刷盘，再从磁盘读入。unpinPage(page_id, is_dirty)把 pin 减一，脏标记或上去。pin 计数大于零的页不能被替换，这是保证执行器持有页指针期间页不被换出的底线。

提示：缓冲池页数不要设得太小。测试脚本一次扫几万行时，页数太小会频繁刷盘，跑起来像卡死。可以先设 128 到 256 个页框，再根据机器内存调。

3.3 系统目录与元数据表

系统目录是 miniSQL 的黑匣子，表存不存在、列什么类型、索引建在哪些列上，都靠它回答。首版可以用固定的系统表来存元数据，比如__tables、__columns、__indexes，启动时加载到内存，DDL 变更后写回。这样比直接序列化 C++ 结构更稳，调试时也能用 SQL 查。

struct ColumnMeta { std::string table_name; std::string column_name; uint8_t type; // 0=int, 1=float, 2=char uint16_t length; // char(n) 的 n，其他类型为固定长度 bool not_null; bool is_primary; }; struct IndexMeta { std::string index_name; std::string table_name; std::vector<std::string> columns; // 首版建议单列索引 bool is_unique; int32_t root_page; // B+ 树根页号 };

root_page很关键。B+ 树分裂时根可能变化，索引元数据要跟着更新；如果只在内存里维护根页号，进程一退出索引就找不到了。建索引时先扫表拿 RID，再批量插入 B+ 树，比逐条INSERT触发索引维护更快，也更容易做失败回滚。

3.4 记录组织与变长字段处理

记录组织要解决两个问题：一条记录怎么序列化，以及删除后空间怎么复用。定长字段直接按偏移写，变长char(n)可以在记录头里存长度，后面跟实际字节。记录头建议带一个 null bitmap，非空约束在插入前检查，不依赖存储层报错。

// 记录布局：记录头 + null bitmap + 定长/变长字段数据 // 记录头里存字段数量和总长度，便于反序列化 struct RecordHeader { uint16_t field_count; uint16_t record_size; uint8_t null_bitmap[2]; // 最多支持 16 个字段，按需扩展 };

更新变长字段是经典坑：新值比旧值长，当前槽放不下，只能删旧记录、插新记录，再更新所有索引里的 RID。这个动作不是原子的，中途失败会出现“记录没了、索引还在”。首版的稳妥做法是限制UPDATE只改定长字段，或者把变长字段更新走“删除 + 插入”并加一致性校验工具。不要让执行器悄悄搬家却不通知索引。

4. 核心模块实现：从 SQL 解析到执行器与索引

4.1 词法语法分析与 AST 设计

词法和语法可以手写递归下降，不必上 parser generator。miniSQL 的语法子集不大，手写反而容易控制错误位置。Token 类型覆盖关键字、标识符、数字、字符串、比较符、逗号和括号。Parser 对外只暴露一个parse，内部按语句类型分派到parseCreate、parseInsert、parseSelect等函数。

enum class TokenType { KEYWORD, IDENT, NUMBER, STRING, EQ, NE, LT, LE, GT, GE, COMMA, LPAREN, RPAREN, SEMI, END }; struct Token { TokenType type; std::string text; size_t pos; // 在原始 SQL 中的位置，报错时带上 }; // AST 基类，所有语句节点继承它 struct Statement { virtual ~Statement() = default; virtual std::string name() const = 0; }; struct CreateTableStmt : Statement { std::string table; std::vector<ColumnDef> columns; std::string name() const override { return "CreateTable"; } };

pos字段是我强烈建议保留的。解析失败时输出“第 12 个字符附近期望)”，比只报“语法错误”好排查得多。AST 节点用std::unique_ptr管理，避免手写 delete。语义分析阶段再查 Catalog，确认表存在、列类型匹配、主键不重复定义；这些检查放在 Parser 里会让解析器变重，放在 Analyzer 里更合适。

4.2 执行器与算子流水线

执行器用火山模型，每个算子实现open、next、close。next返回一行或结束标记。SeqScan扫记录页，IndexScan调 B+ 树范围扫描拿 RID 再回表，Filter做谓词判断，Project选列，Insert、Delete、Update调 Record Manager 和 Index Manager。算子之间用std::unique_ptr<Executor>串起来。

class Executor { public: virtual ~Executor() = default; virtual void open() = 0; // 返回 true 表示取到一行，row 里是列值和 RID virtual bool next(Row &row) = 0; virtual void close() = 0; }; class IndexScan : public Executor { public: IndexScan(IndexManager *idx, RecordManager *rec, const std::string &index_name, const Range &range) : idx_(idx), rec_(rec), index_name_(index_name), range_(range) {} void open() override { // 先拿到索引项迭代器，再逐条回表 iter_ = idx_->rangeScan(index_name_, range_); } bool next(Row &row) override { RID rid; if (!iter_->next(rid)) return false; return rec_->getRecord(rid, row); // 回表读完整记录 } void close() override { iter_.reset(); } private: IndexManager *idx_; RecordManager *rec_; std::string index_name_; Range range_; std::unique_ptr<IndexIterator> iter_; };

IndexScan的关键是“索引项只存 key 和 RID，回表再取完整行”。如果查询只涉及索引列，可以做覆盖索引直接返回，省掉回表；首版不做也没关系，但要在执行计划里说明。open里拿迭代器，close里释放，异常路径也要保证close被调用，否则缓冲池的 pin 会泄漏。

4.3 B+ 树索引的插入删除与范围扫描

B+ 树的节点分内部节点和叶子节点。内部节点存 key 和孩子页号，叶子节点存 key 和 RID 列表，叶子之间用next指针串起来做范围扫描。阶数按页大小算：max_keys = (page_size - header_size) / (key_size + ptr_size)。插入时从根往下找到叶子，插进去；满了就分裂，把中间 key 提上去。删除时先删叶子项，低于半满再尝试借位或合并。

// B+ 树叶子节点：key 与 RID 列表，next 指向下一条叶子页 struct LeafNode { PageHeader header; uint16_t key_count; int32_t next_leaf; // 范围扫描用 // 后面紧跟 key_count 个 Key 和对应的 RID 列表 }; // 查找：返回第一个 >= key 的位置，供等值和范围扫描复用 int LeafNode::lowerBound(const Key &key, const KeyComparator &cmp) { int lo = 0, hi = key_count; while (lo < hi) { int mid = (lo + hi) / 2; if (cmp(getKey(mid), key) < 0) lo = mid + 1; else hi = mid; } return lo; }

非唯一索引要把同一个 key 的多个 RID 挂在叶子项上，或者把 RID 拼进 key 里保证唯一。前者查询时遍历 RID 列表，后者实现简单但 key 变长。课程设计里建议用“key + RID 列表”，并在删除时按 RID 精确删除，避免误删同 key 的其他记录。范围扫描从lowerBound开始，沿next_leaf往后走，直到超过上界。

4.4 简单查询优化与执行计划输出

首版不追求复杂优化，但要有“索引选择”规则：等值条件命中索引列就走IndexScan，范围条件命中索引列也走IndexScan，否则走SeqScan。多个条件用AND连接时，选过滤性最强的索引，其余条件留给Filter。这条规则用一张小表就能说清楚。

执行计划要能打印出来，答辩时直接EXPLAIN SELECT ...展示走没走索引。实现上可以在 Planner 里生成计划树，每个节点带type和cost估算；cost 不用很准，能比较“全表扫页数”和“索引扫描预估行数”即可。不要为了优化而优化，先把计划打印和索引选择做对，再考虑谓词下推。

5. 避坑与排查：最容易翻车的五件事

5.1 页内空闲空间与记录迁移

现象：更新一条char(100)字段后，原来能查到的记录突然查不到，或者索引扫描返回旧值。原因通常是新记录比旧槽长，页内放不下，记录被搬到另一页，但索引里的 RID 没更新。解决方式有两种：一是更新前判断新长度，超过旧槽就删旧插新，并在同一个执行器事务里更新所有索引；二是首版限制变长字段更新，只允许改定长字段。无论选哪种，都要在UPDATE路径上打日志，记录旧 RID 和新 RID。

5.2 索引与记录不一致

现象：SELECT走索引查出一条已经删除的记录，或者全表扫能查到、索引查不到。原因多半是删除顺序不对：先删了记录，再删索引，中途异常退出；或者索引删除时按 key 删，误删了同 key 的其他 RID。解决方式是固定维护顺序，插入时先写记录再插索引，删除时先删索引再删记录，并在check_index工具里做全量比对。工具逻辑很简单：扫全表建 RID 集合，扫索引建另一个集合，两边差集打印出来。

5.3 事务缺失下的并发写

现象：测试脚本并发插入时偶发页损坏，或者缓冲池里同一页被两个线程同时改。原因是没有事务和锁，页的 pin/unpin 不是线程安全的，B+ 树分裂时父节点和子节点也没加锁。课程设计通常默认单线程，但测试脚本可能用多进程跑。解决方式是在文档里明确“单线程执行”，或者在表级加读写锁，缓冲池的页表加互斥量。不要假装支持并发却不加锁，答辩时被问一句“两个客户端同时插入怎么办”就会露馅。

5.4 内存泄漏与异常路径

现象：跑十万行插入后内存持续上涨，或者解析一条错误 SQL 后进程越来越慢。原因常见于 AST 节点手动new没delete、异常抛出后缓冲池页没unpin、B+ 树迭代器没释放。解决方式是用std::unique_ptr管理 AST 和算子，缓冲池用 RAII 封装PageGuard，构造时fetchPage，析构时unpinPage。调试时开 AddressSanitizer，跑一遍错误 SQL 回归集，泄漏点会直接打出来。

5.5 测试数据与边界条件

现象：本地测试全过，答辩现场换一组数据就崩。原因通常是只测了“正常路径”：空表、char超长、int溢出、重复主键、删除不存在的行、索引列为NULL。解决方式是准备一组边界 SQL，每次改完存储或索引都跑一遍。测试集至少覆盖：空表扫描、单页插满、跨页插入、删除后复用槽、索引分裂、索引合并、范围扫描边界。跑完用 diff 比对期望输出，别靠肉眼。

6. 验收与答辩：用一套可复现的测试脚本说话

验收时最怕“演示到一半卡住”。我一般会把验收拆成固定脚本，按顺序跑，每步都有期望输出。下面这个脚本结构可以直接改成自己的：

#!/usr/bin/env bash set -e DB=./build/miniSQL rm -rf /tmp/minisql_test && mkdir -p /tmp/minisql_test # 1. 建表与插入 $DB --db /tmp/minisql_test --file test/sql/01_create_insert.sql \ > /tmp/out1.txt diff /tmp/out1.txt test/expected/01_create_insert.out # 2. 无索引查询与执行计划 $DB --db /tmp/minisql_test --file test/sql/02_seq_scan.sql \ > /tmp/out2.txt diff /tmp/out2.txt test/expected/02_seq_scan.out # 3. 建索引后走 IndexScan $DB --db /tmp/minisql_test --file test/sql/03_index_scan.sql \ > /tmp/out3.txt diff /tmp/out3.txt test/expected/03_index_scan.out # 4. 删除后一致性校验 $DB --db /tmp/minisql_test --file test/sql/04_delete.sql > /tmp/out4.txt diff /tmp/out4.txt test/expected/04_delete.out ./build/check_index /tmp/minisql_test

脚本只做三件事：跑 SQL、比对输出、跑一致性校验。--db指定数据目录，--file指定 SQL 文件，输出重定向到临时文件再 diff。check_index返回非零就说明索引和记录不一致，现场直接暴露问题，比口头解释可信。

答辩演示顺序也有讲究：先建表插入，跑一条无索引查询并EXPLAIN展示全表扫；再建索引，跑同一条查询展示IndexScan；接着做范围查询和删除，最后跑check_index。这套顺序能把“为什么需要索引”讲清楚，也能自然带出 B+ 树分裂和 RID 回表。老师常问的三个问题提前准备：页大小为什么选 4KB、B+ 树分裂时根节点怎么变、索引选择规则在什么情况下会选错。答不上来的细节不要编，直接说“首版按单列索引处理，多列索引在扩展点里”。

从那以后我每次带这类课程设计，都强制先写验收脚本再写功能，跑不通就不往下加模块。希望帮到你。

本文还有配套的精品资源，点击获取