C++ MiniSQL数据库内核源码解析：缓冲池、B+树与SQL引擎

简介：一套基于C++实现的MiniSQL数据库管理系统源码包，面向数据库原理课程学习者与存储引擎研究爱好者，可用于课程设计、实验复现或内核阅读。项目参考CMU15445 BusTub等经典教学框架，并兼容常见MiniSQL实验要求，覆盖缓冲池管理、B+树索引、记录管理、元数据目录（Catalog Manager）以及锁管理器的并发访问控制等核心模块，还支持持久化数据页的分配与回收，便于理解轻量级SQL解析与执行引擎的完整工作流程。压缩包共389个文件，整体约1.07MB，主要包含C/C++头文件与实现文件、Python辅助脚本、CMake构建配置和说明文档；同时提供词法语法分析器及单元测试代码，目录结构清晰，适合编译运行与二次开发。当前已有79人浏览学习，可作为数据库课程设计与实验的参考资料。借助这份代码，读者能逐模块剖析缓冲池与B+树索引的实现细节，学习页读写、替换与回收流程，也可通过锁管理器理解并发事务控制的关键策略，并利用自带测试用例验证功能的正确性。

1. MiniSQL 是什么：能跑课设也能啃内核的 C++ 数据库源码

数据库课程设计最常见的翻车姿势，是把“实现一个数据库”做成“用 Python 包一层 SQLite”。这份基于 C++ 的 MiniSQL 数据库管理系统源码走的是另一条路：它把 CMU15445 BusTub 那套缓冲池、B+ 树索引、锁管理器的思路，落成了一部能读、能改、能调试的 C++ 工程。

它的定位很明确：一个具备 SQL 解析与执行能力的轻量数据库引擎，支持建表删表、插入、更新与查询，并且背后是真实的磁盘页替换、索引节点分裂和并发访问控制逻辑。这份资源要解决的问题，是数据库管理系统怎么从零长出来，而不是怎么把一条 SQL 字符串查出来。

适合两类人：一类是课程设计选了 MiniSQL 题目、需要快速读懂框架并交出自己的扩展实现的学生；另一类是准备把数据库内核项目写进简历、想沿 BusTub 思路系统走一遍的工程师。花两周时间把文件逐个读下来，你对“数据页在哪、索引怎么查、锁什么时候加”会有真实画面感。

2. 从文件结构拆到编译链路：MiniSQL 的骨架与 Bazel 构建

2.1 文件清单：先分清七个文件谁在什么时候工作

拿到压缩包先别急着编译，先把 AUTHORS、BUILD.bazel、glog.bzl、minisql_lex.c、minisql_yacc.c、parser.c、syntax_tree.c、gtest_unittest.cc 这八个文件在编辑器里摊开。按职责分类如下：

这个表是按数据流方向排的。一条 SQL 从字符串变成可执行结构，顺序是 lex → yacc → syntax_tree，而 parser.c 是整条链路的门面。gtest_unittest.cc 是最后的验证层，它直接决定了你敢不敢在有 Bug 的索引实现上跑大规模插入测试。

我拿到一份陌生源码之后做的第一件事，是把编译单元的名字抄到纸上，圈出谁调用谁。MiniSQL 的分层非常典型：词法分析、语法分析、语法树三者解耦，这种结构你在以后看 PostgreSQL 的 gram.y 时也会觉得似曾相识。

2.2 BUILD.bazel 与 glog.bzl：把构建依赖关系钉死

Bazel 是这套代码的默认构建系统，BUILD.bazel 负责告诉 Bazel 哪些源文件参与编译、编译成什么目标格式、依赖谁。常见做法是这样的，源文件里以 parser 为核心目标：

cc_library( name = "minisql_parser", srcs = [ "minisql_lex.c", "minisql_yacc.c", "parser.c", "syntax_tree.c", ], deps = [":glog"], copts = ["-std=c++17"], )

把词法、语法、语法树实现打包成一个 cc_library，对外以 minisql_parser 为名暴露接口。deps 里挂的 :glog 就是由 glog.bzl 生成的依赖目标。这里有几个参数要注意：srcs 决定参与编译的源文件集合，漏掉任何一个都会导致链接时找不到符号；copts 里的-std=c++17是 MiniSQL 这类新工程常用标准，过低会触发 auto 类型推导的兼容性问题。

