miniSQL源码拆解：SQL解析、B+树索引与缓冲池实践

简介：miniSQL 是浙江大学数据库设计课程的期末大程成果，面向数据库课程学习者、课程设计参考者及希望理解关系数据库内核的 C/C++ 开发者。压缩包共 29 个文件、约 885KB，包含 9 个 cpp 与 9 个头文件组成的源码、9 个 txt 测试/说明文件、1 份 PDF 设计报告和 1 个可直接运行的 exe，便于从代码、文档到可执行程序完整对照学习。已有 1532 人学习下载。源码覆盖 SQL 语句解析执行、缓冲管理、记录管理、索引与 B+ 树、Catalog 等模块，能观察关系数据模型、ACID 属性、查询优化等理论在系统中的落地方式；配合设计报告可梳理项目目标、设计决策、实现细节、问题解决和测试结果，测试文件与可执行程序则方便验证查询、更新及并发场景下的功能表现，适合课程设计复盘与数据库内核入门参考。

1. 从一条 create table 说起：这套 miniSQL 到底能干什么

第一次拿到这份 miniSQL 源码，我把它当成只能跑select的课堂玩具，直到把页大小从 4KB 改成 8KB，再打开旧数据目录，整个索引文件直接读不出来。那一刻我才认真看它：这套用 C/C++ 写的迷你数据库，体量不大，但缓冲池、B+ 树索引、记录管理、SQL 解析几层是真按数据库的方式在分工，不是把数据往文件里一扔了事。

它适合两类人。一类是想把课堂上的数据库原理落成可调试代码的开发者，另一类是正在做数据库课程设计、需要一份能跑通建表、增删改查、索引和执行器参考实现的同学。全篇不吹架构，只讲我跑起来、改坏过、又修回来的那些地方。

2. 架构拆解：一条 SQL 从敲下回车到写进磁盘要过几道手

这份工程的规模不大，但分层意识很强。它没有把解析、执行、存储糊在一个main.cpp里，而是按数据库教科书的经典四件套切开了：解析层、系统管理（Catalog）、记录与索引管理、缓冲池与磁盘文件。理解这条链路，后面无论是调 bug 还是加功能，都能先定位到该动哪一层。

2.1 七层职责与调用链路

从控制台敲入一条语句算起，完整路径大致是这样：

这条链里有两个设计点值得单独拎出来说。

第一，执行器统一用迭代器模型。每个算子只暴露Open / Next / Close，Next返回一行，返回false就说明扫完了。这样做的好处是过滤、投影、索引扫描可以像积木一样叠起来，新加一个算子不用改上游代码。

第二，Catalog 是唯一的元数据来源。表有哪些列、每列什么类型、表的第一页是几号、这张表上挂了哪些索引，全部存在 Catalog 文件里，执行器不自己猜。很多同类工程把表结构硬编码在代码里，改一个字段要重编译，这个坑在二次开发时会很要命。

2.2 目录结构与各文件职责

工程目录基本能对上上面的分层，常见结构如下：

miniSQL/ ├── CMakeLists.txt ├── src/ │ ├── main.cpp # 入口：解析参数、建目录、起 REPL │ ├── common/ # 错误类型、类型定义、工具函数 │ ├── parser/ │ │ ├── lexer.cpp/.h # 词法 │ │ ├── parser.cpp/.h # 递归下降语法分析 │ │ └── ast.h # 语句对象定义 │ ├── catalog/ # 表、列、索引的元数据持久化 │ ├── record/ # 记录页格式、页内增删改查 │ ├── index/ # B+ 树节点、分裂合并、范围查找 │ ├── buffer/ # 页表、LRU 链表、脏页回写 │ └── executor/ # 各算子与语句分发 ├── test/ │ ├── cases/ # 按功能拆的 .sql 脚本 │ └── run_tests.sh └── data/ # 运行时生成：catalog、.dat、.idx

data/是运行期目录，不是源码目录，第一次跑之前可以不存在，程序启动时负责创建。这个细节看似小，实际上很多人的第一次翻车就发生在这里：目录没建、catalog 文件不存在、打开文件直接判失败然后解引用空指针。

2.3 构建方式与编译产物

工程一般用 CMake 管理，也见过用裸 Makefile 的分支，原理一样：把所有src/**/*.cpp编成可执行文件，链接时不需要额外依赖。常见要求是编译器支持 C++17，因为代码里会用到std::optional、std::variant这类东西来做类型和语句表达。

