简介基于C实现的MiniSQL数据库管理系统面向数据库原理学习者与课程实验开发者在参考CMU15445 BusTub框架基础上改造扩展兼容MiniSQL实验要求覆盖缓冲池、B树索引、记录管理、持久化、语法解析与执行引擎等核心模块适合作为数据库课程设计或实验参考。压缩包共377个文件以h头文件、cc/cpp源码、Python脚本及CMake构建文件为主整体约1.05MB结构紧凑便于对照阅读。已有80人学习下载。通过源码可了解缓冲池页面置换、B树插入删除、记录管理器操作及SQL语法树生成与执行流程并掌握对象序列化实现持久化的思路对理解关系型数据库底层机制有直接帮助。1. 这份 C MiniSQL 源码值得你花一个周末拆一遍数据库系统原理的课程设计里MiniSQL 是被选得最多的题目之一用 C 手写一个能跑建表、插入、查询的教学型数据库麻雀虽小五脏俱全。这份源码正好把一条 SQL 从命令行到磁盘文件的完整链路摊开了——词法分析、语法解析、记录管理、B 树索引全是用 C 一行行写出来的。适合正在准备数据库课设、或者想从代码层面理解“数据库到底在干什么”的从业者。我拆完之后最直观的感受是它比教科书上的伪代码值钱得多也远比那些只讲架构图的博客具体。前提是你知道该按什么顺序读以及哪些地方是容易翻车的。2. MiniSQL 的三层骨架解析器、执行器与存储引擎怎么分工2.1 一条建表语句进来系统里发生了什么在 MiniSQL 里敲下这条语句CREATE TABLE student (id INT, name CHAR(20), PRIMARY KEY(id));系统内部并不是“一个函数干完所有事”而是按职责拆成了三个模块接力。第一棒是解析器词法分析先把字符串拆成 token识别出 CREATE、TABLE、student、id、INT 这些最小单位语法分析再按文法把它们组合成一棵语法树。第二棒是执行器拿着这棵树去调用目录管理模块登记表名、字段名、字段类型再调用记录管理模块创建对应的数据文件如果是主键字段还可能顺手建一个索引文件。第三棒才是落盘把目录信息写进系统表或者专用文件把表结构固化下来。在源码里找这三个模块的入口是很直观的事。你会在工程里看到类似这样的目录划分interpreter解析器、catalog_manager目录管理、record_manager记录管理、index_manager索引管理最后有一个 API 层把它们的调用关系串联起来。这个分层不是拍脑袋定的它对应的是真实数据库里的词法/语法分析器、优化执行器、存储引擎三个大层次。刚拿到源码时不要一头扎进某个 cpp 文件里读而是顺着这条调用链走一遍interpreter 解析出语法树 → API 层按语句类型分发 → catalog 登记元数据 → record 打开或创建数据文件 → index 维护索引。等你走完这一圈整个项目的脉络就清晰了后面读任何细节都有地方挂靠。2.2 源码包的文件地图这几个文件值得优先读大多数 MiniSQL 课程源码包的文件组织都差不多我把它整理成一张表。你拿到手的包可能会有一点命名差异但职责是能对应上的。文件/目录职责建议阅读顺序interpreter或 parser 目录词法分析、语法分析、语句分发第 1 个读catalog_manager维护表结构、字段信息、索引登记第 2 个读record_manager页、槽、记录的读写与删除逻辑第 3 个读index_managerB 树、哈希索引的插入查找第 4 个读API / executor串联以上模块对外暴露执行接口与第 1 个并行读先说为什么 interpreter 要第一个读。所有用户的 SQL 都要经过它读懂了它你才知道一条语句在什么时候被识别成“建表”、什么时候被识别成“查询”也才能理解后面模块在等什么参数。catalog 放第二个读是因为它是“元数据的中转站”——记录管理要看字段长度索引管理要看哪一列建了索引都从这里问。record 和 index 是真正的硬骨头放到倒数第二步去啃比较合适。record 涉及页的布局和槽位管理index 涉及 B 树的插入、分裂、删除。如果一上来就钻这两个模块很容易被细节淹没连“这个函数什么时候被调用”都搞不清楚。API 层反而是最简单的它就是一层胶水读完它你就能把前面的功能块串成一条线。2.3 先把项目编译跑通用一条 SQL 验证安装拿到源码第一件事不是读代码是编译。常见做法是包内带一个 Makefile 或 CMakeLists.txt我用两种方式各走一遍# 方式一包内带了 Makefile cd MiniSQL make # 如果出现可执行文件 minisql直接启动 ./minisql# 方式二包内带的是 CMakeLists.txt cd MiniSQL mkdir build cd build cmake .. make ./minisql跑起来后会进到一个类似 MySQL 的交互式命令行提示符一般是 MiniSQL。先执行下面三条 SQL确认三层模块都没问题CREATE DATABASE test; -- 有的版本没有这个命令跳过即可 CREATE TABLE student (id INT, name CHAR(20), PRIMARY KEY(id)); INSERT INTO student VALUES (1, Alice); SELECT * FROM student WHERE id 1;如果建表和插入都成功说明解析器、目录管理、记录管理三个模块是通的如果能通过主键查到记录说明索引模块也已经注册生效。有些源码包还支持批处理模式把测试 SQL 写进一个文件重定向执行./minisql test.sql这在我调试时非常有用。交互模式下一旦报错退出就很难复现现场而把 SQL 提前写好、重定向执行每次跑都能得到完全一致的输出排查问题时效率高很多。3. 表和记录把一行数据从“字符串”变成“磁盘字节”3.1 记录格式设计定长还是变长决定你后续的复杂度MiniSQL 里最重要也最容易忽略的一个设计是记录的存储格式。很多课程版源码偷懒只支持定长字段也就是 CREATE TABLE 里全是 INT、CHAR(n)不允许 VARCHAR。这个选择不是随便做的它直接决定了记录模块的复杂度。定长记录的好处是每条记录的长度固定删除后空出来的位置可以被新记录精确复用目录结构只需要存一个“文件里有多少个槽位”的计数。记录模块在分配空间时只需要顺序找第一个空闲槽位// 定长记录槽位结构常见于课程版 MiniSQL 的 record_manager constexpr int DELETE_FLAG -1; struct Slot { int offset; // 记录在页数据区中的字节偏移 int length; // 记录长度-1 表示该槽位已被删除 };offset 和 length 的配合是理解整个记录模块的关键。插入时分配器找到第一个 DELETE_FLAG 的槽位写入 offset 和 length再把数据拷到页面的数据区删除时把 length 置为 DELETE_FLAG表示槽位可复用。这里有个细节length 被复用为删除标记所以真实记录长度不能是负数课程里一般用 -1 表示删除读者看到负数时不要把它当作数据异常。如果源码支持 VARCHAR那么事情就复杂多了。变长记录不能简单用“第 N 个槽位固定偏移”来定位必须在页内维护一个偏移量表每条记录的真实位置要经过二次寻址。这个复杂度会渗透到插入、删除、扫描、索引回表各个环节。所以你拿到源码后先看 CREATE TABLE 支持哪些类型——如果只支持 INT 和 CHAR那说明这套代码刻意选择用“定长”换取“实现简单”你在调试时不要拿变长字符串去测试会得到不符合预期的结果。3.2 目录管理模块一张表到底长什么样谁说了算记录管理负责把字节写进文件但“这张表有哪些列、每列什么类型、哪列有索引”这类信息归目录管理模块管。模拟目录管理模块的典型接口class CatalogManager { public: // 建表成功返回 true表已存在返回 false并置错误信息 bool createTable(const std::string tableName, const std::vectorAttribute attrs, const std::string primaryKey); // 根据表名取表结构找不到返回 nullptr const TableInfo* getTable(const std::string tableName) const; private: std::unordered_mapstd::string, TableInfo tables_; };createTable 的参数里有一个地方值得多看一眼primaryKey。很多课程版实现会把主键直接当作索引来建也就是说 createTable 不仅要写目录还要调用 index_manager 创建一个索引文件。这个侧的调用关系在源码里往往藏得比较深你读代码时容易只看到“记录文件被创建”而忽略“索引文件也被创建了”。我一般会在这里验证一下建完表后去数据目录看文件列表。如果每个表对应两个文件一个以 .data 结尾存记录另一个以 .idx 结尾存索引那就说明建表时确实同步建立了索引。这一步确认了后面查主键才会快。目录管理还有一个容易出问题的点表结构要不要落盘。有的课程版为了简化把表结构存在内存退出程序就丢了有的会序列化到一个 catalog 文件。你可以在启动 MiniSQL 后建一张表退出再重进执行 SHOW TABLES 或者直接 SELECT看这张表还在不在。如果不在说明这个版本的 catalog 没有持久化属于正常设计但你在做课设答辩时一定要能说清楚这一点否则会被问住。3.3 动手实验连续建三张表观察磁盘文件的变化这一步是帮你把“表”和“文件”两个概念对应起来建议照着走一遍# 在 MiniSQL 交互模式下依次执行 CREATE TABLE student (id INT, name CHAR(20), PRIMARY KEY(id)); CREATE TABLE course (cid INT, cname CHAR(30), PRIMARY KEY(cid)); CREATE TABLE sc (sid INT, cid INT, score INT);然后在另一个终端里看数据目录ls -lh data/ # 预期能看到每张表分别对应的数据文件与索引文件你会发现“建表”这件事落到最底层不过就是创建几个空文件。但“空文件”里其实已经写入了页面头和目录信息所以文件大小不会真的是 0一般是 4KB 或者 8KB取决于页面大小定义。MiniSQL 的数据目录位置通常在源码包根目录下有的是 data/有的是 db/有的直接把文件名用表名命名。看文件大小和文件个数能帮你快速判断这个版本的文件组织方式也能在后续排查“插入不进去”时快速定位问题范围——如果文件都没创建出来那问题一定出在 catalog 或建表流程而不是 record_manager。4. B 树索引与 SQL 解析从词法分析到索引选择4.1 SQL 解析递归下降还是 Yacc 生成两个极端怎么选MiniSQL 的解析器一般有两种写法。一种是用 Flex/Bison 生成词法分析和语法分析代码优点是文法规则写在 .y 文件里结构清晰缺点是生成出来的 C 代码可读性差调试时经常要对着生成的 tab 文件看半天。另一种是纯手写的递归下降解析器每个语法规则对应一个函数代码量略大但每一行都是人能读懂的。课程版里手写递归下降更常见因为它能避开 Flex/Bison 的环境依赖——很多同学在 Windows 上折腾半天装不上 bison最后都改成手写了。递归下降的核心套路是这样// 伪代码骨架递归下降解析 SELECT 语句 // 真正的实现里每个函数返回是否解析成功失败时打印错误 bool parseSelect() { expect(TOKEN_SELECT); // 吃掉 SELECT 关键字 parseSelectList(); // 解析列名列表 if (match(TOKEN_FROM)) { // 前瞻判断是否有 FROM parseTableList(); // 解析表名列表 if (match(TOKEN_WHERE)) { parseCondition(); // 解析 WHERE 条件 } } return true; }expect 和 match 是这套解析器的两个“原语”。expect 表示“当前位置必须是我预期的那个 token如果不是直接报语法错误”match 则是“看看当前 token 是不是我想要的是就吃掉、返回 true不是就返回 false、不消费 token”。这个差异决定了你能否在不消费 token 的情况下做前瞻判断——理解这一点对读解析器代码非常关键。调试解析器有一个血泪经验不要拿复杂的嵌套 SQL 去测先拿最简单的单表查询验证链路。比如先跑 SELECT * FROM student; 再逐步加 WHERE、加多字段条件。解析器报错时基本不会告诉你“第几行第几列”这种友好信息它只会吐出一个 internal error这时候要自己判断是词法阶段 token 切分错了还是语法阶段组合错了。4.2 B 树实现要点插入路径、分裂时机与叶子链索引模块是 MiniSQL 代码里最值得精读的部分。课程版一般要求实现 B 树因为它的查询和范围扫描性能都稳定也最能体现“磁盘访问次数由树高决定”这个数据库原理课上的经典结论。关注插入操作即可覆盖 B 树 80% 的核心逻辑。一个典型的插入函数大概是这样的结构// B 树插入主流程课程版实现的常见骨架 bool BPlusTree::insert(const KeyType key, const RecordId rid) { if (root_ nullptr) { root_ newLeafNode(); // 空树先建一个叶子节点 } Node* newNode nullptr; bool ok insertRecursive(root_, key, rid, newNode); if (newNode ! nullptr) { // 叶子节点被分裂生成新的根树高加 1 root_ newInternalNode(root_, newNode); } return ok; }这里的 insertRecursive 是递归插入从根节点出发根据 key 的大小比较选择下一层子节点一直走到叶子节点把 key 和记录位置插进去。如果叶子节点的 key 数量达到上限就需要分裂——把一半 key 分给新的兄弟节点然后把新节点的最小 key 上抛给父节点。分裂是最容易写错的地方。常见的错法有两种一是分裂时忘记更新父节点的指针导致新叶子节点“悬空”查询时明明有数据却查不到二是分裂后没有维护叶子节点之间的链表指针导致范围扫描时无法从当前叶子跳到下一个叶子。课程版 B 树一般要求叶子节点之间用链表串起来这样才能支持 SELECT * FROM t WHERE id BETWEEN 1 AND 10 这类范围查询——这条链表就是范围扫描的物理基础。读这段代码时建议盯着三个变量看节点可以容纳的 key 数量上限常见是 3 或者 4取决于阶数定义、key 在新旧节点之间的分配比例、分裂后父节点插入的新 key 是“左边节点的最大 key”还是“右边节点的最小 key”。这三个点的约定不一致代码就会错得离谱而且编译还不会报错。4.3 谓词下推与索引选择为什么你的查询没走索引很多课程版 MiniSQL 有一个“伪优化”只要 WHERE 条件里的列有索引执行器就选择索引扫描否则退化成全表扫描。这个逻辑的实现大概长这样// 执行计划选择教学版常见简化逻辑 if (condition ! nullptr indexExistsOn(condition.column)) { plan new IndexScanPlan(table, condition); // 走 B 树按 key 定位 } else { plan new TableScanPlan(table); // 全表扫描逐条判断条件 }这个简化逻辑在数据量小的时候看不出问题甚至会让初学者产生一个误解只要建了索引就一定快。真实项目里索引选择要看过滤度和数据量。假如一张表只有 100 条记录全表扫描一页就能读完而走 B 树还要先做几次节点访问开销反而更大。课程版通常不做这层“是否值得走索引”的成本估算所以你在测试时容易观察到索引查询比全表扫描更慢的怪现象——这其实不是源码 bug而是优化器缺失导致的正常表现。谓词下推也值得多提一句。真实数据库中像 WHERE id 1 AND name Alice 这样的条件应该在读取记录之前就尽量缩小范围。MiniSQL 课程版大多只支持单列等值条件走索引多列条件直接全表扫描。所以如果你在测试时写了两个条件的 WHERE发现它不走索引先不要急着怀疑源码很可能是这版实现根本没有做多列索引或索引合并。5. 避坑与排查跑 MiniSQL 最常见的五个翻车现场5.1 建表成功但插入时提示 “table not exist”现象CREATE TABLE 返回成功SHOW TABLES 也能看到表但紧接着 INSERT 就报错说表不存在。原因目录管理的信息只写进了内存没有持久化到文件或者持久化逻辑在插入时没有重新加载目录。还有一种情况是建表时创建了数据文件但目录表里登记的表名和文件名映射不一致导致插入时按文件名找表失败。解决先看 catalog_manager 有没有独立的 save/load 接口。如果有检查建表成功路径上是否调用了 save如果没有确认这个版本是否根本不支持跨会话持久化。无论哪种情况你都需要在源码里找到“根据表名获取 TableInfo”的实现看看它是从内存 map 里查还是从文件里反序列化——这是定位问题的入口。5.2 删除记录后磁盘文件大小完全没有变化现象DELETE FROM student WHERE id 1; 执行成功记录也查不到了但 ls 看数据文件大小和删除前一模一样。原因这不是 bug。课程版 MiniSQL 的删除基本都是“标记删除”——把槽位的 length 字段置为 DELETE_FLAG但页面文件本身不收缩也不触发文件重写。文件大小不变说明删除操作根本没有动文件系统的元数据只在页内做了逻辑删除。解决确认该版本是否对删除记录做空间复用。可以连续插入 10 条再全删掉再插入 10 条看插入是否会复用原来的槽位。如果新插入记录占用的文件大小没有翻倍说明槽位复用生效。如果你需要文件物理收缩那只能自己写一个 VACUUM 风格的整理逻辑把存活记录搬到一个新文件再替换旧文件。5.3 主键等值查询比不带索引 WHERE 还慢现象建了主键索引执行 SELECT * FROM student WHERE id 1; 但耗时和不带条件全表扫描差不多甚至更慢。原因两个层面。第一数据量太小全表扫描可能只需要读一个页面B 树反而要从根节点沿路径下探三层左右节点访问次数更多。第二更值得警惕的是索引查询实现里的“回表”逻辑——通过索引找到 RecordId 后还要再回数据文件按槽位读取记录这个两步操作如果被实现成了全文件扫描那索引就等于白建了。解决先把数据插到几千条以上再测避免小数据量干扰判断。如果还是慢去 index_manager 里看查找流程拿到 key 之后是通过 RecordId 直接定位槽位还是遍历页面找匹配记录后一种实现本质上是“索引外表、查询内核”复杂度是 O(n) 而不是 O(log n)这种版本不管数据多大都跑不过全表扫描。5.4 code 在 g 上编译不过报错信息看不懂现象源码在作者的 Visual Studio 环境里能编译换到 Linux 的 g 上直接报一堆错误最常见的是找不到 to_string、std::stoi、头文件缺失。原因课程版 C 代码大多写于较早年代用的是 C98/03 风格而 stoi、to_string 是 C11 才引入的还有一部分源码依赖了宽松的头文件包含比如在没 include string 的情况下用了 std::string老式编译器加上宽松选项能过严格模式下必挂。解决编译时显式指定 C11 标准把缺失的头文件按需补上# 在 Makefile 或 CMakeLists 里加上 C11 标准 g -stdc11 -o minisql main.cpp interpreter.cpp record.cpp index.cpp如果报的是 to_string 相关错误最省事的做法是写一个小工具函数替代避免改动大量业务代码用 sprintf 配合 char 缓冲区转换数字。这里要提醒一句跨平台编译报错时优先看是不是标准版本不匹配不要盲目改业务逻辑不然会引入新的问题。5.5 多表查询结果列顺序错乱或者连接结果重复现象执行 SELECT * FROM sc, student WHERE sc.sid student.id; 结果里列的顺序跟建表顺序对不上或者同一个学生对上了多门课导致重复行。原因列顺序错乱大概率是执行器拼接结果时没有按照 SELECT 列表的顺序来而是按“第一个表所有列 第二个表所有列”的物理存储顺序拼接了。结果重复则往往是因为连接条件没写全产生了笛卡尔积的中间结果过滤步骤没有在页面扫描阶段提前截断。解决读 executor 层的 tuple 拼接逻辑确认它读取字段时用的是“列名 → 表 → 偏移”的映射而不是“按表顺序遍历所有列”。至于笛卡尔积问题课程版一般不搞连接优化老老实实把连接条件写进 WHERE 就能规避大部分重复行。如果你要拿它应付课设演示多表查询时务必预先设计好能正确连接的 SQL不要在答辩现场临时拼语句。6. 把 MiniSQL 当实验台三个验证技巧与一条自查清单6.1 用同一条 SQL 验证索引是否真的生效没有 EXPLAIN 命令就自己造一个对比实验。先不建索引执行查询再建索引执行同一条查询观察两者的文件访问数量或耗时差异。MiniSQL 可以这样测-- 第一次未建索引 SELECT * FROM student WHERE id 1024; -- 建索引 CREATE INDEX idx_id ON student (id); -- 第二次同一条件 SELECT * FROM student WHERE id 1024;如果该版本有日志输出可以看到第二次查询读取的页面数明显减少如果没有日志就插入几千条数据后再比较耗时。这个技巧我在拆每个数据库源码时都会用它能直接验证你想看的索引代码到底有没有被执行器调用。6.2 事务回滚的边界什么能救、什么救不了多数课程版 MiniSQL 不实现完整 WAL 日志所谓事务只是把一系列操作门面化失败不一定能真正回滚。我建议拿到源码后第一件事就是找日志模块如果没有日志目录默认它回滚只能恢复内存状态无法恢复磁盘文件。演示时不要拿“事务中途断电”这种场景去测试那是自找麻烦。用它做做“批量插入失败后内存状态还原”这类实验就够了。6.3 从这套源码里带走的三条习惯第一读源码先读接口后读实现先搞清楚一个函数被谁调用、影响什么再去看它内部怎么写。第二遇到“数据对不上”的问题先怀疑记录槽位和索引映射不要急着改算法。第三每改一处逻辑用一条最小 SQL 回归验证避免问题滚雪球。从那以后我每次拆这类课设源码都强制自己先写一张“模块调用顺序表”再开始动手改代码。这个习惯帮我避开了至少五次“改完索引忘改记录”的低级失误。这套 C MiniSQL 源码最适合的用法就是你把它拉下来先原样跑通再做一个小改动——比如给 B 树加一个范围查询接口或者给记录模块加变长字段支持。任何一项能独立做完你对数据库的认知都会上一个台阶。希望帮到你。本文还有配套的精品资源点击获取