glog.bzl 的职责是拉取 Google glog 日志库。Bazel 工程里第三方库通常不会直接放在源码树里，而是用工作区规则声明下载地址和校验值，大致形态如下：

load("@bazel_tools//tools/build_defs/repo:http.bzl", "http_archive") def glog_deps(): http_archive( name = "glog", urls = ["https://github.com/google/glog/archive/v0.6.0.zip"], sha256 = "你的本地校验值", strip_prefix = "glog-0.6.0", build_file = "@//:glog.BUILD", )

这段代码的作用是声明“glog 这个名字对应哪个远程源码包”，并把它的构建文件指向项目自己准备的 glog.BUILD。实际运行时，Bazel 会先下载、再按 glog.BUILD 里的规则编译。踩过坑的人都知道，这里的 sha256 写错一个字符，整个构建就会卡在下载阶段报 checksum mismatch，所以我的习惯是第一次先把 sha256 留空，让 Bazel 报出实际哈希再补回去。

整个构建链路可以理解成三层：Bazel 读 WORKSPACE 加载 glog.bzl → 生成 glog 库目标 → 再用 BUILD.bazel 把 minisql_parser 与 glog 链接起来。只要这层依赖关系理清，编译报错就不再是黑匣子。

2.3 parser.c 与语法树：一条 SQL 从文本到结构的旅程

parser.c 是整个解析过程的入口，对外通常裸露一个ParseSQL(const char* sql)这类接口。内部流程是：先调 minisql_lex.c 的词法扫描，把 SQL 字符串切成SELECT、FROM、表名、列名这样的 token 序列；再交给 minisql_yacc.c 按文法规则做归约；最终由 syntax_tree.c 构造出可被执行器遍历的节点树。

syntax_tree.c 里的节点结构设计决定了后续的执行复杂度。以常见实现为例：

typedef enum { NODE_SELECT, NODE_INSERT, NODE_CREATE_TABLE, NODE_WHERE_CLAUSE, NODE_EXPR } NodeType; typedef struct SyntaxNode { NodeType type; struct SyntaxNode *left; struct SyntaxNode *right; struct SyntaxNode *next; char *table_name; char *column_list; } SyntaxNode;

每个节点用 type 标注语义角色，left/right 指针表达嵌套条件，next 指针串起同层多个字段。比如SELECT * FROM students WHERE age > 20，解析结果会是一个 NODE_SELECT 作为根节点，left 指向 NODE_WHERE_CLAUSE，right 指向列清单链表的头部。

参数说明很关键：next指针在列清单场景里承担“遍历兄弟节点”的职责，而在深嵌套表达式里left/right承担优先级语义。改语法树结构时，这两类指针的初始化最容易漏，一漏就是“解析没问题，执行时空指针崩掉”。

执行器拿到这个树之后，会递归遍历。遇到 NODE_CREATE_TABLE 就调 Catalog Manager 登记表元数据，遇到 NODE_INSERT 就定位目标表并调用记录管理模块写页。所以从架构上看，parser.c 和 syntax_tree.c 是前端，缓冲池与 B+ 树是后端，一条 SQL 的生命周期恰好串起了压缩包里的所有 C 文件。

3. 缓冲池与 B+ 树：MiniSQL 的核心机制与实现参数

3.1 缓冲池：页面缓存、固定计数与写回时机

缓冲池是 MiniSQL 所有数据操作的落脚点。它的抽象模型是把数据库文件看成一个个固定大小的页，内存里只保留一部分页的缓存副本。核心问题有两个：替换策略和写回时机。

替换策略通常用 LRU 变种。页面被读取时先在哈希表里查，命中就把 pin_count 加一；未命中就要找一个可替换的槽位，淘汰掉当前 pin_count 为零的帧。写回时机则看脏页标记：只有被修改过的页在淘汰时才需要刷回磁盘，干净页直接丢弃。下面是一段我在类似项目里常用的框架示意，可以作为理解这份源码缓冲池模块的参考：

