简介这是一份基于C实现的MiniSQL数据库管理系统源码面向计算机专业学生、数据库课程设计者以及希望深入理解关系型数据库内核实现的学习者。项目参考CMU15445的BusTub框架兼容原MiniSQL实验要求完整实现缓冲池管理、B树索引、记录管理、持久化存储、SQL语法解析与执行引擎等核心模块并额外支持数据页分配回收状态的持久化。压缩包共包含377个文件以127个h头文件、100个cc和45个cpp源文件为主还包含Lex/Yacc词法语法分析代码、CMake构建脚本、Python辅助工具和测试用例整体仅1.05MB目录结构清晰便于快速定位与本地编译。目前已有80人学习。通过研读源码可掌握SQL语句经Parser生成语法树、再由Executor调度执行的全过程同时理解缓冲池替换策略、B树插入删除查找、记录管理以及数据页持久化的具体实现该工程可完整编译适合在课程设计或二次开发中参考使用。1. 基于C的MiniSQL数据库管理系统一堂把SQL从“会用”变“能写”的源码课你刚把一份“基于C的MiniSQL数据库管理系统”源码解压出来会发现文件数量不多但每个名字都很“硬”parser、record、bplus_tree、executor。很多人的 C 基础不错却从没碰过数据库内核而 MiniSQL 正是少数能从“写控制台程序”迈到“做一个有状态存储服务”的练手项目。它解决的问题很具体一条insert语句是怎么变成磁盘上的字节流一条select又是怎么把字节流还原成你能看到的表。对想补 C 功底、准备数据库方向面试或课程设计需要“能演示、能答辩”的人来说这份源码都值得照着拆一遍而不是只跑一下看个效果。2. 先拆清楚MiniSQL的要害一个数据库系统到底包含哪些部件MiniSQL 不算大但五脏俱全。很多人把它理解成“一份能跑通的 SQL 字符串匹配程序”这是课程设计翻车的第一步。真正决定它是不是数据库系统的是存储、解析、执行、索引、元数据这五部分能不能被独立替换。拿到源码后我通常不看主程序先找storage和parser目录这两个位置设计得干净整棵代码才能往下读。2.1 表与记录的存储设计为什么很多C实现选择定长记录MiniSQL 的典型起点是“定长记录”。所谓定长就是每张表的每一行在内存里占用的字节数完全一样int占 4 字节float占 4 字节char(n)直接占 n 字节。这样做的好处非常多——你可以用“行号”直接算偏移量可以用record_id page_id * slot_num slot_offset这种公式做定位排序和索引回表也都变得很简单。// 字段元数据一张表最多支持多少字段由字段数组大小决定 struct Field { int type; // 0: int1: float2: char int length; // char(n) 的 nint/float 强制为 4 char name[32]; // 字段名MiniSQL 一般限制不超过 32 字节 }; // 表级元数据用来描述一张表的完整行布局 struct TableMeta { char table_name[64]; Field fields[32]; int field_count 0; int record_length 0; // 关键参数单行定长长度供页面分配使用 };这里的record_length是第一个必须算对的参数。常见实现是meta-record_length 4 4 n这样逐项累加但如果你在字段后面补了padding就要把对齐字节也加进去。我一般会单独写一个compute_record_length()函数避免在创建表和执行插入时各算一遍结果不一致导致写入越界。定长记录还有一个隐性收益删除记录不需要压缩文件。被删除的槽位可以放进一个 free list新插入时优先复用。这个设计对 MiniSQL 的索引尤其重要因为记录物理位置不会因为“后续插入”而移动索引项里的 record pointer 一旦生成就是稳定的。如果哪个版本把varchar混进定长表你就得准备好面对一堆偏移计算崩溃。2.2 SQL解析分几步走词法、语法、AST到执行计划MiniSQL 的 SQL 子集很小create table、drop table、insert、delete、select、create index、drop index。虽然命令少解析部分却仍然是完整流程字符串先进入 lexer 切成 token再进入 parser 按语法规则生成 AST最后 executor 遍历 AST 执行。很多课程设计源码为了省事用find(from)加substr硬拆语句这在小规模测试下能跑但一旦 where 条件里出现and、括号或字符串常量立刻翻车。// 递归下降解析 select 的一个最小骨架 SelectStmt Parser::parseSelect() { expect(TokenType::SELECT); // 当前 token 必须是 select SelectStmt stmt; while (peek().type ! TokenType::FROM) { stmt.columns.push_back(consume(TokenType::IDENT).text); if (peek().type TokenType::COMMA) { advance(); // 跳过逗号继续读下一列 } else { break; } } expect(TokenType::FROM); stmt.table_name consume(TokenType::IDENT).text; if (peek().type TokenType::WHERE) { stmt.condition parseExpr(); // 放到表达式层继续递归 } return stmt; }这段代码看起来简单但背后有一个容易忽视的参数选择where条件到底在 parser 里生成树状表达式还是直接存成字符串传给执行器我强烈建议生成表达式树哪怕只是为了应付id 1 and age 30这种组合。表达式树里的每个节点可以带left、right、op三个指针执行时递归求值调试起来也比字符串重解析直观得多。AST 生成之后真正的“执行计划”在 MiniSQL 里通常很朴素单表查询就是全表扫描或索引扫描连接查询极少出现在 MiniSQL 需求里。所以执行器核心是一个 switch 语句按stmt.type分发到executeInsert、executeSelect、executeDelete。这已经足够展示数据库执行器的骨架也给后续加优化留了空间。2.3 索引用B树还是哈希MiniSQL的经典选择与理由MiniSQL 的索引选择基本是 B 树。哈希索引查等值很快但select * from t where id 100这种范围查询就无能为力而 B 树天然支持顺序扫描。另一个理由更实际B 树的叶子节点可以存记录指针中序遍历叶子节点就是有序输出能顺带解决order by的排序需求。// B树索引节点的最小表示ORDER 表示每个内部节点最多有几个孩子 static const int BPLUS_ORDER 4; struct BPlusNode { bool is_leaf; // true 表示叶子节点false 表示内部节点 int key_count; // 当前节点实际保存的键数量 int keys[BPLUS_ORDER - 1]; // 键数组按照从小到大排列 long long record_ids[BPLUS_ORDER - 1]; // 叶子节点记录在文件中的位置 int children[BPLUS_ORDER]; // 内部节点孩子页号 };这个结构是面试经常让你手写的“C 八股”节点分裂、父节点关键码上提、叶子节点链表拼接。MiniSQL 里最麻烦的不是节点结构而是“什么时候把分裂递归到根节点”。我会建议把分裂逻辑单独拆成splitChild(parent, child_index)而不是把分裂代码写死在insert里否则调试时每次都会在递归栈里迷路。还有一个容易被忽略的参数页面大小。B 树节点通常是 4KB 或 8KB和文件系统页面对齐。教学版 MiniSQL 经常把节点直接放在内存里关闭时整体写回这当然可行但如果你想让数据量超过内存就必须实现“按需从页面读节点”的方式。这两种做法的边界我会在后面避坑章节单独展开。3. 从零到能跑搭建MiniSQL源码工程的编译与命令行接口拿到源码后最怕的事是长期停留在“读代码”阶段。我建议第一件事就是把工程编译起来然后立刻跑通五个核心命令建表、插入、查询、删除、建索引。先让程序活起来再回头读代码你会发现理解速度比纯看快一倍。3.1 拿到源码包后推荐的文件布局与编译方法示例CMakeLists一个常见的 MiniSQL 源码包通常会有src和test两层目录src下面再按模块拆分。如果压缩包里没有 CMakeLists那你先要解决的问题是“用什么构建”。我一般会手动新建一个 CMakeLists按模块编译这样后续加单测和调试都方便。# 推荐的文件布局按模块分目录不要把源文件堆在根目录 minisql/ ├── CMakeLists.txt ├── src/ │ ├── parser/ # lexer.cpp parser.cpp AST定义 │ ├── storage/ # table.cpp record.cpp bplus_tree.cpp │ ├── executor/ # executor.cpp │ ├── catalog/ # 元数据与系统表 │ └── main.cpp └── tests/ # 简单的回归测试脚本cmake_minimum_required(VERSION 3.16) project(MiniSQL CXX) set(CMAKE_CXX_STANDARD 17) set(CMAKE_CXX_STANDARD_REQUIRED ON) # 按模块源文件编译避免链接时找不到符号 add_executable(minisql src/main.cpp src/parser/lexer.cpp src/parser/parser.cpp src/storage/table.cpp src/storage/record.cpp src/storage/bplus_tree.cpp src/executor/executor.cpp src/catalog/catalog.cpp ) target_include_directories(minisql PRIVATE src)这里的CMAKE_CXX_STANDARD是一个关键参数。很多老代码用register关键字或者隐式类型转换放到 C17 下会直接报错。如果你手里的源码很旧先把标准降到C14甚至C11比硬改源码更省时间。MiniSQL 项目对标准库依赖不高只要不用std::filesystemC11 完全够用。编译命令建议写成一条脚本cmake -S . -B build cmake --build build。源码包如果没有生成 build 目录这是正常现象压缩包里很少会带编译产物。跑通这一步之后你才算真正开始接触数据库管理系统。3.2 用 vscode 配置 c/c 环境跑通 MiniSQL 的调试会话MiniSQL 这类源码非常适合在 Visual Studio Code 里断点调试因为它包含大量上下文相关逻辑解析器要追踪当前 tokenB 树要追踪递归层级。如果只是用printf调试会非常痛苦。配置 c/c 环境的关键不在编译器而在“告诉调试器去哪里找源文件”。{ version: 2.0.0, tasks: [ { label: build minisql, type: shell, command: cmake -S . -B build cmake --build build, options: { cwd: ${workspaceFolder} }, group: build } ] }这个tasks.json的作用是让你在 VSCode 里按CtrlShiftB直接构建而不需要切回终端敲命令。构建之后launch.json里的program要指到build/minisqlcwd设为${workspaceFolder}。如果你用的是 Dev C 这类老 IDE我的习惯是先在命令行把工程编过再回去配 VSCode因为 MiniSQL 最常见的编译错误是源文件路径不一致这和 IDE 无关。断点不要打在 REPL 主循环上那个地方跳得太快。我通常会在Parser::parseSelect和BPlusTree::insert两处设断点前者看 token 序列是否被正确识别后者看节点分裂时 key 的移动是否正确。VSCode 左侧的调用栈面板能看到executor调用了谁这对理解“一条 SQL 覆盖了多少层代码”尤其有帮助。3.3 核心命令行接口执行“ create table / insert / select” 的最小实现MiniSQL 的入口通常是一个无限读取命令行的 REPL。这里有一个设计细节经常被忽视每行输入可能包含多个语句以分号分隔也可能用户跨行输入一条很长语句。为了降低实现难度我习惯先按行读取再用分号切分而不是在 lexer 里处理换行符。int main() { MiniSQL db; // 持有所有表、索引、元数据 std::string line; while (true) { std::cout minisql std::flush; if (!std::getline(std::cin, line)) break; try { // 一条输入可能包含多条以分号结尾的 SQL std::vectorstd::string statements splitStatements(line); for (auto sql : statements) { if (sql.empty()) continue; Node* ast db.parse(sql); db.execute(ast); } } catch (const std::exception e) { std::cerr Error: e.what() \n; } } return 0; }splitStatements要注意字符串常量里的分号比如insert into t values(a;b)就不应该被切开。我在实现时会在 lexer 层处理分号只有不在引号内的分号才作为语句边界。这种小地方正是 MiniSQL 源码最值得学的部分。执行器的核心逻辑我更倾向于“先模拟再加速”。execute接收 AST 后先走一遍表格元数据校验再按语句类型分发。例如InsertStmt需要逐字段校验类型SelectStmt需要先从 catalog 拿到表对象再决定全表扫描还是走索引。把这两步拆开命令行的响应速度会变慢但调试不会黑匣子值得。4. 把MiniSQL变成能存数据的系统持久化与事务的落地细节很多 MiniSQL 源码能做到“跑得通”但一重启数据全丢因为表结构和记录只活在内存里。真正的数据库管理系统必须解决持久化问题。MiniSQL 作为教学项目不需要做到 Postgres 那种 WAL 强度但至少要保证“正常关闭后数据还在异常关闭后能恢复或不崩”。4.1 文件格式与页面分配表数据和索引文件怎么写表数据的落盘文件一般分成两种一种是把所有记录顺序存放另一种是分页存放。分页存放更接近真实数据库也更容易配合 B 树。我常用的页面格式是页头记录当前页空闲位置页体存放定长记录槽位。// 页面头每个数据文件由多个 page 组成page 大小建议与 B树节点一致 struct PageHeader { uint32_t page_id; // 当前页号从 0 开始 uint32_t slot_count; // 槽位数量定长表里固定 uint32_t free_offset; // 下一个可用的记录起始位置 uint32_t free_size; // 空闲字节数用于诊断页是否写满 }; // 记录编码器把内存中的字段值转成可落盘的字节流 std::string encodeRecord(const TableMeta meta, const std::vectorFieldValue values) { std::string buf; buf.resize(meta.record_length, 0); int offset 0; for (int i 0; i meta.field_count; i) { const Field f meta.fields[i]; if (f.type 0) { // int 固定写 4 字节 int32_t v values[i].int_value; memcpy(buf.data() offset, v, 4); } else if (f.type 1) { // float 固定写 4 字节 float v values[i].float_value; memcpy(buf.data() offset, v, 4); } else { // char(n)不足补 \0 memcpy(buf.data() offset, values[i].char_value, f.length); } offset (f.type 2) ? f.length : 4; } return buf; }这里最容易翻车的参数不是memcpy本身而是offset的累加规则。如果某个版本的源码在char字段后加了padding你必须同步修改encodeRecord和decodeRecord否则就会出现“写入一个字节读出另一个字节”的玄学现象。另一个常见错误是直接用sizeof(Record)写文件结构体内部有内存对齐不同编译器算出来的大小不一样。逐字段序列化虽然慢但跨平台稳定是 MiniSQL 源码最值得照搬的写法。4.2 日志与回滚的取舍教学版MiniSQL该做WAL还是直接覆盖写成熟数据库的持久化要保证原子性需要 redo/undo 日志。但 MiniSQL 的场景是单线程、命令式执行很多源码选择“直接覆盖写文件”好处是代码短坏处是执行到一半断电容易损坏表文件。我自己的做法是折中用一个命令日志文件记录已经执行的 SQL启动时重放这样即使数据文件写坏也可以从日志重建最近状态。// 一个极简的 SQL 日志实现只负责追加不负责删除 class SQLLog { public: explicit SQLLog(const std::string path) : log_path_(path) {} void append(const std::string sql) { std::ofstream f(log_path_, std::ios::app | std::ios::binary); if (!f) { throw std::runtime_error(cannot open sql log file); } // 先写长度再写内容便于启动时按长度切分语句 uint32_t len static_castuint32_t(sql.size()); f.write(reinterpret_castchar*(len), 4); f.write(sql.data(), len); f.flush(); } private: std::string log_path_; };这个日志的设计要点是“只追加不修改历史”。每次执行写操作前先调用append(sql)再执行真正修改。启动时按长度字段逐条读出 SQL在内存里重放一遍。这里有一个重要权衡在断电恢复时只重做已经追加日志但可能尚未写盘的语句不会出现重复插入前提是每条 SQL 都要具备幂等性。如果你的 MiniSQL 不打算用唯一索引重放insert确实可能重复但课程设计一般不做这么深的恢复只要保证“日志追加先于数据写盘”就已经能应对大部分崩溃场景。4.3 表清单和元数据存储一个简单的system catalog实现数据库管理系统需要知道自己有哪些表、每张表的字段是什么这就叫系统目录。MiniSQL 的实现通常是在数据目录下放一个固定名称的元数据文件比如catalog.txt或tables.meta。这个文件的格式设计得越简单越好我推荐每一行描述一张表。// 把表元数据序列化成一行文本便于作为 system catalog 持久化 std::string Catalog::serializeTable(const TableMeta meta) { std::ostringstream os; os meta.table_name | meta.field_count; for (int i 0; i meta.field_count; i) { os | meta.fields[i].type | meta.fields[i].length | meta.fields[i].name; } return os.str(); }这里使用|作分隔符是因为字段名和表名里通常不会出现这个字符。读取时按|拆分逐段还原成TableMeta就能实现“启动时扫描目录自动感知所有表”。需要提醒的是不要把serializeTable和页面文件混在一个目录里否则 B 树扫描文件目录时会误把 catalog 当成数据文件。我一般习惯目录结构固定为minisql_data/存放所有表数据文件minisql_data/catalog.meta存放系统目录minisql_data/minisql.log存放 SQL 命令日志这个目录约定看似简单却决定源码后续扩展的方向。谁把这几条路径写散谁就会在维护时不断踩坑。5. MiniSQL踩坑排查我在这类源码里翻过的四个典型车MiniSQL 看着小实际写起来全是细节。下面这几条坑是我在实际排查过程中遇到过很多次的每条都按“现象、原因、解决”的路径给你一个可以直接照做的检查清单。5.1 char 字段落盘后乱码甚至 access violation c0000005现象往char(10)字段插入“hello world”查询出来是乱码或者程序直接崩溃调试器报 access violation c0000005。原因定长 char 字段的长度是 10但字符串本身超过 10memcpy把后面的内存一起写进了记录槽。读取时按 10 字节读因为没读到\0打印函数持续读到越界内存。解决在插入时严格校验字段长度超过定义长度直接报错并拒绝执行。读取 char 字段时先按字段长度拷贝到临时数组再手动补一个\0。我通常会在decodeRecord里加一行防御性代码temp[len] \0哪怕字段本身没存结束符也不会崩。5.2 结构体直接读写文件换个编译器数据全变现象同一份数据放在内存里正常写进文件再读出来某些字段的值变成大得离谱的数字或者整条记录错位。原因C 结构体在内存中会做对齐比如int和char之间存在 padding bytes。直接把结构体指针转成char*写文件会把这些 padding 一起写进去在不同编译选项或不同平台上padding 长度不一样读回来的结构体自然错位。解决所有落盘数据都必须逐字段序列化不要用reinterpret_cast和sizeof(Record)。如果觉得逐字段写太繁琐可以定义一个RecordCodec类把encode/decode封装成一对函数后续所有表都走同一个编解码器。5.3 加了B树索引反而更慢全表扫描和索引扫描的决策现象表里只有几百条数据建索引之后select * from t where id 100变得更慢插入速度也明显下降。原因小表上全表扫描只读几页而 B 树查询要反复比较节点、回溯父节点还要多维护一份索引文件。MiniSQL 如果没有优化器每次都硬走索引自然“捡芝麻丢西瓜”。解决在执行器里加一个简单的门槛判断例如当表记录数小于 200 时强制走全表扫描当条件命中唯一索引且是等值查询时才走索引路径。这个参数不能拍脑袋写死应该拿到实际数据后打印扫描行数再调整。第四小节会讲怎么输出执行信息正好配合。5.4 重启后打开数据库就崩索引文件与数据文件不同步现象程序上一次没正常退出或者调试时强杀进程再次启动后create table提示成功但一查询就崩索引文件打开失败。原因内存中的 B 树只负责提供查询能力关闭时才写回索引文件数据文件是每执行一条写操作就落盘。两条写入路径没有事务保护强杀进程后一边更新一边没更新索引里的记录指针指向了不存在的行。解决启动时不要直接读索引文件而是扫描 catalog 里的索引定义从数据文件重新构建 B 树。这种“重建索引”策略牺牲了一点启动时间但换来了极高的可靠性。如果源码里已经有索引文件格式可以先清洗掉旧索引文件再统一重建。这个做法也是我强烈建议你保留在源码里的“后悔药”。6. MiniSQL的进阶验证给执行器加一档EXPLAIN和行数统计MiniSQL 跑通之后很多人就停在“能交作业就行”。实际上要验证你的执行器选路是否正常最有效的方法是加一个EXPLAIN命令打印每语句扫描的行数、是否使用索引。它不需要重写执行器只需要在每个算子入口放一个计数器。void Executor::executeSelect(const SelectStmt stmt) { int scanned_rows 0; bool index_used false; // 判断是否走索引 if (stmt.has_where stmt.where_col indexed_column) { index_used true; auto result btree_-search(stmt.where_value); scanned_rows result.size(); for (auto rid : result) { Row row table_-getRecord(rid); if (matchCondition(row, stmt.condition)) { emit(row); } } } else { for (auto row : table_-allRecords()) { scanned_rows; if (matchCondition(row, stmt.condition)) { emit(row); } } } if (profile_enabled_) { std::cout rows_scanned scanned_rows , index_used (index_used ? yes : no) \n; } }这个profile_enabled_参数由explain命令控制开启后不影响正常输出只在执行结束后追加一行统计。有了它你就可以对照下面这张表验证预期行为场景期望 index_used期望 scanned_rows等值查询条件列有索引yes1 或极小范围查询条件列有索引no或未做范围优化接近表总行数无条件 selectno表总行数只有十几条数据的表no建议全表扫描十几条我自己的习惯是每加一个执行算子先不观察运行时间只看scanned_rows。如果 MiniSQL 的调试输出和预期明显不符问题大概率出在 where 条件解析或者索引定义没有真正被 executor 识别。这个习惯帮我排掉过很多次“看起来很慢”的假象。MiniSQL 的源码看起来是课程设计实际上它把数据库管理系统最核心的存储、索引、解析、执行圈了个完整的圆。我建议你不要只想着交作业而是把EXPLAIN、重建索引、定长记录编解码这三个点都保留下来它们是你在这个项目里投入时间最值得换回的东西。希望这篇笔记能帮你把这份源码拆明白也让你在自己的 C 项目里少走一次弯路希望帮到你。本文还有配套的精品资源点击获取