# 1. 准备编译环境（Debian/Ubuntu 系） sudo apt install build-essential cmake # 2. 配置 + 编译，Debug 版方便 gdb 跟栈 cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug cmake --build build -j"$(nproc)" # 3. 运行，参数是数据目录 ./build/minisql ./data

三个参数值得解释一下：-S .指定源码根目录，-B build把中间产物丢进build/不污染源码树，-DCMAKE_BUILD_TYPE=Debug打开-g -O0，调试时能看到真实行号。如果你的解析器是用 flex/bison 生成的，CMake 配置阶段会自动调用它们，机器上没装就会在 configure 阶段报flex not found，装上即可，不影响后续代码阅读。

3. 解析与执行：一条 SQL 是怎么被拆成算子的

解析层是这份工程里最容易读、也最容易被低估的部分。它没用 flex/bison 的也不少，手写递归下降反而更好改——加一个语句类型只要在词法里补关键字、在语法里加一个分支，不用重新生成代码。

3.1 手写词法：把 SQL 切成 token

词法器的职责非常单一：从左到右扫一遍字符串，吐出Token流。它要处理空白、--行注释、数字、字符串字面量、标识符和运算符。下面这段是我从工程里抽出来的核心结构：

// src/parser/lexer.cpp enum class Tok { END, IDENT, NUMBER, STRING, COMMA, LPAREN, RPAREN, STAR, EQ, LT, GT, LE, GE, NE, SEMI }; struct Token { Tok kind; std::string text; // 关键字也放这里，parser 层再区分 }; class Lexer { public: explicit Lexer(std::string sql) : src_(std::move(sql)), pos_(0) {} Token Next() { SkipSpace(); if (pos_ >= src_.size()) return {Tok::END, ""}; char c = Peek(); if (std::isalpha(c) || c == '_') return ScanIdentOrKeyword(); if (std::isdigit(c)) return ScanNumber(); if (c == '\'') return ScanString(); return ScanOperatorOrPunct(); // <= >= <> = < > , ( ) * ; } private: char Peek() const { return pos_ < src_.size() ? src_[pos_] : '\0'; } char Get() { return pos_ < src_.size() ? src_[pos_++] : '\0'; } void SkipSpace() { while (pos_ < src_.size()) { if (std::isspace(src_[pos_])) { pos_++; continue; } // -- 行注释，扫到换行结束 if (src_[pos_] == '-' && pos_ + 1 < src_.size() && src_[pos_ + 1] == '-') { while (pos_ < src_.size() && src_[pos_] != '\n') pos_++; continue; } break; } } std::string src_; size_t pos_; };

代码里几个参数的含义：src_持有整条语句，pos_是游标；Peek()不移动游标，专门给<=、>=、<>这种两字符运算符做前瞻用；ScanString里要处理''转义（SQL 里表示一个单引号）。Next()返回的text统一存原始字符，关键字识别放到 parser 层做，好处是词法不用背关键字表，加语句类型时改一处就够。

这里有个常被忽略的细节：字符串字面量必须以'结尾，扫到\0还没闭合就该立刻抛语法错误，而不是把整段内容当字符串返回。少了这个检查，用户输错一个引号，后面所有 token 都会乱掉，报错信息会指向一个八竿子打不着的位置，排起来非常痛苦。

3.2 AST 与语句分发

语法分析的产出是 AST。这份工程常见做法是不做泛型表达式树，而是按语句类型各建一个结构体，因为课程设计级别的 SQL 子集就那么多：

// src/parser/ast.h enum class StmtType { SELECT, INSERT, DELETE, UPDATE, CREATE_TABLE, DROP_TABLE, CREATE_INDEX, DROP_INDEX, EXIT }; struct Condition { std::string column; Tok op; // EQ / LT / GT / LE / GE / NE Value rhs; // 统一成一个 variant：int / std::string }; struct Statement { explicit Statement(StmtType t) : type(t) {} virtual ~Statement() = default; StmtType type; }; struct SelectStmt : Statement { SelectStmt() : Statement(StmtType::SELECT) {} std::string table; std::vector<std::string> columns; // 空表示 select * std::vector<Condition> where; // 多个条件之间按 AND 处理 };

Condition里只放单列条件，是这套实现的一个明确取舍：它不支持多表连接，也不支持or。这不是缺陷，是课程设计里"够用就好"的典型边界。真要在上面加 join，得先把Condition扩成带表名的形式，这是一个值得在改造前想清楚的扩展点。

分发逻辑放在执行器工厂里，根据 AST 构造对应的执行器对象：