Page *BufferPool::FetchPage(PageId pid) { auto it = page_table_.find(pid); if (it != page_table_.end()) { frames_[it->second].pin_count++; return frames_[it->second].page; } FrameId victim = Evict(); if (frames_[victim].dirty) { disk_->WritePage(frames_[victim].page_id, frames_[victim].page); frames_[victim].dirty = false; } disk_->ReadPage(pid, frames_[victim].page); frames_[victim].pin_count = 1; frames_[victim].page_id = pid; page_table_[pid] = victim; return frames_[victim].page; }

逻辑说明：第一步查哈希表，命中就直接增加引用计数并返回，避免重复读盘；第二步淘汰旧页，若旧页脏则先写回，再读入新页并重建映射。这套“命中检查 → 淘汰 → 写回 → 读入”的顺序不能乱，把写回放在读入之前是所有这类实现里最容易漏的一条。

参数说明：pin_count表示当前有多少执行流程正在使用这个页，只有归零的页才有资格被淘汰。如果代码里某处 FetchPage 之后忘了 Unpin，缓冲池就会逐渐耗尽空位，表现为“数据库跑着跑着突然无法分配新页”。调试这类问题，第一件事就是检查 pin/unpin 是否成对出现。

MiniSQL 在 BusTub 框架基础上还补充了对持久化数据页分配回收状态的支持，也就是说空闲页链表本身也要持久化，否则数据库重启后，之前删表释放的页无法被重新分配，新表会持续占用增长的文件尾部。

3.2 B+ 树索引：插入分裂、删除合并与迭代遍历

B+ 树是 MiniSQL 里最重的数据结构。它支撑了两类需求：等值查询和范围查询。和普通二叉搜索树最大的区别在于，B+ 树的所有数据都放在叶子节点，内部节点只存索引键，叶子节点用链表串起来，这让范围遍历可以顺序扫描而不用回溯。

插入逻辑的核心是分裂。当叶子节点写满时，需要把它拆成两个节点，并把中位键提升到父节点；如果父节点也满，则继续往上分裂，直到根节点。删除则相反，节点低于半满时触发合并或借位。下面给出插入路径的关键骨架：

void BPlusTree::Insert(Key key, Value value) { LeafNode *leaf = FindLeaf(key); if (leaf->Size() < leaf->max_size) { leaf->InsertSorted(key, value); return; } LeafNode *right = SplitLeaf(leaf); InternalNode *parent = leaf->parent; parent->InsertKey(right->first_key, right); if (parent->Size() > parent->max_size) { SplitInternal(parent); } }

逻辑说明：查找叶子节点用的是从根到叶的单路径遍历，每层做二分查找定位下一层指针；插入先落在叶子，满了才分裂并把新节点的第一个键提升到父节点。SplitLeaf返回的 right 节点里包含了原节点一半的数据，first_key是右节点的最小键，也是父节点索引必须记录的“路标”。

参数说明：这里有两个关键值，max_size决定一个节点容纳多少键值对。取小了树变高楼，磁盘寻道次数变多；取大了节点利用率高，但内存内二分查找的耗时会上升。常见实现会选择 4 到 8 之间的数，MiniSQL 这类教学框架通常取 4，因为这样可以更容易地触发分裂逻辑，方便观察和调试。

迭代遍历的实现比插入更隐蔽。由于叶子节点之间用 next 指针串联，遍历只需要从最左端叶子开始，沿 next 指针逐页扫描。你会在代码里看到类似LeafIterator的类，它维护了当前节点和槽位号，重载++运算符时先检查槽位，再决定是否跳到下一个叶子。这个设计直接支撑了 SQL 里的范围查询和全表扫描。

3.3 选型理由：为什么是 B+ 树而不是哈希索引

MiniSQL 同时有索引和记录管理，索引结构选择 B+ 树是有理由的，不是拍脑袋。对比哈希索引，B+ 树的优势集中在两点。

第一是范围查询。哈希索引只支持等值匹配，WHERE age > 20这种条件在哈希结构里基本退化成全表扫描。B+ 树的叶子链表天然有序，一次二分定位就能从任意位置开始顺序遍历，范围查询成本稳定在 O(log n + m)，m 是结果集大小。

第二是磁盘访问局部性。B+ 树节点大小通常和磁盘页对齐，一个节点一次 IO 就能完整载入。哈希索引在冲突严重时会产生链式访问，多次随机 IO 对机械硬盘是灾难。MiniSQL 的缓冲池以页为粒度缓存，B+ 树节点如果设计成恰好占用一页，缓存命中率会明显提升。

