★ FEATURED ARTICLE 简介miniSQL 是浙江大学数据库设计课程的期末大程成果面向数据库课程学习者、课程设计参考者及希望理解关系数据库内核的 C/C 开发者。压缩包共 29 个文件、约 885KB包含 9 个 cpp 与 9 个头文件组成的源码、9 个 txt 测试/说明文件、1 份 PDF 设计报告和 1 个可直接运行的 exe便于从代码、文档到可执行程序完整对照学习。已有 1532 人学习下载。源码覆盖 SQL 语句解析执行、缓冲管理、记录管理、索引与 B 树、Catalog 等模块能观察关系数据模型、ACID 属性、查询优化等理论在系统中的落地方式配合设计报告可梳理项目目标、设计决策、实现细节、问题解决和测试结果测试文件与可执行程序则方便验证查询、更新及并发场景下的功能表现适合课程设计复盘与数据库内核入门参考。1. 从一条 create table 说起这套 miniSQL 到底能干什么第一次拿到这份 miniSQL 源码我把它当成只能跑select的课堂玩具直到把页大小从 4KB 改成 8KB再打开旧数据目录整个索引文件直接读不出来。那一刻我才认真看它这套用 C/C 写的迷你数据库体量不大但缓冲池、B 树索引、记录管理、SQL 解析几层是真按数据库的方式在分工不是把数据往文件里一扔了事。它适合两类人。一类是想把课堂上的数据库原理落成可调试代码的开发者另一类是正在做数据库课程设计、需要一份能跑通建表、增删改查、索引和执行器参考实现的同学。全篇不吹架构只讲我跑起来、改坏过、又修回来的那些地方。2. 架构拆解一条 SQL 从敲下回车到写进磁盘要过几道手这份工程的规模不大但分层意识很强。它没有把解析、执行、存储糊在一个main.cpp里而是按数据库教科书的经典四件套切开了解析层、系统管理Catalog、记录与索引管理、缓冲池与磁盘文件。理解这条链路后面无论是调 bug 还是加功能都能先定位到该动哪一层。2.1 七层职责与调用链路从控制台敲入一条语句算起完整路径大致是这样层输入输出典型文件交互层 / REPL一行文本 分号完整 SQL 语句main.cpp、shell.cpp词法分析SQL 字符串Token 流lexer.cpp语法分析Token 流AST语句对象parser.cpp、ast.h语句分发AST执行器对象executor.cpp执行器表元数据 条件逐行结果seq_scan.cpp、index_scan.cpp等记录 / 索引管理行数据、键值页内偏移、B 树位置record_manager.cpp、bplus_tree.cpp缓冲池 / 磁盘页号4KB 页内容buffer_pool.cpp、disk_manager.cpp这条链里有两个设计点值得单独拎出来说。第一执行器统一用迭代器模型。每个算子只暴露Open / Next / CloseNext返回一行返回false就说明扫完了。这样做的好处是过滤、投影、索引扫描可以像积木一样叠起来新加一个算子不用改上游代码。第二Catalog 是唯一的元数据来源。表有哪些列、每列什么类型、表的第一页是几号、这张表上挂了哪些索引全部存在 Catalog 文件里执行器不自己猜。很多同类工程把表结构硬编码在代码里改一个字段要重编译这个坑在二次开发时会很要命。2.2 目录结构与各文件职责工程目录基本能对上上面的分层常见结构如下miniSQL/ ├── CMakeLists.txt ├── src/ │ ├── main.cpp # 入口解析参数、建目录、起 REPL │ ├── common/ # 错误类型、类型定义、工具函数 │ ├── parser/ │ │ ├── lexer.cpp/.h # 词法 │ │ ├── parser.cpp/.h # 递归下降语法分析 │ │ └── ast.h # 语句对象定义 │ ├── catalog/ # 表、列、索引的元数据持久化 │ ├── record/ # 记录页格式、页内增删改查 │ ├── index/ # B 树节点、分裂合并、范围查找 │ ├── buffer/ # 页表、LRU 链表、脏页回写 │ └── executor/ # 各算子与语句分发 ├── test/ │ ├── cases/ # 按功能拆的 .sql 脚本 │ └── run_tests.sh └── data/ # 运行时生成catalog、.dat、.idxdata/是运行期目录不是源码目录第一次跑之前可以不存在程序启动时负责创建。这个细节看似小实际上很多人的第一次翻车就发生在这里目录没建、catalog 文件不存在、打开文件直接判失败然后解引用空指针。2.3 构建方式与编译产物工程一般用 CMake 管理也见过用裸 Makefile 的分支原理一样把所有src/**/*.cpp编成可执行文件链接时不需要额外依赖。常见要求是编译器支持 C17因为代码里会用到std::optional、std::variant这类东西来做类型和语句表达。# 1. 准备编译环境Debian/Ubuntu 系 sudo apt install build-essential cmake # 2. 配置 编译Debug 版方便 gdb 跟栈 cmake -S . -B build -DCMAKE_BUILD_TYPEDebug cmake --build build -j$(nproc) # 3. 运行参数是数据目录 ./build/minisql ./data三个参数值得解释一下-S .指定源码根目录-B build把中间产物丢进build/不污染源码树-DCMAKE_BUILD_TYPEDebug打开-g -O0调试时能看到真实行号。如果你的解析器是用 flex/bison 生成的CMake 配置阶段会自动调用它们机器上没装就会在 configure 阶段报flex not found装上即可不影响后续代码阅读。3. 解析与执行一条 SQL 是怎么被拆成算子的解析层是这份工程里最容易读、也最容易被低估的部分。它没用 flex/bison 的也不少手写递归下降反而更好改——加一个语句类型只要在词法里补关键字、在语法里加一个分支不用重新生成代码。3.1 手写词法把 SQL 切成 token词法器的职责非常单一从左到右扫一遍字符串吐出Token流。它要处理空白、--行注释、数字、字符串字面量、标识符和运算符。下面这段是我从工程里抽出来的核心结构// src/parser/lexer.cpp enum class Tok { END, IDENT, NUMBER, STRING, COMMA, LPAREN, RPAREN, STAR, EQ, LT, GT, LE, GE, NE, SEMI }; struct Token { Tok kind; std::string text; // 关键字也放这里parser 层再区分 }; class Lexer { public: explicit Lexer(std::string sql) : src_(std::move(sql)), pos_(0) {} Token Next() { SkipSpace(); if (pos_ src_.size()) return {Tok::END, }; char c Peek(); if (std::isalpha(c) || c _) return ScanIdentOrKeyword(); if (std::isdigit(c)) return ScanNumber(); if (c \) return ScanString(); return ScanOperatorOrPunct(); // , ( ) * ; } private: char Peek() const { return pos_ src_.size() ? src_[pos_] : \0; } char Get() { return pos_ src_.size() ? src_[pos_] : \0; } void SkipSpace() { while (pos_ src_.size()) { if (std::isspace(src_[pos_])) { pos_; continue; } // -- 行注释扫到换行结束 if (src_[pos_] - pos_ 1 src_.size() src_[pos_ 1] -) { while (pos_ src_.size() src_[pos_] ! \n) pos_; continue; } break; } } std::string src_; size_t pos_; };代码里几个参数的含义src_持有整条语句pos_是游标Peek()不移动游标专门给、、这种两字符运算符做前瞻用ScanString里要处理转义SQL 里表示一个单引号。Next()返回的text统一存原始字符关键字识别放到 parser 层做好处是词法不用背关键字表加语句类型时改一处就够。这里有个常被忽略的细节字符串字面量必须以结尾扫到\0还没闭合就该立刻抛语法错误而不是把整段内容当字符串返回。少了这个检查用户输错一个引号后面所有 token 都会乱掉报错信息会指向一个八竿子打不着的位置排起来非常痛苦。3.2 AST 与语句分发语法分析的产出是 AST。这份工程常见做法是不做泛型表达式树而是按语句类型各建一个结构体因为课程设计级别的 SQL 子集就那么多// src/parser/ast.h enum class StmtType { SELECT, INSERT, DELETE, UPDATE, CREATE_TABLE, DROP_TABLE, CREATE_INDEX, DROP_INDEX, EXIT }; struct Condition { std::string column; Tok op; // EQ / LT / GT / LE / GE / NE Value rhs; // 统一成一个 variantint / std::string }; struct Statement { explicit Statement(StmtType t) : type(t) {} virtual ~Statement() default; StmtType type; }; struct SelectStmt : Statement { SelectStmt() : Statement(StmtType::SELECT) {} std::string table; std::vectorstd::string columns; // 空表示 select * std::vectorCondition where; // 多个条件之间按 AND 处理 };Condition里只放单列条件是这套实现的一个明确取舍它不支持多表连接也不支持or。这不是缺陷是课程设计里够用就好的典型边界。真要在上面加 join得先把Condition扩成带表名的形式这是一个值得在改造前想清楚的扩展点。分发逻辑放在执行器工厂里根据 AST 构造对应的执行器对象// src/executor/executor.cpp std::unique_ptrExecutor BuildExecutor(const Statement stmt, Catalog catalog, BufferPool bpm) { switch (stmt.type) { case StmtType::SELECT: { const auto s static_castconst SelectStmt(stmt); TableMeta* table catalog.GetTable(s.table); if (!table) throw SqlError(table not found: s.table); // 条件是等值、且该列上有索引 - 走索引扫描否则退化成顺序扫描 IndexMeta* idx table-FindEqualityIndex(s.where); std::unique_ptrExecutor child; if (idx) { child std::make_uniqueIndexScan(*table, *idx, s.where, bpm); } else { child std::make_uniqueSeqScan(*table, bpm); } return std::make_uniqueFilter(std::move(child), s.where); } // INSERT / DELETE / UPDATE / CREATE TABLE ... 各自一个分支 default: throw SqlError(unsupported statement); } }参数说明catalog提供表与索引元数据bpm是全局缓冲池引用所有算子共享同一个实例绝不能各建各的。FindEqualityIndex返回空指针就说明这次查询没有可用索引代码会自动降级为全表扫描——这个降级策略很关键它保证了即使索引构建失败查询也能出结果只是慢一点。3.3 迭代器模型Open/Next/Close 为什么好用所有算子继承同一个基类// src/executor/executor.h class Executor { public: virtual ~Executor() default; virtual void Open() 0; // 申请资源、定位到第一行 virtual bool Next(Row out) 0; // 取下一行false 表示结束 virtual void Close() 0; // 释放资源 virtual const Schema GetOutputSchema() const 0; };Filter的实现就是个循环Next里不断调子算子的Next直到条件满足或子算子返回false。这种火山模型写法在工程里非常友好——想加Limit就套一层想在哪个算子前后打日志就包一层不用改动既有代码。我调试索引为什么没生效时就是在BuildExecutor里临时打印走了哪个分支一眼就能看出是IndexScan还是SeqScan。4. 存储与索引4KB 页里塞下记录和 B 树存储层是这份工程最值得细看的部分。上面解析层再花哨最后都要落到这一行往哪个页的第几个槽写。它用 4KB 定长页组织数据页内用槽目录管理变长记录索引用 B 树实现缓冲池做 LRU 与脏页回写。4.1 记录页布局槽目录如何容纳变长记录页头的结构大致如下// src/record/page.h constexpr size_t PAGE_SIZE 4096; struct PageHeader { uint16_t slot_count; // 已分配的槽位数量 uint16_t free_start; // 空闲区起点紧跟在槽目录之后 uint16_t free_end; // 空闲区终点记录区从页尾往前长 page_id_t next_page; // 同表下一页-1 表示没有下一页 };设计上把页分成三段页头在开头槽目录从前往后长记录数据从后往前长中间那段是可用空间。每条记录在槽目录里对应一个offset length记录本身可以是不定长的char(n)。插入一条记录的代码如下// 返回槽位下标页满返回 -1由上层决定是换下一页还是报错 int16_t Page::InsertRecord(const char* data, uint16_t len) { PageHeader* h header(); const size_t slot_bytes sizeof(Slot); // offset length通常 4 字节 if (h-free_end - h-free_start len slot_bytes) return -1; h-free_end - len; // 数据从页尾往前长 std::memcpy(PageData() h-free_end, data, len); Slot s{h-free_end, len}; WriteSlot(h-slot_count, s); // 槽目录从页头往后长 h-slot_count; h-free_start slot_bytes; return static_castint16_t(h-slot_count - 1); }三个关键值free_start与free_end之差就是剩余空间len slot_bytes是要申请的净空间slot_count同时当作槽目录的下一个写入位置。删除记录时不要真的搬数据只需要把对应槽标记为已删除例如length 0等页内碎片多到一定程度再做整理——这是几乎所有页式存储的通用做法搬数据不仅慢还会把所有上层引用弄乱。4.2 B 树查找、分裂与叶子链表索引层用的是标准 B 树内部节点只存键和孩子页号叶子节点存键与记录定位信息页号 槽位所有叶子用next_leaf串成链表支持范围查询。查找入口先一路下探到叶子// src/index/bplus_tree.cpp // 找到 key 应落入的叶子页与槽位 bool BPlusTree::FindLeaf(const Key key, page_id_t leaf_id, int slot) { page_id_t cur root_id_; while (true) { auto guard bpm_.FetchPage(cur); // 自动 pin出作用域 unpin BPlusNode node(guard.Data()); if (node.IsLeaf()) { leaf_id cur; slot node.LowerBound(key); // 第一个 key 的位置 return true; } int i node.UpperBound(key) - 1; // 最后一个 key 的孩子下标 if (i 0) i 0; // 最小键边界 cur node.ChildAt(i); } }LowerBound与UpperBound的区别是二分查找里经典的开闭区间问题写反了不会崩但会漏掉边界键重复的行表现出来就是偶尔少一行非常玄学。叶子节点满了就分裂成两个、把中间键上推到父节点父节点也满了继续向上分裂直到根根分裂时新建一层。删除同理有合并逻辑但很多课程实现为了简化不实现合并只做标记删除这个取舍要在文档里写清楚否则长期跑下来索引文件会只涨不缩。4.3 缓冲池LRU、pin 计数和脏页回写缓冲池是磁盘页在内存中的缓存池页表负责page_id - frame的映射LRU 链表负责淘汰pin 计数负责保护正在被使用的页。核心取页逻辑// src/buffer/buffer_pool.cpp Page* BufferPool::FetchPage(page_id_t pid) { std::lock_guardstd::mutex lock(latch_); auto it page_table_.find(pid); if (it ! page_table_.end()) { // 命中 Frame* f frames_[it-second]; f-pin_count; Touch(f); // 挪到 LRU 链表头部 return f-page; } Frame* f FindVictim(); // 从链表尾部找 pin_count 0 的 if (!f) throw BufferPoolFull(all frames pinned); if (f-dirty) FlushFrame(f); // 脏页先写回磁盘 page_table_.erase(f-pid); disk_.ReadPage(pid, f-page); // 整页读入 f-pid pid; f-dirty false; f-pin_count 1; page_table_[pid] static_castframe_id_t(f - frames_); Touch(f); return f-page; }需要配套实现的是UnpinPage(pid, is_dirty)pin_count--如果传进来的is_dirty为真就把该 frame 标脏。这里有个血泪经验——忘记 unpin 的程序不会立刻报错它会先把所有 frame 的 pin 计数占满然后在几百条插入之后突然抛BufferPoolFull此时错误现场离真正的原因已经很远了。调试这类问题我一般在FindVictim返回空之前把每个 frame 的pid和pin_count打出来谁没释放一目了然。5. 跑起来与排查从 make 到第一条 select 的通关记录代码读得再顺不跑一遍心里没底。这一章按装依赖—编译—冒烟—出问题怎么查的顺序走一遍把我在几个不同分支上踩过的坑集中写出来。5.1 依赖清单与首次构建最小依赖只有三样C17 编译器、CMake、一个能跑 shell 的终端。如果解析器是生成式实现再加上 flex 和 bison交互层如果用了 readline 做行编辑就再装libreadline-dev没装的话工程通常会退化成std::getline功能不受影响。# 最小集 sudo apt install build-essential cmake # 可选生成式解析器 / 行编辑 sudo apt install flex bison libreadline-dev # 配置与编译打开警告更容易发现类型问题 cmake -S . -B build -DCMAKE_BUILD_TYPEDebug -DCMAKE_CXX_FLAGS-Wall -Wextra cmake --build build -j$(nproc)-Wall -Wextra建议一直开着。这个工程里大量的页内偏移是uint16_t和size_t混算时一旦漏掉强制转换编译器给的警告往往就是后面某个内存越界的先兆。5.2 交互式 shell 与回归脚本启动后进入 REPL语句以分号结尾下面这段可以直接贴进去跑一遍冒烟create table student (id int, name char(16), score int); create index idx_student_id on student (id); insert into student values (1, alice, 90); insert into student values (2, bob, 85); insert into student values (3, carol, 78); select * from student where id 2; -- 应该走索引返回 1 行 select * from student where score 80; -- 无索引走全表扫返回 2 行 delete from student where id 1; select * from student; -- 应该只剩 2 行 quit;如果工程支持exec 文件名;这样的指令就把上面的内容存成test/cases/basic.sql用脚本把test/cases/下所有文件跑一遍再拿结果和手写的期望输出做diff。这套回归很土但在改缓冲池和 B 树的时候救过我很多次——那两个模块的 bug 最擅长只在小数据量下正确。5.3 五个把我卡住的现场现象一启动直接段错误gdb 显示崩在 catalog 加载处。原因是数据目录第一次不存在打开 catalog 文件失败后代码没有走新建分支直接对空指针解引用。解决办法是在启动流程里先判断目录是否存在不存在就mkdir再判断 catalog 文件是否存在不存在就走初始化流程建一个空 catalog 并写回磁盘。现象二插入的数据在本次会话能查到重启后全没了。根因是脏页只在缓冲池析构函数里统一回写而有的人在 REPL 里用exit()直接退出进程析构根本没执行。解决方式有两种把退出路径统一改成从main正常return或者在 REPL 的quit分支里显式调一次FlushAllPages()。后者更稳推荐两个都做。现象三明明建了索引explain一类的调试输出却显示走了全表扫描。常见原因是条件里的字面量类型和索引列类型对不上比如id是int用户写了where id 2比较函数直接返回不匹配索引匹配逻辑就放弃了。解决办法是在解析阶段做一次类型归一化把字符串字面量按目标列类型转换转换失败直接报语法错误而不是悄悄降级。现象四改了页大小之后旧数据目录读出来全是脏数据。文件里没有版本标识程序按新页大小去解读旧文件边界全错。解决办法是在每个数据文件开头加一个固定长度的头写明 magic number、页大小和格式版本加载时先校验不匹配就明确报错而不是硬读。这个头只占十几个字节却能把数据损坏变成版本不兼容这种可诊断的问题。现象五char(n)字段上建索引后等值查询时有时查到有时查不到。定长字符串在存储时会用空格补齐到 n而查询条件里的字符串没有补齐两边做比较时长度不同B 树的键序就乱了。解决办法是在写入索引键和查询键之前统一做一次右补空格到定长的归一化比较函数里也按定长比较不要用strcmp那种遇到\0就停的写法。6. 二次开发从加一个 explain 开始练手改造这份工程我建议从最小的功能切入别一上来就动存储格式。最合适的第一个练手目标是给执行器加一个explain语句它不改变任何数据只是把BuildExecutor构造出来的算子树按层打印出来让你直观看到一条 SQL 到底走了索引还是全表扫。6.1 加一个 explain 算子实现上只需要在 AST 里加一个ExplainStmt语法规则里识别explain关键字分发时把内层语句构造成执行器树后遍历打印// src/executor/explain.cpp void ExplainExecutor::Dump(const Executor root, int depth) { std::string indent(depth * 2, ); std::cout indent root.Name(); // SeqScan(student) / IndexScan(...) if (auto* child root.Child()) Dump(*child, depth 1); }Name()由每个算子自己返回带上表名和关键参数比如IndexScan(student.idx_student_id, id 2)。这一步改完后面所有性能相关的调试都会轻松很多。6.2 把单表查询扩成双表 join 的最小改法如果要往前走一步最小可行的 join 是嵌套循环外层SeqScan扫左表内层对每一行右表做一次带等值条件的查找右表连接列上有索引就直接复用IndexScan。改动集中在三处Condition加上表名前缀、AST 里允许from跟两张表、BuildExecutor里多一个NestedLoopJoin分支。这个改法的验证标准很明确验证项方法通过标准正确性同一组数据分别在改造版和成熟数据库里跑同样的 join行数与内容完全一致索引复用给右表连接列建索引看explain输出内层是IndexScan而非SeqScan空表与空值左表或右表为空、连接列为 NULL不崩结果为 0 行大数据量两表各插一万行不抛BufferPoolFull耗时在可接受范围6.3 验证改造是否正确的三步第一步永远是跑老回归。改造前先把test/cases/全跑一遍存档改完再跑一遍做 diff任何一行差异都要能解释清楚。第二步是边界构造空表、单行、重复键、最大长度字符串这四类输入能覆盖掉大部分页内偏移和二分查找的边界 bug。第三步才是性能观察用小数据量对比explain输出的算子形态确认索引真的被用上了而不是看起来快了。我现在改任何存储相关代码之前都会先写一个能跑通的最小 SQL 脚本存进test/cases/改完立刻跑。这份习惯是从上面那次改页大小把旧数据读坏之后养成的——格式可以改但没有版本头和回归脚本的格式改动迟早会在某个深夜让你怀疑人生。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
