从零实现miniSQL：C++数据库存储引擎与B+树索引全链路拆解

简介这份 miniSQL 工程是浙江大学数据库设计课程期末大程的完整成果面向希望从代码层面理解关系数据库原理的高校学生与 C/C 开发者。它围绕 SQL 解析与执行、缓冲区管理、记录管理、B 树索引、查询解释等核心模块展开适合课程设计参考、数据库内核入门和项目复盘。压缩包共 29 个文件约 885KB包含 9 个 cpp 与 9 个 h 源文件、9 个 txt 测试或说明文本、1 份 pdf 设计报告和 1 个 exe 可执行程序源码、文档与可运行版本相对齐全。现有 1532 人学习或下载说明其在数据库课程设计场景中有一定参考价值。读者可借助设计报告梳理需求、模块划分与实现取舍结合源码观察 SQL 语句如何被解析并映射到存储与索引层也可直接运行程序验证建表、增删改查等基本操作并通过测试文件理解功能完整性与并发场景下的验证思路。1. miniSQL一份能跑起来的数据库课程设计从建表到索引全链路很多人对数据库课程设计的印象还停留在画 ER 图加几句 SQL 查询但这份 miniSQL 不太一样——它真的用 C/C 从零搭了一个能接收 SQL 语句、能建表、能插数据、能走索引查询的小型关系数据库引擎。你敲进去一条create table它要自己解析语法、分配页、写元数据你敲select ... where id 3它得判断走全表扫描还是走 B 树索引。整个链路里词法语法分析、系统管理、记录管理、索引、缓冲池一个都不少。适合两类人正在做数据库大作业、想看看别人家完整版长什么样的同学以及想通过一个规模可控的项目理解存储引擎内部结构的开发者。接下来我就按自己拆这份源码的顺序把它从架构到关键代码、再到怎么改一段段讲清楚。2. 整体架构与工程结构六个模块如何拼成一个数据库拿到源码第一步不是急着编译而是先看清楚它被切成了哪几块。这类课程设计项目典型的组织方式是按职责分层每个模块一个目录对外暴露一个 Manager 类互相之间通过 catalog 里的元数据通信。看懂这张模块图后面读任何一段代码都不会迷路。2.1 模块划分从 API 层到磁盘页的一条竖线miniSQL 的主体一般被分成六层自顶向下是解释器Interpreter负责词法/语法分析并调用下层、API 层把一条 SQL 翻译成对 Catalog、Record、Index 的组合调用、Catalog 管理器存表结构、索引定义等元数据、记录管理器Record Manager负责表数据的增删改查、索引管理器Index ManagerB 树实现、缓冲池管理器Buffer Manager页的换入换出以及磁盘管理器Disk Manager直接读写文件页。加上一个记录列值定义的辅助层就是常见的七个部分。这种分层的好处是每层只依赖下一层的接口。比如 Record Manager 想读某个页不需要知道这个页在文件第几个偏移直接调 Buffer Manager 的getPage就行Buffer Manager 换页时也不关心页里装的是表记录还是索引节点一律按 4KB 字节块处理。你在二次开发时如果只想加个新字段类型基本只需要动 Catalog 和 Record 两层索引层可以完全不碰。提示不同版本 miniSQL 的目录命名不完全一致有的叫src/interpreter有的叫src/parser但职责划分大同小异按解释器 / API / Catalog / Record / Index / Buffer / Disk这条线去对号入座即可。2.2 目录结构与构建方式一个典型的工程布局长这样以 CMake 构建为例miniSQL/ ├── CMakeLists.txt ├── src/ │ ├── main.cpp # 入口起一个 REPL 循环 │ ├── interpreter/ # 词法、语法分析 语句分发 │ ├── api/ # 把 AST 翻译成下层调用 │ ├── catalog/ # 表、索引的元数据管理 │ ├── record/ # 记录管理行级增删改查 │ ├── index/ # B 树索引 │ ├── buffer/ # 缓冲池LRU 替换 │ ├── disk/ # 文件页读写 │ └── common/ # 类型定义、错误码、常量 └── test/ # 若干 .sql 测试脚本构建通常只要三步mkdir build cd build cmake .. make -j4 ./minisql # 或 ./miniSQL看可执行文件名启动后一般会进入一个交互式命令行提示符类似miniSQL直接敲 SQL 加;回车即可。也支持把测试脚本重定向进去./minisql test/basic.sql批量跑用例。这里有个容易被忽略的点——数据库文件.db或.data默认落在当前工作目录如果你在不同目录下反复启动会看到表不存在的假象其实是读到了另一个空库。我一般会先ls一下确认有没有残留的数据文件或者干脆在干净目录里跑。注意编译前确认 g 版本不要太老B 树里用到的std::shared_ptr、std::optional如果实现用了对 C17 有要求CMakeLists 里的set(CMAKE_CXX_STANDARD 17)别删掉。2.3 一条 SQL 在模块间的流动理解架构最直观的方式是跟一条语句走完全程。以select * from student where id 1;为例Interpreter先做词法分析把字符串切成 token 序列[select, *, from, student, where, id, , 1, ;]再按语法规则组装成一棵简单的抽象语法树AST节点类型是SelectStatement里面带着表名、条件列表。API 层收到这个 AST先去Catalog查student的表定义有哪些列、每列什么类型、主键是谁、id 上有没有建索引。如果 id 上有索引API 就调Index Manager的search传入 key1拿回记录所在的 RID页号 槽位号如果没有索引就走Record Manager的全表扫描scan逐行比对条件。拿到 RID 后Record Manager调Buffer Manager的getPage(pageId)缓冲池命中就直接返回内存页不命中就从Disk Manager读盘并可能触发 LRU 淘汰。最后把行数据按列类型反序列化格式化输出到终端。这条链路里每一层的输入输出都很干净解释器只产出 ASTAPI 只产出要做什么操作的指令序列底层只管字节。你调试时如果发现查询结果不对可以从输出倒推——是解析错了打 AST、是元数据查错了打 Catalog、还是页读错了打 pageId 和页内容一层层缩小范围比盲目加 printf 高效得多。3. 解释器与执行链路SQL 是怎么被拆成动作的中间层最值得看的是解释器因为它决定了整个项目支持哪些 SQL、不支持哪些 SQL。课程设计的解释器通常不做成完整的编译器前端而是手写一个递归下降解析器够用即可。这里展开讲词法切分、语法树构造以及 API 层怎么把它翻译成具体调用。3.1 词法与语法一个手写递归下降的骨架词法分析一般用一个Tokenizer类逐字符扫描跳过空白遇到字母数字就吃到下一个分隔符识别关键字、标识符、数字、字符串字面量、运算符。语法分析则是一组互相调用的函数每个非终结符对应一个函数。下面是这类实现里最常见的骨架// interpreter/interpreter.cpp示意 std::shared_ptrStatement Interpreter::parseStatement() { Token tok lexer_.peek(); switch (tok.type) { case TokenType::CREATE: return parseCreate(); // create table / index case TokenType::DROP: return parseDrop(); // drop table / index case TokenType::INSERT: return parseInsert(); case TokenType::SELECT: return parseSelect(); case TokenType::DELETE: return parseDelete(); case TokenType::UPDATE: return parseUpdate(); default: throw SyntaxError(unexpected token: tok.text); } } // 解析 select 语句select col_list from table [where cond] [;] std::shared_ptrSelectStatement Interpreter::parseSelect() { lexer_.expect(TokenType::SELECT); auto stmt std::make_sharedSelectStatement(); stmt-columns parseColumnList(); // 支持 * 或逗号分隔列名 lexer_.expect(TokenType::FROM); stmt-tableName lexer_.expectIdent(); // 表名 if (lexer_.match(TokenType::WHERE)) { stmt-condition parseCondition(); // 递归处理 and 连接的比较表达式 } lexer_.expect(TokenType::SEMICOLON); return stmt; }这段代码的关键在于每个parseXxx函数只做一件事——消费掉属于自己语法的 token产出一个 AST 节点。expect在类型不匹配时直接抛语法错误match则是有就消费、没有也不报错适合处理可选子句where、order by之类。条件解析parseCondition一般是递归的遇到and就左右各解析一个比较表达式再拼成一个AndCondition比较表达式里再区分列名和常量常量按列类型转成对应的 int/float/string。这里有个参数细节值得说parseColumnList要能处理*也要能处理id, name, score这种多列。实现上通常返回std::vectorstd::string*用一个特殊标记比如空 vector表示交给 API 层去 Catalog 里展开成全部列名。如果你后面想加count(*)这种聚合就得在这一层识别函数调用 token改动量不小建议先把基础查询跑通再说。3.2 API 层把 AST 翻译成 Record/Index 调用AST 只是描述用户想干什么真正落地要靠 API 层。以insert为例API 要做三件事查 Catalog 拿到表结构、按列类型把值序列化进一条记录、写入 Record Manager 并同步更新所有索引。代码大致如下// api/api.cpp示意 bool API::insertRecord(const std::string tableName, const std::vectorValue values) { // 1. 取表元数据校验列数、类型 auto table catalog_-getTable(tableName); if (table nullptr) throw TableNotFound(tableName); if (values.size() ! table-columns.size()) throw TypeError(column count mismatch); // 2. 组装一条记录按列顺序拼接定长/变长字段 Record record table-makeRecord(values); // 3. 先查主键/唯一索引是否冲突再真正插入 for (auto idx : table-indexes) { if (idx-isUnique()) { auto key record.getField(idx-columnOffset()); if (indexManager_-search(idx-name(), key).has_value()) throw DuplicateKey(idx-name()); } } // 4. 写入记录管理返回新记录的 RID RID rid recordManager_-insert(tableName, record); // 5. 为每个索引插入 key, rid 映射 for (auto idx : table-indexes) { auto key record.getField(idx-columnOffset()); indexManager_-insert(idx-name(), key, rid); } return true; }逐段解释一下。第 1 步的getTable返回的是从 Catalog 里读出来的表定义对象里面包含列类型、列长度、主键信息以及该表上建了哪些索引——这是后面所有判断的依据。第 2 步makeRecord是 Record 层的职责它把用户给的Value数组按列的字节布局拼成一条连续的字节序列变长字符串varchar要么单独存偏移要么直接内联并记录长度取决于实现。第 3 步的唯一性检查必须放在真正插入之前否则你先写进 Record 再发现索引冲突就得回滚而这个项目通常没有事务和 undo log回滚逻辑得自己补很容易出 bug。第 5 步的索引同步是关键记录写入后拿到 RID再把每个索引项的 key 和 RID 插进对应的 B 树。这里RID一般是{pageId, slotId}的结构体B 树的叶子节点存的就是这个。对应的select执行逻辑则是反过来先看 where 条件能不能命中某个索引等值条件 有索引 可走索引能就走索引拿到候选 RID 集合不能就走全表扫描最后对每条候选记录做剩余条件过滤。这段能不能走索引的判断是整个查询性能的分水岭也是课程设计里最容易被老师追问的地方// 简化的索引选择逻辑 std::vectorRID API::selectRecords(const std::string tableName, const Condition cond) { auto table catalog_-getTable(tableName); // 仅处理单列等值条件col const if (cond.type CondType::EQ) { auto idx table-findIndexOn(cond.columnName); if (idx ! nullptr) { return indexManager_-search(idx-name(), cond.value); // 走索引 } } return recordManager_-fullScan(tableName, cond); // 退化全表扫 }这段代码看着简单但它把索引可用性判断压缩在一个函数里非常好改。你想支持范围查询、走索引只需要在这里加一个分支调 B 树的rangeSearch(low, high)其余部分不用动。这种把策略决策集中在一处的写法是我看这份代码时最欣赏的地方——后面第 5 章讲的很多坑其实都源于这部分没想清楚。3.3 执行结果如何格式化输出查询结果最终要打印成一张表给人看。这一步通常在 API 层或一个独立的ResultFormatter里做先把所有列名按宽度对齐打印表头再逐行打印每条记录的每个字段字段值根据类型转成字符串——int 直接std::to_stringfloat 要固定精度比如两位小数varchar 直接原样输出。看似不起眼但这里有两个细节容易翻车一是列宽取值要么按列名长度和所有值长度的最大值动态计算要么给个固定宽度截断二是空值null的显示课程设计不一定支持 null但如果你加了格式化时必须单独判断否则把空指针塞进std::string会直接崩溃。4. 存储与索引核心缓冲池和 B 树是怎么落地的项目能不能用取决于解释器快不快、稳不稳则取决于存储层。这部分代码量最大也是最值得拆的。我按数据写入磁盘的方向讲先看记录怎么组织成页再看缓冲池怎么管页最后看 B 树索引怎么跟记录对上。4.1 页与记录管理定长页里的行布局磁盘和内存之间交换的基本单位是页miniSQL 一般固定 4KB4096 字节。一张表的所有记录按插入顺序切成若干页每页里再切成槽slot一个槽存一行。为了让删除的行能被复用页头通常维护一个位图bitmap记录哪些槽是空的。页结构大致是---------------------------------------------------------------- | pageHeader | slot 0 | slot 1 | ... | | (bitmap/计数) | (record bytes) | (record bytes) | | ----------------------------------------------------------------对应的插入代码核心逻辑是找一个空槽写进去返回 RID// record/record_manager.cpp示意 RID RecordManager::insert(const std::string tableName, const Record rec) { auto file catalog_-getTableFile(tableName); // 从最后一页开始找命中空槽就复用 for (PageId pid file-lastPage(); pid 0; --pid) { Page* page bufferManager_-getPage(file-id(), pid); int slot page-findFreeSlot(); // 位图里第一个 0 if (slot 0) { page-writeSlot(slot, rec.bytes()); // 拷贝字节到槽位 page-markUsed(slot); // 位图置 1 bufferManager_-markDirty(page); // 标记脏页等待落盘 return RID{pid, slot}; } } // 没找到空槽向文件尾部追加一页 Page* page bufferManager_-newPage(file-id()); page-init(); // 清空页头 page-writeSlot(0, rec.bytes()); page-markUsed(0); bufferManager_-markDirty(page); return RID{file-lastPage(), 0}; }这里几个参数和动作要分清getPage返回的是缓冲池里的内存页指针不是磁盘数据markDirty只是打个标记真正写盘发生在页被淘汰或显式 flush 时RID{pid, slot}是记录在整张表里的物理地址索引里存的就是它。删除时则是把对应槽的位图位清 0并让记录层的有效计数减一不需要真的清零字节——下次插入直接覆盖即可。这种标记删除 槽复用的做法在小规模数据下完全够用但要注意如果删除的行曾被索引引用索引项也必须一并删掉否则查询会通过索引拿到一个已经失效的 RID读出来是脏数据。这个坑我在第 5 章会专门展开。4.2 缓冲池LRU 替换与脏页写回缓冲池是内存里的一块页数组加一张页表pageId - frameIndex的映射。每次getPage先查页表命中就直接返回并更新访问时间不命中就找一个空闲 frame没有空闲就按 LRU 淘汰一个淘汰前如果是脏页要先写回磁盘。核心代码// buffer/buffer_manager.cpp示意 Page* BufferManager::getPage(FileId fileId, PageId pageId) { Key key{fileId, pageId}; auto it pageTable_.find(key); if (it ! pageTable_.end()) { touch(it-second); // 更新 LRU 链表位置 return frames_[it-second]; } // 未命中找可用 frame int frame findFreeFrame(); // 无空闲则按 LRU 淘汰 if (frame 0) frame evictLRU(); // 淘汰时若脏则写回磁盘 frames_[frame] diskManager_-readPage(fileId, pageId); frames_[frame].dirty false; pageTable_[key] frame; touch(frame); return frames_[frame]; }参数上要关注两点一是findFreeFrame优先返回从未用过的 frame避免一上来就淘汰二是evictLRU选中的 frame 如果是脏页必须先writePage再复用否则数据就丢了。LRU 链表一般用std::list加迭代器实现touch把访问的 frame 移到链表头evictLRU取链表尾。还有一种更简单的实现用时间戳计数器每次访问更新lastAccess淘汰时扫描找最小值代码更短但 O(n)小项目可以接受。注意缓冲池容量在代码里通常是个固定常量比如 64 个 frame。如果你测试时插了几万行发现某些查询越来越慢未必是索引没建对可能是缓冲池太小导致频繁换页。先把这个常量调大试试再怀疑索引。4.3 B 树索引key 到 RID 的映射索引管理器的目标只有一个给定一个 key快速找到对应的 RID 列表唯一索引就一个 RID非唯一索引可能有多个。B 树分内部节点和叶子节点内部节点只存 key 和子节点指针叶子节点存 key 加 RID 列表并且叶子之间用链表串起来方便范围扫描。节点一般也按页大小分配一个节点一页这样节点的读写能直接复用缓冲池。插入的核心是找到叶子、插入、必要时分裂并向上传播// index/bplus_tree.cpp示意仅展示插入主干 void BPlusTree::insert(Key key, RID rid) { Node* leaf findLeaf(key); // 从根向下按 key 比较 leaf-insertEntry(key, rid); // 叶子内有序插入 if (leaf-size() maxLeafSize_) { // 未溢出 writeNode(leaf); return; } // 叶子分裂把后半部分挪到新节点把中间 key 提到父节点 Node* newLeaf splitLeaf(leaf); Key upKey newLeaf-firstKey(); insertIntoParent(leaf, upKey, newLeaf); // 递归向上根满则新建根 }这段代码里有三个关键函数要理解。findLeaf从根节点开始每个内部节点用二分查找定位到应该走的子指针一直走到叶子splitLeaf把溢出的叶子一分为二左半留原节点、右半进新节点同时维护叶子链表的前后指针insertIntoParent把新节点的最小 key 和指针插进父节点父节点如果再溢出就继续往上裂直到根——根也溢出时创建一个新根树高加一。删除则是插入的逆过程删掉条目、节点太空就合并兄弟、合并导致父节点 key 变化要向上更新这块比插入复杂也是课程设计里最容易写错的模块。索引 key 和记录字段怎么对应也有个约定建索引时 Catalog 里记下这个索引建在哪一列、列在记录里的字节偏移是多少插入或查询时先按偏移从记录里取出字段值再按列类型转成统一的Key结构通常是 int/float/string 的联合配一个比较函数。比较函数的正确性直接决定搜索能不能命中——字符串比较如果用了strcmp而 key 里存的是std::string长度处理不当就会读越界。这种细节在单测里不一定暴露但一旦上了稍微复杂的数据就翻车。5. 避坑与排查那些跑一次才会暴露的问题代码逻辑通顺不代表能跑通。以下几条是我自己复现这类项目时真实踩过的坑按现象 → 原因 → 解决写遇到类似症状可以直接对照。5.1 现象建了索引查询却还是慢得像全表扫原因API 层的索引选择逻辑只识别col const这种单列等值条件而你的测试 SQL 写的是id 1 and name x条件被解析成AndCondition没命中单列等值分支直接退化成全表扫描。或者你建索引的列名大小写和查询里不一致findIndexOn没匹配上。解决先在selectRecords里加日志打印解析出来的条件类型和命中的索引名确认到底走了哪条路。如果是复合条件短期可以把最左那个等值条件提出来单独做索引选择其余条件留作过滤如果只是大小写建索引和查询时统一转小写或都保持原样别在比较处偷懒用硬碰。5.2 现象删了数据再插同主键报唯一键冲突原因删除记录时清了记录页的槽位但忘了删索引项B 树里还留着老 RID。下次插入同 key唯一性检查一查索引发现已存在直接抛冲突。更隐蔽的情况是删了记录但没删索引查询走索引拿到失效 RID读出来是已被覆盖的脏数据。解决把删记录和删索引绑成一个不可分割的动作在 Record Manager 的删除接口里先拿到待删记录的完整内容或至少拿到所有索引列的值再依次调indexManager_-remove最后才标记槽位空。顺序别反先删索引后删记录中途崩溃最多留下孤儿索引项比留下指向脏数据的索引安全。5.3 现象程序跑一半崩溃报段错误堆栈指向 B 树原因节点分裂或合并后父节点里指向子节点的指针没更新或者叶子链表的前后指针在分裂时漏改了一边遍历时顺着野指针访问了已释放的内存。还有一种常见情况是缓冲池淘汰了正在使用的页页指针悬空。解决这类问题光看代码很难定位得加断言。在每次节点指针变动后断言parent-child[i]确实指向新节点、叶子链表next-prev 当前在getPage返回后确认 frame 没有被误标记为可淘汰。跑小数据量单测时开启-fsanitizeaddress越界和悬空指针会直接报行号比断点调试快得多。5.4 现象数据文件越跑越大删了数据空间不回收原因记录层的槽位是复用的但页本身不会因为变空而归还给文件系统如果实现里插入时只往文件尾部追加新页、从不回头找空页删除再多也没用。缓冲池的脏页如果没有及时 flush进程被杀时数据还可能丢。解决插入逻辑改成先扫已有页找空槽找不到再追加新页第 4.1 节的代码就是这么做的在程序正常退出前显式调用一次bufferManager_-flushAll()把脏页全部落盘。这不是性能问题而是正确性问题别省这一步。5.5 现象换台机器编译报错说某个 C 特性不认识原因本地用的是较新的编译器默认标准而 CMakeLists 里没显式指定 C 标准换到旧环境就退回 C11std::optional、结构化绑定之类的语法全报错。解决在 CMakeLists 里固定set(CMAKE_CXX_STANDARD 17)并加set(CMAKE_CXX_STANDARD_REQUIRED ON)同时在 README 里写明最低编译器版本。如果确实要兼容旧环境就把 optional 换成std::pairbool, T这类手写替代别指望编译器默认值。6. 二次开发从加一个字段类型到补一条索引失效路径把项目跑通只是开始真正有价值的是知道往哪儿改。以我改这类代码的习惯二次开发一般从小步可验证入手别一上来就动执行引擎。第一个改造点是加字段类型比如给表加一个date列。改动链条其实很固定先在common/types.h里补一个Type::DATE枚举和它的字节长度比如按 int 存天数再到 Catalog 的建表解析里允许date关键字然后 Record 层的序列化/反序列化加一个分支最后解释器的字面量解析要能把2024-01-01转成内部表示。四步改完用一条create table t(d date); insert into t values(2024-01-01); select * from t;端到端验证能跑通就说明链路齐了。建议每加一种类型都补一个这样的最小 SQL 用例放进test/比事后回忆哪里改过强。第二个改造点是补索引失效路径。前面说过复合条件a 1 and b 2目前不走索引。一个务实的改法是在 API 层把AndCondition拆成若干单列条件挑一个有索引且等值的作为驱动条件走索引其余条件作为过滤器在结果集上再筛一遍。伪代码只需几十行// 从复合条件中挑一个可走索引的单列等值条件 std::optionalCondition pickIndexable(const std::vectorCondition conds, const TableDef* table) { for (auto c : conds) { if (c.type CondType::EQ table-findIndexOn(c.columnName)) return c; // 找到第一个能走索引的就返回 } return std::nullopt; // 没有则退化全表扫 }验证方法要成体系不能只靠手敲。我的习惯是准备三组用例一组基础 DML建表、增删改查各来几条、一组边界空表查询、主键重复插入、删除不存在的主键、一组索引对比同一条查询分别在有索引和删掉索引两种情况下跑结果必须一致只允许耗时有差别。第三组最容易被忽略却是最有用的——它同时验证了索引的正确性和性能收益一旦索引搜索漏了行或多返回了行对比结果立刻暴露。最后一个技巧是给关键路径加可开关的日志。用一个环境变量控制比如MINISQL_DEBUG1时打印解析出的 AST、命中的索引名、每次getPage的 pageId 和是否命中缓冲池。这些日志在生产里关掉排障时打开比反复改代码加 printf 干净得多也能让你在给同学演示时一眼看出查询到底走了哪条路。这份代码我前后完整复现过几遍中间最惨的一次是索引删除没同步导致同一个主键删了再插一路冲突查了整整一下午才发现是记录删了索引没删。从那以后我每次改存储层都强制先跑一遍删除后重插同主键和索引开关结果对比这两条用例再往下写后悔药不如事前多敲一行断言。希望这份拆解能帮你少走点弯路把这份 miniSQL 真正跑成自己能改的东西。本文还有配套的精品资源点击获取