还有一个容易被忽略的点：B+ 树是唯一能同时支撑等值、范围和排序输出的索引结构。MiniSQL 的 Catalog Manager 需要按表名做前缀匹配、按索引键做等值查找，一套 B+ 树实现就能覆盖所有场景，不需要在代码里并存两套索引系统，这对一个教学引擎来说价值很大。

4. 避坑指南：编译、并发与测试环节的五个高频翻车点

4.1 Bazel 构建失败：找不到 glog 规则或头文件缺失

现象：执行 bazel build 时报错，提示无法解析 :glog 依赖，或者编译到某个源文件时找不到logging.h头文件。

原因：绝大多数情况下是 glog.bzl 里的http_archive地址失效，或者build_file指向的 glog.BUILD 文件路径不对。Bazel 在下载阶段失败时最容易伪装成编译错误。

解决：先去 BUILD.bazel 里确认 deps 中:glog这个名字，再到 glog.bzl 里检查name = "glog"是否一致。如果远程下载不稳定，直接在本地把 glog 源码放在 third_party 目录下，用local_repository替代http_archive。改完以后记得清理缓存重跑，Bazel 对已缓存失败项有记忆。

4.2 词法与语法 token 不同步：SQL 解析结果错乱

现象：输入INSERT INTO students VALUES (1, 'Alice')，语法树里却能解析出 SELECT 节点；或者 WHERE 条件被丢弃，查询返回空结果。

原因：minisql_lex.c 返回的 token 枚举值和 minisql_yacc.c 里%token声明的常量不一致。这两份文件通常由 flex 和 bison 生成，但如果手写过其中一份，token 编号就会错位。yacc 按错误的 token 编号归约，就会形成完全错误的语法树。

解决：查看 yacc 文件顶部的%token定义，和 lex 文件里的返回值逐一比对。最稳妥的做法是用 flex/bison 重新生成两份文件，确保两者出自同一套定义。另外，修改文法之后要同步更新 syntax_tree.c 里的节点构造逻辑，否则会出现“语法树合法但执行器无法识别”的半崩溃状态。

4.3 并发插入撞车：B+ 树结构与死锁双告警

现象：两个并发事务同时向同一张表插入数据，一段时间后出现“duplicate key”或者“page not found”，甚至整个进程卡死。

原因：MiniSQL 的锁管理器负责事务级的表锁和行锁，但 B+ 树内部的节点分裂 / 合并操作如果没有单独保护，两个事务同时分裂同一个节点，父节点指针就会被覆盖成错误值。死锁则是因为事务 A 持有了左叶子节点的锁，正在等右叶子；事务 B 持有了右叶子的锁，正在等左叶子。

解决：给 B+ 树的写操作加业界的通用方案——锁耦合（crabbing protocol），即从根到叶路径上先锁父节点再锁子节点，子节点确认安全（不会分裂或合并）后立即释放父节点锁。你可以在 MiniSQL 的索引模块里检查有没有类似逻辑，没有的话，最省事的临时方案是把整棵树的写操作包进一把全局互斥锁，牺牲并发度换取一致性。

4.4 脏页提前写回：事务回滚后数据不一致

现象：一个事务更新了某条记录，随后 rollback，但重启数据库后发现这条记录依然保留着更新后的值。

原因：缓冲池的淘汰策略只看 pin_count 和 dirty 标记，并不知道这个脏页里包含的数据属于哪个事务。如果脏页在事务提交前被写回磁盘，rollback 机制就无法撤销它，因为磁盘上已经是新值。这是把“页面缓存管理”和“事务管理”分开实现时最容易出现的断层。

解决：两个方向。一是写回时检查页面版本的可见性，未提交事务的数据不落盘；二是在 log 模块里记录回滚信息。作为课设级别的修复，更实际的做法是：事务 rollback 时，对所有相关的缓冲池页执行逆操作并将脏页强制写回，保证内存和磁盘状态一致。代码审查时重点看事务提交与缓冲池 Flush 的先后顺序。

4.5 测试用例相互污染：gtest 第二次运行结果诡异

现象：gtest_unittest.cc 里的用例第一次运行全部通过，第二次运行开始随机失败；换台机器跑，失败的用例又不同。

