简介：这份资源是浙江大学数据库设计课程的期末大程成果——miniSQL迷你数据库系统，面向正在学习数据库原理、希望动手理解SQL底层实现的高校学生与开发者。压缩包共29个文件，约885KB，以C/C++源码为主体，包含9个cpp与9个h文件，覆盖缓冲管理、记录管理、索引管理、B+树、目录与解释器等核心模块，另附可执行文件、测试文件及一份PDF设计报告，可直接运行或编译研究。已有1532人学习下载，说明其在数据库课程学习者中具有一定参考价值。读者可从中获得一套较完整的数据库引擎实现范例：通过阅读源码理解SELECT、INSERT、UPDATE、DELETE等语句的解析与执行路径，结合设计报告掌握关系模型、ACID属性、查询优化与索引结构如何落地，并借助测试用例验证系统功能与稳定性，适合作为课程设计参考或数据库内核入门实践材料。
1. 从零手写一个 miniSQL：数据库课程设计到底要交付什么
课程设计里最容易被低估的一件事，是把「会用数据库」和「会做数据库」分开。平时写SELECT、建索引、调事务，都是站在使用者视角；而一份数据库系统实现的期末大程，要求你站到内核视角，把 SQL 语句从字符串一路变成磁盘上的字节。这个项目要解决的核心问题很具体：用 C/C++ 实现一个能跑通建表、插入、查询、删除、索引、简单事务的 miniSQL，把词法语法分析、系统管理、记录管理、索引管理、查询执行这几层串成一条完整链路。它适合正在做数据库课设、需要交一份可演示可答辩方案的学生，也适合想补一遍存储引擎底层实现的从业者。关键词 SQL、数据库、C/C++ 在这里不是标签，而是三层技术栈：SQL 是输入契约，C/C++ 是实现载体，数据库是最终交付物。
2. 需求拆解与技术选型：先定边界再动手
2.1 功能边界：哪些 SQL 必须支持，哪些明确不做
做 miniSQL 最容易翻车的地方不是写不出来，而是范围失控。血泪经验是：一开始想支持 JOIN、子查询、聚合函数，写到一半发现连WHERE的多条件组合都没跑通。我一般会先把功能切成「必须」「加分」「明确不做」三档，写进设计文档第一页，答辩时也拿它当验收基线。
必须支持的部分通常包括：CREATE TABLE（含主键、唯一约束、非空）、DROP TABLE、CREATE INDEX、DROP INDEX、INSERT、DELETE、UPDATE、SELECT（单表、WHERE等值与范围条件、ORDER BY单列）。加分项是AND/OR组合条件、NULL语义、唯一性冲突检测、简单事务（BEGIN/COMMIT/ROLLBACK）。明确不做的是多表 JOIN、子查询、视图、触发器、复杂聚合。这个边界不是偷懒，而是让每一层都有明确的测试用例可覆盖。
类型系统也要先定死。通常的做法是支持INT、FLOAT、CHAR(n)三类，CHAR定长存储，避免变长记录带来的页内碎片问题。主键默认建聚簇索引或至少建唯一索引，这个决定会直接影响后面记录管理与索引管理的耦合方式。
2.2 技术选型：为什么是 C/C++ 加自管缓冲池
选 C/C++ 不是因为它「高级」，而是因为这个项目要频繁做内存布局控制、指针偏移计算、文件随机读写，用带 GC 的语言反而要绕开运行时抽象。编译器用g++ -std=c++17，构建用 CMake 或简单 Makefile 都行，关键是能一键编译出可执行文件，答辩现场不能卡在环境上。
存储层不引第三方库，自己实现缓冲池（Buffer Pool）。原因很实际：课程设计要展示你对页式存储的理解，直接调 SQLite 就失去意义了。缓冲池通常按固定页大小（如 4KB）管理，维护页表、脏页标记、LRU 替换策略。下面是一个页头结构的示意，字段设计决定了后续所有模块怎么读写：
// page.h —— 页头与页内布局约定 constexpr int PAGE_SIZE = 4096; struct PageHeader { int32_t page_id; // 页号，-1 表示无效页 int32_t next_page; // 链表下一页，用于溢出页或空闲页链 int16_t slot_count; // 当前页内记录槽位数 int16_t free_offset; // 空闲空间起始偏移 int32_t lsn; // 日志序列号，事务回滚时用 bool dirty; // 脏页标记，写回时判断 }; // 页内记录采用槽目录（slot directory）方式： // [PageHeader][slot0_offset][slot1_offset]...[free space]...[record data]这段结构的关键在于槽目录：每条记录在页内不按顺序存放，槽目录保存偏移，删除记录时只清槽位不搬数据，避免页内大范围移动。free_offset从页尾向前增长，槽目录从页头向后增长，两者相遇即页满。lsn字段是为事务预留的，即使第一版不做完整 WAL，也建议留位，否则后面加回滚要改所有页结构，属于典型的后悔药没处买。
2.3 模块划分：五层职责与依赖方向
整体按五层划分，依赖只能自上而下，禁止反向调用，否则调试时会出现「改索引把解析器改崩」的玄学问题。
| 层次 | 模块 | 核心职责 | 对外接口 |
|---|---|---|---|
| 第一层 | 词法语法分析 | SQL 文本转 AST | parse(sql) -> Statement* |
| 第二层 | 系统管理 | 库表元数据、schema 持久化 | getTable(name)、createTable() |
| 第三层 | 查询执行 | AST 转执行计划、算子调度 | execute(Statement*) |
| 第四层 | 记录管理 | 记录增删改查、页内槽位管理 | insertRecord()、scan() |
| 第五层 | 索引管理 + 缓冲池 | B+ 树索引、页缓存与磁盘 IO | search(key)、fetchPage() |
依赖方向是：解析层只产出 AST，不碰存储；执行层调记录管理和索引管理；记录管理和索引管理都通过缓冲池拿页。系统管理单独维护一张元数据表（通常也用一个特殊页或独立文件存），记录所有表名、列定义、索引定义。这个分层看起来朴素，但它让每个模块都能单独写单元测试，答辩时你可以指着某一层说「这里我单独测过 200 条用例」。
3. 核心模块实现：从 SQL 文本到磁盘字节
3.1 词法与语法分析：手写递归下降还是用工具
课程设计里常见的两条路：用 Flex/Bison 生成，或者手写递归下降。我的建议是手写，理由有三：一是 SQL 子集不大，手写可控；二是报错信息能精确到字符位置，答辩演示时输入错误 SQL 能给出人话提示；三是避免环境里装不上 Flex/Bison 的尴尬。
词法分析把输入切成 token 流，token 类型包括关键字、标识符、数字字面量、字符串字面量、运算符、分隔符。关键字大小写不敏感，标识符大小写敏感（或统一转小写，二选一写进文档）。下面是一个简化的 token 定义与扫描循环：
enum class TokenType { KEYWORD, IDENT, NUMBER, STRING, OP, PUNCT, END }; struct Token { TokenType type; std::string text; // 原始文本 int pos; // 在 SQL 中的起始位置，报错用 }; // 扫描主循环：跳过空白，按首字符分派 std::vector<Token> tokenize(const std::string& sql) { std::vector<Token> out; size_t i = 0; while (i < sql.size()) { char c = sql[i]; if (isspace(c)) { ++i; continue; } if (isalpha(c) || c == '_') { // 标识符或关键字 size_t start = i; while (i < sql.size() && (isalnum(sql[i]) || sql[i] == '_')) ++i; std::string word = sql.substr(start, i - start); out.push_back({isKeyword(word) ? TokenType::KEYWORD : TokenType::IDENT, word, (int)start}); } else if (isdigit(c)) { // 数字，含小数 size_t start = i; while (i < sql.size() && (isdigit(sql[i]) || sql[i] == '.')) ++i; out.push_back({TokenType::NUMBER, sql.substr(start, i - start), (int)start}); } else if (c == '\'') { // 字符串字面量 size_t start = ++i; while (i < sql.size() && sql[i] != '\'') ++i; out.push_back({TokenType::STRING, sql.substr(start, i - start), (int)start}); ++i; // 跳过收尾引号 } else { // 运算符与标点 out.push_back({TokenType::OP, std::string(1, c), (int)i}); ++i; } } out.push_back({TokenType::END, "", (int)sql.size()}); return out; }pos字段是容易被省掉但极有用的设计：语法分析报错时直接输出「第 23 个字符附近期望)」，比「syntax error」强太多。关键字表用unordered_set存，查表 O(1)。字符串字面量这里没处理转义引号，如果要做，在遇到''时继续扫描而不是结束。
语法分析用递归下降，每个非终结符一个函数：parseStatement看首关键字分派到parseCreate、parseInsert、parseSelect等；parseSelect内部再拆parseSelectList、parseFrom、parseWhere、parseOrderBy。AST 节点用基类加派生类，或者用带kind字段的联合结构，前者更清晰。表达式解析按优先级分层：OR最低，其次AND，再是比较运算，最后是字面量与列引用。这一层写完，先用十几个手写 SQL 跑通 AST 打印，确认结构对了再往下走。
3.2 记录管理：页内槽位、变长字段与扫描迭代器
记录管理负责把一条记录塞进页、从页里读出来、按条件扫描。前面定了CHAR定长，但INT、FLOAT、CHAR(n)混合时记录长度是固定的，这大大简化了实现：每条记录长度 = 各列长度之和，页内槽位只存偏移，读记录时按 schema 逐列解析。
插入流程：先算记录长度，找有空闲空间的页（从表对应的页链头开始扫，或维护空闲页列表），在free_offset处写入记录字节，槽目录追加一个偏移，更新slot_count和free_offset。如果当前页放不下，分配新页并挂到页链尾部。删除流程：根据槽位号把对应槽目录项标记为无效（比如置 -1），记录空间不立即回收，等页内碎片过多时做一次整理（compaction）。更新如果长度不变，原地覆盖；长度变化（本项目定长，基本不涉及）则删旧插新。
扫描迭代器是查询执行层最常调的接口，设计成「打开—取下一行—关闭」三段式：
class TableScanner { public: TableScanner(BufferPool* bp, TableMeta* meta, int first_page) : bp_(bp), meta_(meta), page_id_(first_page), slot_(0) {} // 取下一行，返回 false 表示扫描结束 bool next(std::vector<Value>& row) { while (page_id_ != -1) { Page* p = bp_->fetchPage(page_id_); auto* hdr = (PageHeader*)p->data; while (slot_ < hdr->slot_count) { int off = slotOffset(p, slot_++); if (off < 0) continue; // 已删除槽位，跳过 row = decodeRecord(p->data + off, meta_); return true; } page_id_ = hdr->next_page; // 当前页扫完，跳下一页 slot_ = 0; } return false; } private: BufferPool* bp_; TableMeta* meta_; int page_id_; int slot_; };decodeRecord按 schema 逐列读：INT读 4 字节，FLOAT读 4 字节，CHAR(n)读 n 字节并去掉尾部填充。这里有个细节：CHAR比较时要去掉尾部空格，否则'abc'和'abc '判不等，测试用例会莫名其妙挂掉。扫描器不负责过滤，过滤交给执行层的Filter算子，这样扫描器可以复用于全表扫描和索引回表两种场景。
3.3 索引管理：B+ 树的插入分裂与范围查询
索引用 B+ 树，这是课程设计的标准答案，也是答辩必问点。节点分内部节点和叶子节点：内部节点存 key 和子页号，叶子节点存 key 和记录定位（页号 + 槽位号），叶子之间用next指针串成链表，支持范围扫描。
插入的核心是分裂。叶子节点满了，把一半 key 复制到新节点，把中间 key 上推到父节点；父节点满了继续分裂，直到根节点分裂时新建根。下面给出叶子分裂的关键片段，重点看 key 的分配和链表维护：
// 叶子节点分裂：node 为已满叶子，返回新节点页号，mid_key 带出上推 key int splitLeaf(BPlusNode* node, Key& mid_key) { int new_pid = allocPage(); BPlusNode* right = initNode(new_pid, /*is_leaf=*/true); int mid = node->key_count / 2; // 右半部分 key 与定位复制到新节点 for (int i = mid; i < node->key_count; ++i) { right->keys[i - mid] = node->keys[i]; right->rids[i - mid] = node->rids[i]; } right->key_count = node->key_count - mid; node->key_count = mid; // 维护叶子链表：node -> right -> 原 next right->next = node->next; node->next = new_pid; mid_key = right->keys[0]; // 叶子分裂，上推的是右节点第一个 key 的副本 return new_pid; }注意叶子分裂上推的是「副本」，key 仍留在叶子中，这是 B+ 树与 B 树的本质区别，答辩时被问到要能说清。内部节点分裂则是把中间 key 上推并从原节点移除。范围查询WHERE id BETWEEN a AND b的流程：从根向下找到第一个key >= a的叶子，沿next链表向后扫，直到 key 超过b，每个 key 拿到rid回表取记录。等值查询找到叶子后还要继续向右看，因为 B+ 树允许重复 key（非唯一索引场景）。
索引与记录的同步是另一个坑：插入记录后要插索引，删除记录后要删索引，更新主键列等于删旧插新。建议把「记录操作 + 索引操作」包在一个函数里，别让执行层分别调，否则漏调一次就是数据不一致。
4. 查询执行与事务：把算子串成执行计划
4.1 执行计划：火山模型与算子接口
查询执行用火山模型（Volcano Model），每个算子实现open()、next()、close()三个方法，父算子调子算子的next()拉取一行。单表查询的计划通常是Project -> Filter -> Scan或Project -> Filter -> IndexScan。优化点不多，但至少要做两件事：WHERE条件里如果有索引列等值条件，走索引扫描而不是全表；ORDER BY如果列上有索引，直接利用索引有序性省掉排序算子。
class Operator { public: virtual void open() = 0; virtual bool next(std::vector<Value>& row) = 0; // false 表示无更多行 virtual void close() = 0; virtual ~Operator() = default; }; // 过滤算子：从子算子拉行，满足谓词才向上返回 class FilterOp : public Operator { public: FilterOp(Operator* child, Predicate pred) : child_(child), pred_(std::move(pred)) {} void open() override { child_->open(); } bool next(std::vector<Value>& row) override { while (child_->next(row)) { if (pred_.eval(row)) return true; // 命中才返回 } return false; } void close() override { child_->close(); } private: Operator* child_; Predicate pred_; };Predicate内部持有列下标、比较运算符和右值，eval按列下标取值比较。这个接口的好处是算子可以任意嵌套，加一个SortOp或LimitOp不用改其他代码。执行层拿到 AST 后，先做一遍简单绑定（把列名解析成列下标，检查表和列是否存在），再自底向上构造算子链，最后从根算子反复next()输出结果。
4.2 简单事务：撤销日志与回滚边界
如果做事务加分项，最小可行方案是「语句级回滚」而不是完整 ACID。做法是维护一个 undo 日志：每次插入记录记下(表, 页号, 槽位号)，删除记录记下整条记录内容，更新记下旧值。ROLLBACK时倒序执行 undo。COMMIT时清空日志。这个方案不支持并发，但单线程演示足够，答辩时能讲清「我们实现了原子性，隔离性和持久化是简化处理」。
要注意的是索引也要进 undo：插入记录时插了索引，回滚时要把索引项删掉，否则索引里留下指向空槽位的脏 key，后续查询回表拿到无效记录。这个坑我在类似项目里踩过，现象是回滚后SELECT偶尔返回空行，查了半天才发现是索引没回滚。
5. 避坑与排查：五个最容易翻车的点
5.1 页内偏移算错导致数据错位
现象：插入几条记录后查询结果字段串位，INT列读出乱码。原因：CHAR(n)写入时没按 n 字节对齐填充，或者decodeRecord的偏移累加用了sizeof(std::string)而不是 schema 定义长度。解决：写一个recordSize(TableMeta*)函数统一算长度，编码解码都调它，禁止各处手算偏移；再加一个自检函数，插入后立即读回比对。
5.2 缓冲池脏页未写回导致重启丢数据
现象：程序正常退出后重新打开，刚插入的数据没了。原因：缓冲池只在页被替换时写回，程序退出时没遍历脏页刷盘。解决：在BufferPool析构或显式flushAll()里遍历所有页帧，dirty为真的写回文件；更稳妥的是每次COMMIT后强制刷相关页，牺牲一点性能换确定性。
5.3 B+ 树分裂后父节点指针未更新
现象：索引数据量超过一页后，部分 key 查不到。原因：叶子分裂返回新页号，但父节点没插入新的子指针和分隔 key，或者根节点分裂时没更新元数据里的根页号。解决：分裂函数必须返回(new_page_id, mid_key)，调用方负责插父节点；根分裂单独处理，更新系统管理里的根页号。写完先做 1000 条随机插入再全量查询的回归测试。
5.4 字符串比较忽略尾部空格
现象：WHERE name = 'abc'查不到存进去的'abc'。原因：CHAR定长存储补了空格，比较时没 trim。解决：在Value的比较函数里对CHAR类型统一去尾部空格再比，或者存储时右补空格、比较时按定长逐字节比但忽略尾部空格。两种都行，关键是全项目统一。
5.5 解析器对错误输入直接崩溃
现象：演示时输入一条不完整 SQL，程序段错误退出。原因：递归下降里没做 token 越界检查，peek()在END之后继续取。解决：所有advance/expect前检查当前 token 类型，遇到END抛解析异常，顶层catch后打印错误位置并继续接受下一条输入。答辩现场程序崩一次，印象分直接掉一档。
6. 验收与答辩：怎么证明这套 miniSQL 真的能跑
验收不是「能启动就行」，而是要有一套可复现的演示脚本和一张对照表。我一般会准备三样东西：一份 SQL 脚本、一份预期输出、一份模块自测清单。演示脚本按功能递进，从建表到事务回滚，每条语句都有明确预期，现场逐条跑，跑完对照输出。
| 验收项 | 操作 | 通过标准 |
|---|---|---|
| 建表与元数据 | CREATE TABLE t(id INT, name CHAR(8), score FLOAT); | 重复建同名表报错，DROP后重建成功 |
| 插入与约束 | 插入主键重复、非空列插NULL | 均报错且不写入脏数据 |
| 全表扫描 | 插入 1000 行后SELECT * | 行数、字段值完全一致 |
| 索引等值与范围 | 对id建索引，查id=500、id BETWEEN 100 AND 200 | 结果与全表扫描一致，且走索引（可打印计划验证） |
| 删除与更新 | 删中间若干行、更新若干行 | 再查结果正确，索引同步无脏 key |
| 事务回滚 | BEGIN后插入再ROLLBACK | 数据与索引均回到事务前状态 |
| 异常输入 | 输入残缺 SQL、未知表名 | 打印错误位置，程序不退出 |
答辩技巧上，别一上来讲架构图，先跑演示，让评委看到东西能动，再回头讲分层。被问到「为什么不用 B 树用 B+ 树」，答「范围查询走叶子链表，内部节点不存数据，同样页大小能存更多 key，树更矮」。被问到「事务做到什么程度」，如实说「语句级原子性，隔离性和持久化做了简化」，比硬吹完整 ACID 然后被追问穿帮强。代码量、测试用例数这些数字提前统计好，写在 PPT 角落，评委扫一眼就有底。
从那以后我每次带这类课程设计，都强制先写验收脚本再写实现，脚本跑不通就不算完成，这个习惯帮我省掉了无数次「演示前夜发现主流程断了」的慌乱。希望帮到你。
本文还有配套的精品资源，点击获取