// src/executor/executor.cpp std::unique_ptr<Executor> BuildExecutor(const Statement& stmt, Catalog& catalog, BufferPool& bpm) { switch (stmt.type) { case StmtType::SELECT: { const auto& s = static_cast<const SelectStmt&>(stmt); TableMeta* table = catalog.GetTable(s.table); if (!table) throw SqlError("table not found: " + s.table); // 条件是等值、且该列上有索引 -> 走索引扫描，否则退化成顺序扫描 IndexMeta* idx = table->FindEqualityIndex(s.where); std::unique_ptr<Executor> child; if (idx) { child = std::make_unique<IndexScan>(*table, *idx, s.where, bpm); } else { child = std::make_unique<SeqScan>(*table, bpm); } return std::make_unique<Filter>(std::move(child), s.where); } // INSERT / DELETE / UPDATE / CREATE TABLE ... 各自一个分支 default: throw SqlError("unsupported statement"); } }

参数说明：catalog提供表与索引元数据，bpm是全局缓冲池引用，所有算子共享同一个实例，绝不能各建各的。FindEqualityIndex返回空指针就说明这次查询没有可用索引，代码会自动降级为全表扫描——这个降级策略很关键，它保证了即使索引构建失败，查询也能出结果，只是慢一点。

3.3 迭代器模型：Open/Next/Close 为什么好用

所有算子继承同一个基类：

// src/executor/executor.h class Executor { public: virtual ~Executor() = default; virtual void Open() = 0; // 申请资源、定位到第一行 virtual bool Next(Row& out) = 0; // 取下一行，false 表示结束 virtual void Close() = 0; // 释放资源 virtual const Schema& GetOutputSchema() const = 0; };

Filter的实现就是个循环：Next里不断调子算子的Next，直到条件满足或子算子返回false。这种"火山模型"写法在工程里非常友好——想加Limit就套一层，想在哪个算子前后打日志就包一层，不用改动既有代码。我调试索引为什么没生效时，就是在BuildExecutor里临时打印走了哪个分支，一眼就能看出是IndexScan还是SeqScan。

4. 存储与索引：4KB 页里塞下记录和 B+ 树

存储层是这份工程最值得细看的部分。上面解析层再花哨，最后都要落到"这一行往哪个页的第几个槽写"。它用 4KB 定长页组织数据，页内用槽目录管理变长记录，索引用 B+ 树实现，缓冲池做 LRU 与脏页回写。

4.1 记录页布局：槽目录如何容纳变长记录

页头的结构大致如下：

// src/record/page.h constexpr size_t PAGE_SIZE = 4096; struct PageHeader { uint16_t slot_count; // 已分配的槽位数量 uint16_t free_start; // 空闲区起点，紧跟在槽目录之后 uint16_t free_end; // 空闲区终点，记录区从页尾往前长 page_id_t next_page; // 同表下一页，-1 表示没有下一页 };

设计上把页分成三段：页头在开头，槽目录从前往后长，记录数据从后往前长，中间那段是可用空间。每条记录在槽目录里对应一个offset + length，记录本身可以是不定长的char(n)。插入一条记录的代码如下：

// 返回槽位下标；页满返回 -1，由上层决定是换下一页还是报错 int16_t Page::InsertRecord(const char* data, uint16_t len) { PageHeader* h = header(); const size_t slot_bytes = sizeof(Slot); // offset + length，通常 4 字节 if (h->free_end - h->free_start < len + slot_bytes) return -1; h->free_end -= len; // 数据从页尾往前长 std::memcpy(PageData() + h->free_end, data, len); Slot s{h->free_end, len}; WriteSlot(h->slot_count, s); // 槽目录从页头往后长 h->slot_count++; h->free_start += slot_bytes; return static_cast<int16_t>(h->slot_count - 1); }

三个关键值：free_start与free_end之差就是剩余空间，len + slot_bytes是要申请的净空间，slot_count同时当作槽目录的下一个写入位置。删除记录时不要真的搬数据，只需要把对应槽标记为已删除（例如length = 0），等页内碎片多到一定程度再做整理——这是几乎所有页式存储的通用做法，搬数据不仅慢，还会把所有上层引用弄乱。

4.2 B+ 树：查找、分裂与叶子链表

索引层用的是标准 B+ 树：内部节点只存键和孩子页号，叶子节点存键与记录定位信息（页号 + 槽位），所有叶子用next_leaf串成链表支持范围查询。查找入口先一路下探到叶子：

