简介一套基于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 这八个文件在编辑器里摊开。按职责分类如下文件类别职责定位AUTHORS元信息贡献者信息无运行时作用BUILD.bazel构建配置声明源文件、编译目标与依赖关系glog.bzl构建规则封装 glog 日志库的外部依赖加载minisql_lex.c词法分析把 SQL 字符串切分成 token 流minisql_yacc.c语法分析按文法把 token 流归约为语法树节点parser.c解析入口暴露解析接口协调 lex 与 yaccsyntax_tree.c语法树实现构造与销毁语法树节点供执行器遍历gtest_unittest.cc单元测试用 GoogleTest 验证核心模块行为这个表是按数据流方向排的。一条 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 [-stdc17], )把词法、语法、语法树实现打包成一个 cc_library对外以 minisql_parser 为名暴露接口。deps 里挂的 :glog 就是由 glog.bzl 生成的依赖目标。这里有几个参数要注意srcs 决定参与编译的源文件集合漏掉任何一个都会导致链接时找不到符号copts 里的-stdc17是 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_CLAUSEright 指向列清单链表的头部。参数说明很关键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 不同步问题测试断言应该直接面向语法树结构而不是解析器的中间 tokenTEST(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 重跑一遍新功能没有对应测试用例就不算完成。这套习惯让我以后再接手类似内核框架时每次改动都有后悔药吃。希望这些经验和这份资源能帮到你。本文还有配套的精品资源点击获取