原因：所有测试共享同一个数据库文件。前面的用例插入的数据残留在磁盘文件里，后面的用例读到这些残留，以为是自己插入的，导致断言失败。B+ 树测试尤其脆弱，因为残留数据可能让树叶节点提前满，触发意外的节点分裂。

解决：在测试固件里给每个用例创建独立的数据库文件，用测试用例名称生成文件名，并在 TearDown 里删除。另外，每个测试构造前重置缓冲池和 Catalog Manager 的全局状态，避免静态变量跨用例残留。我的习惯是在 gtest main 函数里统一设置临时目录，所有用例的数据库文件都放在这个目录下，测试结束后整体清空。

5. 用 gtest 建立回归测试习惯：让 MiniSQL 的改动可验证

最后一个想聊的话题，是这份源码里的 gtest_unittest.cc 该怎么利用。MiniSQL 有缓冲池、B+ 树、解析器三层核心逻辑，每一层都有适合用测试钉死的接口，改代码时基本靠这些测试兜底。

先说最值得写的测试：缓冲池的脏页淘汰行为。这类 Bug 最隐蔽，因为问题只会在特定访问顺序下触发。我一般会写一个覆盖 LRU 替换边界条件的用例，核心思路是把池子容量设小，再访问超过容量的页数，最后检查数据是否被正确写回：

TEST(BufferPoolTest, EvictDirtyPageAfterFullCyle) { DiskManager dm("test_evict.bin"); BufferPool pool(4, &dm); for (int i = 1; i <= 8; i++) { Page *p = pool.NewPage(); std::string data = "data_" + std::to_string(i); std::memcpy(p->GetData(), data.c_str(), data.size()); pool.Unpin(p->GetPageId(), true); } Page *reloaded = pool.FetchPage(5); EXPECT_NE(reloaded, nullptr); EXPECT_EQ(std::string(reloaded->GetData()), "data_5"); }

逻辑说明：池容量只有 4，循环写入了 8 个页，强制触发了至少两轮替换。核心断言是第 5 页在经历多次淘汰后重新被读取时，内容依然完好，这验证了脏页写回逻辑是否在每次替换前正确执行。

代码里的Unpin(page_id, true)第二个参数是 dirty 标记，传 true 意味着这个页被修改过，淘汰时必须写回。单元测试里最容易漏的就是这个参数，漏传 false，脏页就丢了。

B+ 树模块值得测的是插入后按序遍历结果：

TEST(BPlusTreeTest, SequentialInsertAndScan) { BPlusTree tree(4); for (int i = 0; i < 100; i++) { tree.Insert(i, i * 2); } int expected = 0; for (auto it = tree.Begin(); it != tree.End(); ++it) { EXPECT_EQ(it->first, expected); EXPECT_EQ(it->second, expected * 2); expected++; } EXPECT_EQ(expected, 100); }

逻辑说明：往阶数为 4 的 B+ 树里连续插入 100 个键，每次插入都可能触发分裂。用迭代器从头扫到尾，验证两个事实：一是 100 个键一个不少，二是遍历顺序严格递增。这两条如果同时满足，说明分裂和叶子链表指针都没有坏，这是索引模块最重要的回归测试。

解析器的测试同样重要，但要记住规避之前提到的 token 不同步问题，测试断言应该直接面向语法树结构，而不是解析器的中间 token：

TEST(ParserTest, CreateTableParsesCorrectly) { SyntaxNode *root = ParseSQL("CREATE TABLE students (id INT, name TEXT)"); ASSERT_NE(root, nullptr); EXPECT_EQ(root->type, NODE_CREATE_TABLE); EXPECT_STREQ(root->table_name, "students"); FreeSyntaxTree(root); }

这段代码盯着 ParseSQL 返回的根节点类型和表名断言，不关心 lex/yacc 内部实现。FreeSyntaxTree 负责回收节点内存，这类测试跑多了，能顺手把内存泄漏一起盯住。

自从跟脏页写回这个 Bug 纠缠过一个通宵之后，我养成了一个条件反射：任何对缓冲池和 B+ 树的修改，哪怕只是改了行注释，都必须把全套 gtest 重跑一遍；新功能没有对应测试用例，就不算完成。这套习惯让我以后再接手类似内核框架时，每次改动都有后悔药吃。希望这些经验和这份资源能帮到你。

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