// src/index/bplus_tree.cpp // 找到 key 应落入的叶子页与槽位 bool BPlusTree::FindLeaf(const Key& key, page_id_t& leaf_id, int& slot) { page_id_t cur = root_id_; while (true) { auto guard = bpm_.FetchPage(cur); // 自动 pin，出作用域 unpin BPlusNode node(guard.Data()); if (node.IsLeaf()) { leaf_id = cur; slot = node.LowerBound(key); // 第一个 >= key 的位置 return true; } int i = node.UpperBound(key) - 1; // 最后一个 <= key 的孩子下标 if (i < 0) i = 0; // 最小键边界 cur = node.ChildAt(i); } }

LowerBound与UpperBound的区别是二分查找里经典的开闭区间问题，写反了不会崩，但会漏掉边界键重复的行，表现出来就是"偶尔少一行"，非常玄学。叶子节点满了就分裂成两个、把中间键上推到父节点；父节点也满了继续向上分裂，直到根，根分裂时新建一层。删除同理有合并逻辑，但很多课程实现为了简化不实现合并，只做标记删除，这个取舍要在文档里写清楚，否则长期跑下来索引文件会只涨不缩。

4.3 缓冲池：LRU、pin 计数和脏页回写

缓冲池是磁盘页在内存中的缓存池，页表负责page_id -> frame的映射，LRU 链表负责淘汰，pin 计数负责保护正在被使用的页。核心取页逻辑：

// src/buffer/buffer_pool.cpp Page* BufferPool::FetchPage(page_id_t pid) { std::lock_guard<std::mutex> lock(latch_); auto it = page_table_.find(pid); if (it != page_table_.end()) { // 命中 Frame* f = &frames_[it->second]; f->pin_count++; Touch(f); // 挪到 LRU 链表头部 return &f->page; } Frame* f = FindVictim(); // 从链表尾部找 pin_count == 0 的 if (!f) throw BufferPoolFull("all frames pinned"); if (f->dirty) FlushFrame(f); // 脏页先写回磁盘 page_table_.erase(f->pid); disk_.ReadPage(pid, &f->page); // 整页读入 f->pid = pid; f->dirty = false; f->pin_count = 1; page_table_[pid] = static_cast<frame_id_t>(f - frames_); Touch(f); return &f->page; }

需要配套实现的是UnpinPage(pid, is_dirty)：pin_count--，如果传进来的is_dirty为真就把该 frame 标脏。这里有个血泪经验——忘记 unpin 的程序不会立刻报错，它会先把所有 frame 的 pin 计数占满，然后在几百条插入之后突然抛BufferPoolFull，此时错误现场离真正的原因已经很远了。调试这类问题，我一般在FindVictim返回空之前把每个 frame 的pid和pin_count打出来，谁没释放一目了然。

5. 跑起来与排查：从 make 到第一条 select 的通关记录

代码读得再顺，不跑一遍心里没底。这一章按"装依赖—编译—冒烟—出问题怎么查"的顺序走一遍，把我在几个不同分支上踩过的坑集中写出来。

5.1 依赖清单与首次构建

最小依赖只有三样：C++17 编译器、CMake、一个能跑 shell 的终端。如果解析器是生成式实现，再加上 flex 和 bison；交互层如果用了 readline 做行编辑，就再装libreadline-dev，没装的话工程通常会退化成std::getline，功能不受影响。

# 最小集 sudo apt install build-essential cmake # 可选：生成式解析器 / 行编辑 sudo apt install flex bison libreadline-dev # 配置与编译，打开警告更容易发现类型问题 cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug -DCMAKE_CXX_FLAGS="-Wall -Wextra" cmake --build build -j"$(nproc)"

-Wall -Wextra建议一直开着。这个工程里大量的页内偏移是uint16_t，和size_t混算时一旦漏掉强制转换，编译器给的警告往往就是后面某个内存越界的先兆。

5.2 交互式 shell 与回归脚本

启动后进入 REPL，语句以分号结尾，下面这段可以直接贴进去跑一遍冒烟：

create table student (id int, name char(16), score int); create index idx_student_id on student (id); insert into student values (1, 'alice', 90); insert into student values (2, 'bob', 85); insert into student values (3, 'carol', 78); select * from student where id = 2; -- 应该走索引，返回 1 行 select * from student where score > 80; -- 无索引，走全表扫，返回 2 行 delete from student where id = 1; select * from student; -- 应该只剩 2 行 quit;

