MiniSQL源码实战：从C++课程设计读懂数据库内核

简介这是一份基于C实现的MiniSQL数据库管理系统源码面向高校数据库课程学生与底层内核开发者可作为CMU15445 BusTub框架的扩展实验参考解决从SQL解析到存储执行全链路的入门难题。资源共389个文件压缩包仅1.07MB核心部分由头文件与CC/CPP源文件组成其中头文件用于模块接口声明源文件承载缓冲池管理、B树索引、记录管理、元数据目录及基于锁的事务并发控制等实现此外还包含CMAKE构建脚本、Python自动化测试、Yacc语法定义等辅助开发文件。目前已有79人学习。读者通过阅读和编译此工程既可对比学习数据库各核心模块的协作流程又能深入理解数据页淘汰、索引增删查与锁调度的具体编码思路支持在现有框架上二次开发适用于课程实验、期末项目或数据库内核入门研究。1. MiniSQL是什么一份C课程设计源码值得读懂而不是跑通就删数据库管理系统课程设计周很多人的状态是从网上下到一个“基于C的MiniSQL数据库管理系统.zip”解压make跑通几条 SELECT 就认为完事了。等到面试被问一句“你的 B树索引是怎么维护的”直接哑火。关于C的MiniSQL它不是一个工业级数据库它是一套麻雀虽小五脏俱全的教学源码覆盖了SQL解析、表管理、记录存储、B树索引和简单执行引擎。你这门课值不值得做取决于你从这份源码里拿走多少而不是能不能跑。本篇文章的目标很直接不只让你看懂这类源码怎么运行更让你理解它背后每一层在解决什么问题拿到其他源码包也能照方抓药。这类项目不算很大但它非常适合想从零搞清楚“数据库到底怎么工作”的开发者。2. 拿到源码先别编译MiniSQL的模块划分与三个关键入口文件很多初学者拿到 zip 包第一件事就是双击 Makefile 编译然后被一堆编译错误劝退。我一般会先按住手花半小时把目录结构过一遍搞清楚一件事数据库管理系统的源码永远是“解析、执行、存储”三件事在多个文件里跳来跳去。你先把这些跳动的路线画出来编译只是填充细节。2.1 MiniSQL 的经典三层结构解析层、执行层、存储层你打开任意一份 MiniSQL 源码大概率能看到这三个层次。第一层是解析层一般叫 Interpreter 或者 Parser任务是把用户输入的 SQL 文本变成程序能理解的结构化中间表示。第二层是执行层也叫 Executor拿到中间表示后负责决定先做什么、后做什么比如先查表还是先建索引。第三层是存储层对应 TableManager、RecordManager、IndexManager 这类命名负责管理文件里的页面、记录和 B树节点。这个结构化分层不是 MiniSQL 原创MySQL、PostgreSQL 也是这么拆的。好处是每一层只通过接口和上下层对话你把解析层从手写改成 lex/yacc 生成的不影响存储层。一般 MiniSQL 源码里这三个层分别对应不同的 .h 和 .cpp 文件解析层SQLParser 或 Interpreter包含词法扫描函数和语法分析函数。执行层API 层封装比如execSelect、execInsert这类函数负责调度存储接口。存储层表和索引的文件读写是最底层的字节操作。读源码时建议从执行层的函数列表入手比如execDropTable调用了哪些存储函数顺着调用链一层层往下读。这个调用链读通后你看到任何一句 SQL脑子里就能立刻浮现它将要触发的文件路径和内存结构这会成为调试时最大的本钱。2.2 先读这三个文件往往比先编译更有价值具体到这类 MiniSQL 源码有三个文件基本可以视为命门。第一个是定义表结构 schema 的头文件比如Table.h里面定义了字段名、字段类型、字段长度它是整个系统的“世界模型”。第二个是RecordManager或RecordFile的实现记录怎么读写、怎么标记删除都在这里。第三个是BPlusTree或IndexManager的实现文件这是所有源码里最容易写崩的部分也是面试官最可能问到的部分。为什么先读这三个因为数据结构决定算法也决定你能在哪调试。先看 schema 定义你能知道系统支持哪些数据类型比如 int 占 4 字节、float 占 4 字节、char(n) 是定长字符串如果字符串按定长存储那么写记录时不足 n 字节的部分必须填充否则后续读出来的字符串很可能带着垃圾尾。// Table.h 里的典型字段结构定义 struct Field { std::string name; // 字段名 enum { INT, FLOAT, CHAR } type; // 字段类型 int length; // 仅 CHAR 类型有效表示该字段最大长度 };这段结构体定义说明了三件事。name是字段的对外名字SQL 里的列名最终都映射到这里。type枚举决定了序列化和比较的方式int 和 float 按数值比较char 按字符串比较。length对 char 类型来说是硬约束往表里插数据时写入按这个长度补齐取出时也要按这个长度截断否则会出现“字符串后边挂着一串不可见字符”的经典翻车现场。2.3 编译命令和 Makefile 调整不想让报错追着跑就先统一标准拿到源码后先看根目录有没有 Makefile 或 CMakeLists.txt。正常 MiniSQL 源码会带一个 Makefile核心编译参数通常是g -stdc11 -O2 -Wall -o minidb \ main.cpp \ parser.cpp \ executor.cpp \ record.cpp \ btree.cpp \ -lpthread这条命令里每个参数都有讲究。-stdc11指定语言标准很多老源码用 C 早期语法比如把NULL当 0 用在 C11 里虽然兼容但会出警告-O2开优化B树在 debug 模式和无优化模式下性能差距极大课程测试时如果跑大批量插入优化开关直接影响能否在超时前完成-Wall是为了把可疑代码暴露出来比如未初始化指针、类型转换。如果你是在 Windows 上用 Visual Studio 打开这套源码常见问题是 C 标准库头文件差异。老源码里常写#include stdio.h和#include stdlib.h在 VS 里也兼容但不建议换掉。如果在 macOS 上编译偶尔会遇到strcasecmp这类 POSIX 函数不可用需要自己实现一个大小写不敏感比较函数或者用std::transform转小写再比较。编译时有一个经验第一次编译不要带-O2先用-g -Wall保证能断点调试。因为优化开高后代码的执行顺序会被重排你打断点看到的变量值可能已经变了。跑通功能后再开-O2做性能验证。3. 把 SQL 变成可执行动作解析器的词法、语法与语义三层关卡解析器是整个 MiniSQL 源码中最“像编译原理”的部分也是很多第一次读源码的人最容易迷路的地方。很多源码包里写得很乱因为解析器天然充满分支判断和状态流转。但只要你按词法、语法、语义三层去读就能理清头绪。3.1 词法分析Token 的类型与边界问题词法分析的任务是把用户输入的一长串字符切分成“单词”这些单词叫 Token。MiniSQL 里的 Token 大致有几类关键字select、insert、delete、标识符表名、列名、数值常量整数和浮点数、字符串常量单引号括起来的内容、运算符和界符括号、逗号、分号、等号。// 一个典型的 Token 定义 struct Token { enum Type { KEYWORD, // 关键字 IDENTIFIER, // 标识符表名、列名 INTEGER, // 整数常量 FLOAT, // 浮点常量 STRING, // 字符串常量 OPERATOR, // , ( ) ; 等 END // 输入结束 } type; std::string text; // 原始字符串 int intVal; // 整数常量时可用 float floatVal; // 浮点常量时可用 };注意这里的边界问题词法分析最容易出 bug 的地方是字符串常量里出现空格和特殊字符。比如insert into student values (1, li ming)如果词法扫描器见空格就断 Token那li和ming会被切成两个 Token后面的语法分析直接报错。正确做法是遇到单引号后一直读直到下一个单引号中间的所有字符都属于这个字符串常量。很多源码在这里因为指针没有正确越过结尾引号导致读出来的字符串少一个或多一个字符进而影响后续记录存储。3.2 递归下降语法分析parseSelect 的骨架和参数含义词法分析把字符切成 Token 流后语法分析的任务是判断这些 Token 串起来是否符合 SQL 语法同时把关键信息提取出来。MiniSQL 的语法分析基本都用手写递归下降实现因为它简单直接不需要引入 extern 工具生成代码。class Parser { public: // 顶层入口根据第一个 Token 决定进入哪条 SQL 解析路径 void parse() { if (lookahead.type Token::KEYWORD) { if (lookahead.text select) parseSelect(); else if (lookahead.text insert) parseInsert(); else if (lookahead.text delete) parseDelete(); else if (lookahead.text create) parseCreate(); else if (lookahead.text drop) parseDrop(); else error(unexpected keyword: lookahead.text); } else { error(SQL must start with a keyword); } } private: void parseSelect() { match(select); // 先解析列名列表直到发现 from while (lookahead.text ! from) { selectCols.push_back(lookahead.text); match(Token::IDENTIFIER); if (lookahead.text ,) match(,); } match(from); tableName lookahead.text; match(Token::IDENTIFIER); // where 子句是可选的 if (lookahead.text where) { match(where); condition parseCondition(); } expect(;); } };这段代码的逻辑是从select这个关键字开始先收集目标列名遇到from后读表名再往后看有没有where如果有就去解析条件表达式。这里最容易写错的参数是parseCondition()它要处理、、和逻辑运算and、or。不少 MiniSQL 只支持单条件 where如果你的源码支持where age 18 and name tom条件解析必须递归地处理左操作数、运算符、右操作数然后再处理与/或。写的时候要注意and优先级高于or否则a or b and c的含义就错了。3.3 语义检查表不存在、列不存在、类型不匹配语法正确不等于可以执行。语义检查负责判断 SQL 里提到的表名是否在系统目录中存在列名是否在该表中存在插入的值类型是否匹配。MiniSQL 里通常有一个 Catalog 模块维护这些元数据一张“表之表”记录有哪些表每张表有哪些字段哪个字段建了索引。语义检查放在语法分析之后、执行之前的时机最好。很多初版源码把检查散落在执行函数里结果就是每执行一个语句都要重复做同样的事。合理的做法是构建一个Query结构体把解析结果汇总进去struct Query { std::string type; // SELECT / INSERT / DELETE / CREATE std::string tableName; std::vectorstd::string columns; Condition cond; // where 条件 };查表是否存在时看一眼 Catalog 里的 map 即可不存在则直接报错。查列是否存在则遍历该表的字段名列表O(n) 就够。这里要注意的是类型匹配如果你往 int 字段里插入字符串需要在语义检查时就拦截不要等到存储层序列化时才发现问题那时定位栈会复杂得多。我遇到过一份源码语义检查只做了一半查了表存在性没查列存在性结果 INSERT 时按列名找字段下标下标记为 -1然后照样写记录写完数据读了三个月才发现所有插入都是错位存储。检查这种问题最简单的方式是给语义检查函数写一行日志每次检查通过时打印“table ok, columns ok, type ok”跑一批 SQL 就能看到哪层拦截失效。4. 记录怎么落盘索引怎么加速存储层与 B树的实现细节解析和语义检查只是前端真正决定 MiniSQL 能不能存得住数据的是存储层。这里的核心目标是理解两个问题一条记录在文件里长什么样以及索引结构如何改变记录的查找路径。4.1 定长记录的序列化字段布局与内存对齐MiniSQL 的表文件一般按定长记录存储因为定长记录计算偏移极其简单第 n 条记录的位置就是文件头大小 n * 记录大小。极少数实现用变长记录那要额外引入偏移表复杂度高出不少。课程设计里除非题目明确要求否则不推荐做变长。// 记录序列化把结构体写入 char 数组 void serializeRecord(const Record rec, char* buf, const TableSchema schema) { int offset 0; for (size_t i 0; i schema.fields.size(); i) { if (schema.fields[i].type Field::INT) { int val rec.ints[i]; memcpy(buf offset, val, sizeof(int)); offset sizeof(int); } else if (schema.fields[i].type Field::FLOAT) { float val rec.floats[i]; memcpy(buf offset, val, sizeof(float)); offset sizeof(float); } else { // CHAR // 定长字符串不足 length 的部分填 \0 memset(buf offset, 0, schema.fields[i].length); memcpy(buf offset, rec.strs[i].c_str(), std::min((int)rec.strs[i].length(), schema.fields[i].length)); offset schema.fields[i].length; } } }这段代码的核心是维护offset游标每写完一个字段就前进对应字节数。这里最隐蔽的坑是 C 结构体对齐如果你直接把整条记录定义为一个 structint 和 char 混排时编译器会自动填充 padding 字节同一个 struct 在不同编译器下大小都可能不同。上面这种逐字段写入 char 数组的方式主动避开了结构体对齐问题每个字段的偏移都是纯手工计算得到的结果可预测。定长字符串补齐\0是关键操作否则后续strcmp或std::string构造会读越界。4.2 表文件组织文件头加上数据页的平面结构MiniSQL 的表通常就是一个二进制文件文件开头是文件头存记录数、每条记录大小、已删除位置位图等元信息之后全是一条接一条的定长记录。删除一条记录时不会物理删掉那条数据而是标记删除位为 1新插入时优先复用这些空位。const int HEADER_SIZE 128; // 文件头预留 128 字节 const int BITMAP_OFFSET 32; // 位图从偏移 32 字节开始 void insertRecord(const Record rec) { fstream file(student.tbl, ios::binary | ios::in | ios::out); int slot findFreeSlot(file); file.seekp(HEADER_SIZE slot * recordSize); serializeRecord(rec, buf, schema); file.write(buf, recordSize); file.close(); }文件头预留 128 字节算是比较保守的做法里面即使只用了 64 字节也能为以后扩展留下空间。BITMAP_OFFSET 32意味着位图从第 32 字节开始自己定义文件格式时这个布局必须前后一致。常见的坑是写入时用了seekp读取时用了seekg在同一个 fstream 上两者状态互相干扰导致读到错误位置。解决方法是读取时重新 open 文件或操作之间调用clear()恢复流状态。这里有一个需要自己拿主意的参数每条记录大小上限。如果 schema 里定义了 5 个 char(255) 字段一条记录就是 1275 字节文件头 128 字节微不足道。但如果 char 长度设到 65535记录大小会非常大文件读写效率肉眼可见地下降所以课程设计里 char 长度通常限制在 255 以内这是 MiniSQL 项目里常见的隐含边界。4.3 B树索引为什么用它以及入门实现的关键参数MiniSQL 要求必须创建索引来加速查找绝大多数实现选择 B树而不是哈希索引原因是B树支持范围查询条件哈希只支持等值B树永远平衡查找时间稳定在树高级别叶子节点之间有链表指针顺序扫描整棵索引树非常高效。哈希索引虽然在单条等值查询上可能更快但不满足课程设计对“支持范围查询”的考察要求。B树的几个关键参数必须理解阶数 order每个节点最多允许的子节点数。order 越大树越矮但单个节点内的线性查找成本上升。叶子节点存实际键值和记录 ID内部节点只存键值和指向子节点的指针不存记录。分裂策略当节点键值数超过 order 时必须分裂成两个节点并把中间键提升到父节点。// B树叶子插入找到叶子后按序插入超过阶数就分裂 bool insertKey(BTreeNode* leaf, const BKey key, const RecordId rid) { // 用 upper_bound 找到第一个大于 key 的位置 auto it std::upper_bound(leaf-keys.begin(), leaf-keys.end(), key); size_t pos it - leaf-keys.begin(); leaf-keys.insert(it, key); leaf-recordIds.insert(leaf-recordIds.begin() pos, rid); // 超过阶数上限后触发分裂 if (leaf-keys.size() order) { splitLeaf(leaf); } return true; }upper_bound是标准库里专为已排序序列做的二分查找插入前 keys 有序插入后依然有序。分裂时机是判断keys.size() order如果你是初学者建议把分裂逻辑独立成单独函数先写叶子分裂再写内部节点分裂最后写根节点分裂。因为根节点分裂会产生新的根那部分容易写崩。分裂的时候有一个经常翻车的选择中间键是上提到父节点还是留在左子节点。对于叶子节点中间键通常留在左子节点同时复制一份上提到父节点因为叶子节点的键必须全部保留对于内部节点中间键上提到父节点后不会再留在原节点。如果你的源码搞反了这个索引会丢失键值表现为明明插入了数据索引却查不到。这种 bug 非常难发现因为表扫描能查到只有强制走索引时才暴露。5. 避坑合集MiniSQL 调试里最常翻车的 5 个现场在调试这类数据库管理系统源码时经验往往比能力更值钱。下面这五个问题出现的概率极高每一条我都用“现象、原因、解决办法”三段式记录方便快速对照。5.1 复现写进去的数据读出来是乱码且越界崩溃现象插入一条含 char 字段的记录再 SELECT 出来字符串尾部出现一串不可见字符当字符串长度接近字段上限时程序偶尔崩溃在 memcpy。原因字符串没有填充\0或者 memcpy 拷贝的长度超过了目标字段长度直接越界写坏内存。定长 char 字段写入时长度必须严格限定为min(字符串长度, 字段长度)超出部分不写。再有是读端问题读出时按字段长度拷贝到临时缓冲区但临时缓冲区没有多留一个字节放结束符构造std::string时读到缓冲区末尾后面继续读。解决写入时统一先memset整个字段区域为 0再拷贝。读出时分配length 1个字节强制在buf[length] \0。字符串比较用strncmp或转成std::string再比较不能用strcmp因为填充的\0可能让比较提前结束。5.2 复现SELECT 语句查询引号内字符时查不到或查错数据现象where name tom能查到换成Tom就查不到或者插入带空格的li ming后按li去查居然也能命中。原因比较时用了区分大小写的精确匹配MiniSQL 一般按大小写敏感处理这本身不是 bug问题在词法和语义层的长度裁剪。如果截断逻辑把li ming的尾部截掉了索引里存的 key 就变成li导致后续任何li*前缀都能命中。解决先确认词法层读出的字符串是否完整。在解析后不打断点直接打印 token 的 text 值与长度肉眼确认引号边界。字符串比较统一走一个函数先比较长度再逐字节比较两处逻辑不要各写各的。5.3 复现建了索引查询却仍然全表扫描性能上不去现象插入几万条记录后做等值 SELECT 很快但范围查询非常慢或者 EXPLAIN 显示没走索引。原因执行器代码里根本没有“根据 where 条件判断是否能走索引”的逻辑。很多简易 MiniSQL 只把索引用于唯一性判断查询还是顺着表文件从头扫到尾。再有一种情况索引键值用的是字符串但条件里的字符串没有走索引定义时的比较规则索引查找路径永远匹配不上。解决给执行器加一个条件判断函数条件字段上有索引且运算符是、、时先查 B树获取一组 RecordId再按这些 ID 读记录否则退回表扫描。判断逻辑里要区分主键和普通索引键的边界。5.4 复现连续执行大量 INSERT 后内存占用暴涨最终 OOM现象程序跑 2 万条 INSERT 后内存占用到几个 GB随后崩溃。检查代码发现索引插入节点用的new但删除表或关闭数据库时没有逐节点回收。原因B树节点在堆上分配析构函数只释放了根节点子节点全部泄漏。更隐蔽的是缓存池BufferPool里的页面没有做 LRU 淘汰新页面不断加入旧页面永不移除。解决给 B树写一个destroyTree(Node*)的递归删除函数析构时调用。BufferPool 限定最大页面数超过后按最近最少使用淘汰把脏页写回文件。这一步看似无趣但实验数据一大没有它程序必崩。5.5 复现where 条件的逻辑运算结果不对and和or混用时查错现象where age 18 or age 16 and name tom按直觉应该是or左边整体和and右边组合但结果却是两边的条件被平级处理超出预期。原因解析条件表达式时没有考虑运算符优先级。如果不做层级区分所有布尔运算符按同一优先级从左到右执行结果必然乱。C 里优先级高于||SQL 里and优先级也高于or解析器必须在递归过程中优先吃掉and。解决条件解析拆两层parseAndExpr()里循环调用parseConditionAtom()处理单个比较表达式并以and连接parseOrExpr()里循环调用parseAndExpr()。这样上层先拆or下层再拆and优先级自然就对了。6. 从能跑到可控回归验证、两个进阶方向和一个收尾技巧当你把上面这些坑都填平MiniSQL 源码就算真正拿下了。接下来要做的不只是运行而是可控地运行。6.1 用 SQL 脚本做冒烟测试与回归验证写一个测试脚本覆盖建表、插入、修改、删除、查询、建索引、删表全部路径。每次改动后跑一遍只要任何一条 SQL 行为变化立刻知道改崩了哪里。用一个简单的 bash 循环可批量执行# 把测试用例按行写入 test.sql while read -r sql_line; do echo $sql_line ./minidb --sql $sql_line done test.sql这里比较关键的是结果对比不要靠人眼把每条 SQL 的输出重定向到文本文件再用diff对比上次的运行结果任何差异都会被精确定位到某一条语句。6.2 两个进阶方向事务日志与 ORDER BY第一个方向是加 WAL预写日志机制插入或删除前先追加一条日志记录崩溃后回放日志恢复数据这是数据库管理系统的核心可靠性保证。第二个方向是给 SELECT 的结果做内存排序实现 ORDER BY这能让你理解排序在数据库执行引擎里到底在哪个阶段介入是拿到全部记录后还是索引扫描过程中同步进行。6.3 收尾技巧用随机数构造数据集测索引边界很多课程设计卡在“数据量一大就崩”但手边又没有现成大数据集。最平常的解决办法是用 C 随机数生成测试数据循环插入 10 万条记录每条的键值用均匀分布随机生成。这样能逼出三个问题索引分裂是否稳定、文件是否无限膨胀、查询是否有性能拐点。养成这个习惯后遇到任何数据库源码我都会先写一段随机数灌压脚本再做功能测试——顺序反过来往往测不出真实问题。希望这些实战细节帮你在 MiniSQL 源码上少走弯路把课程设计变成真正的数据库内核入门课。本文还有配套的精品资源点击获取