如果工程支持exec 文件名;这样的指令，就把上面的内容存成test/cases/basic.sql，用脚本把test/cases/下所有文件跑一遍，再拿结果和手写的期望输出做diff。这套回归很土，但在改缓冲池和 B+ 树的时候救过我很多次——那两个模块的 bug 最擅长"只在小数据量下正确"。

5.3 五个把我卡住的现场

现象一：启动直接段错误，gdb 显示崩在 catalog 加载处。原因是数据目录第一次不存在，打开 catalog 文件失败后代码没有走"新建"分支，直接对空指针解引用。解决办法是在启动流程里先判断目录是否存在，不存在就mkdir，再判断 catalog 文件是否存在，不存在就走初始化流程建一个空 catalog 并写回磁盘。

现象二：插入的数据在本次会话能查到，重启后全没了。根因是脏页只在缓冲池析构函数里统一回写，而有的人在 REPL 里用exit()直接退出进程，析构根本没执行。解决方式有两种：把退出路径统一改成从main正常return，或者在 REPL 的quit分支里显式调一次FlushAllPages()。后者更稳，推荐两个都做。

现象三：明明建了索引，explain一类的调试输出却显示走了全表扫描。常见原因是条件里的字面量类型和索引列类型对不上，比如id是int，用户写了where id = '2'，比较函数直接返回不匹配，索引匹配逻辑就放弃了。解决办法是在解析阶段做一次类型归一化，把字符串字面量按目标列类型转换，转换失败直接报语法错误，而不是悄悄降级。

现象四：改了页大小之后，旧数据目录读出来全是脏数据。文件里没有版本标识，程序按新页大小去解读旧文件，边界全错。解决办法是在每个数据文件开头加一个固定长度的头，写明 magic number、页大小和格式版本，加载时先校验，不匹配就明确报错而不是硬读。这个头只占十几个字节，却能把"数据损坏"变成"版本不兼容"这种可诊断的问题。

现象五：char(n)字段上建索引后，等值查询时有时查到有时查不到。定长字符串在存储时会用空格补齐到 n，而查询条件里的字符串没有补齐，两边做比较时长度不同，B+ 树的键序就乱了。解决办法是在写入索引键和查询键之前统一做一次"右补空格到定长"的归一化，比较函数里也按定长比较，不要用strcmp那种遇到\0就停的写法。

6. 二次开发：从加一个 explain 开始练手

改造这份工程，我建议从最小的功能切入，别一上来就动存储格式。最合适的第一个练手目标是给执行器加一个explain语句：它不改变任何数据，只是把BuildExecutor构造出来的算子树按层打印出来，让你直观看到一条 SQL 到底走了索引还是全表扫。

6.1 加一个 explain 算子

实现上只需要在 AST 里加一个ExplainStmt，语法规则里识别explain关键字，分发时把内层语句构造成执行器树后遍历打印：

// src/executor/explain.cpp void ExplainExecutor::Dump(const Executor& root, int depth) { std::string indent(depth * 2, ' '); std::cout << indent << root.Name(); // "SeqScan(student)" / "IndexScan(...)" if (auto* child = root.Child()) Dump(*child, depth + 1); }

Name()由每个算子自己返回，带上表名和关键参数，比如IndexScan(student.idx_student_id, id = 2)。这一步改完，后面所有性能相关的调试都会轻松很多。

6.2 把单表查询扩成双表 join 的最小改法

如果要往前走一步，最小可行的 join 是嵌套循环：外层SeqScan扫左表，内层对每一行右表做一次带等值条件的查找（右表连接列上有索引就直接复用IndexScan）。改动集中在三处：Condition加上表名前缀、AST 里允许from跟两张表、BuildExecutor里多一个NestedLoopJoin分支。这个改法的验证标准很明确：

6.3 验证改造是否正确的三步

第一步永远是跑老回归。改造前先把test/cases/全跑一遍存档，改完再跑一遍做 diff，任何一行差异都要能解释清楚。第二步是边界构造，空表、单行、重复键、最大长度字符串这四类输入，能覆盖掉大部分页内偏移和二分查找的边界 bug。第三步才是性能观察，用小数据量对比explain输出的算子形态，确认索引真的被用上了，而不是"看起来快了"。

我现在改任何存储相关代码之前，都会先写一个能跑通的最小 SQL 脚本存进test/cases/，改完立刻跑。这份习惯是从上面那次改页大小把旧数据读坏之后养成的——格式可以改，但没有版本头和回归脚本的格式改动，迟早会在某个深夜让你怀疑人生。希望帮到你。

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