简介miniSQL 是浙江大学数据库设计课程的期末大程成果面向希望从零理解关系数据库内部机制的高校学生与 C/C 开发者可用于课程设计参考、数据库引擎入门及 SQL 执行流程学习。压缩包共 29 个文件、约 885KB含 9 个 cpp、9 个 h、9 个 txt以及 1 份 pdf 设计报告和 1 个 exe 可执行程序源码覆盖 API、解释器、缓冲管理、记录管理、目录与 B 树索引等模块报告记录项目目标、设计决策、实现细节、问题及测试结果。已有 1532 人学习下载。读者可直接运行 myMiniSQL.exe 验证建表、增删改查与索引操作也可结合测试文件和源码梳理 SQL 语句从解析到执行的链路理解 ACID、查询优化和索引结构在迷你数据库中的落地方式报告与代码相互印证便于复盘模块划分、接口设计和调试思路同时可借助测试用例检查功能完整性适合作为数据库课程项目与系统设计入门的实践样本。1. 从一份期末大程说起miniSQL 到底要交付什么miniSQL 这类数据库期末大程真正难的不是写一条CREATE TABLE而是让 SQL 解析、记录管理、B 树索引和执行器在同一套页式存储上闭环。答辩现场最常被问的往往不是“B 树多难”而是“为什么这条 SQL 走了全表扫”“删完记录后索引里为什么还能查到”。这套方案面向的是一份可运行的 C/C 单机数据库支持建表、增删改查、建索引、按索引检索最后用脚本跑通一致性验证。读者如果是做课程设计、毕设前期原型或者想用 C 练一遍存储引擎这套结构可以直接对照着搭从业者也能把它当成一个最小数据库的模块划分参考。2. 需求拆解与技术选型为什么用 C/C 手写而不是套框架2.1 功能边界DDL、DML、索引三条主线miniSQL 的功能边界要先钉死不然后面每加一个语法都像在补漏。通常的做法是把需求拆成三条主线DDL 负责表与索引的生命周期DML 负责记录读写索引负责加速等值与范围查询。三条主线共享同一套系统目录任何一条没闭环验收时都会露馅。DDL 至少覆盖CREATE TABLE、DROP TABLE、CREATE INDEX、DROP INDEX。表定义里常见的字段类型是int、float、char(n)约束至少支持主键、唯一、非空。DML 覆盖INSERT、DELETE、UPDATE、SELECTSELECT先做单表条件支持、、、、、和AND聚合与连接可以作为加分项但不要在第一版塞进去。索引主线要求 B 树能跟着记录插入、删除、更新同步维护并且能回答两类问题等值查找和范围扫描。这里有个容易被忽略的边界索引不是“建完就完事”它要和记录管理器共享 RID。RID 通常由页号加槽号组成记录一旦搬家索引里的 RID 就失效。所以需求里要明确一条变长字段更新导致记录重分配时索引必须同步更新或者干脆限制更新只改定长部分。我一般会在需求文档里写一句“首版不支持更新主键”能省掉大量边界讨论。功能边界还要写清楚“不做什么”。比如不做完整事务、不做多表连接、不做并发控制这些不是偷懒而是把验收范围收窄。课程设计最怕的是功能列表很长现场一跑就崩。把单表 CRUD、索引维护、错误提示做扎实比堆十个半成品算子更有说服力。2.2 技术选型C11 及以上 页式文件 手写 B 树的取舍用 C/C 实现 miniSQL核心取舍在“自己写到哪一层”。用现成的 SQLite 当然快但课程设计要展示的是存储、索引、执行器的连接关系套壳就失去意义。用第三方 B 树库也不合适索引维护本身就是答辩重点。比较稳的选型是C11 及以上、标准库容器做内存结构、文件 I/O 自己封装成页式存储、B 树手写。页大小通常取 4KB和大多数文件系统块大小对齐调试时也容易按页号定位。缓冲池用 LRU 替换每个页框记录 pin 计数和脏页标记。B 树的阶数不写死按页大小和 key 长度算出来内部节点存n个 key 和n1个孩子指针叶子节点存 key 与 RID 列表。这样换页大小或换 key 类型时不用改树结构。为什么不直接用std::map做索引内存索引跑测试很快但一关机就没了而且无法展示页分裂、节点合并这些过程。课程设计要的是“能落盘、能恢复、能解释清楚”。手写 B 树还有一个好处你能在答辩时画出一次插入分裂前后的页布局这比背概念管用。工程上建议用 CMake 或 Makefile 统一构建Debug 构建开-O0 -gRelease 构建开-O2。测试 SQL 放在test/sql/下期望输出放在test/expected/下跑完用 diff 比对。这个习惯后面验收章还会展开。2.3 工程约束构建、调试与可复现环境miniSQL 这种项目代码量不大但模块多最容易翻车的地方是“本机能跑换台机器就崩”。血泪经验是从第一天就把构建脚本和测试脚本写进仓库不要等到答辩前才补。目录可以按下面这样分头文件和源文件分开测试数据独立存放miniSQL/ ├── CMakeLists.txt ├── include/ │ ├── parser/ # 词法、语法、AST │ ├── catalog/ # 系统目录与元数据 │ ├── storage/ # 页、缓冲池、记录管理 │ ├── index/ # B 树 │ └── executor/ # 算子与执行计划 ├── src/ ├── test/ │ ├── sql/ # 回归 SQL 脚本 │ └── expected/ # 期望输出 └── tools/ └── check_index.cpp # 索引与记录一致性检查构建脚本里至少有两个目标miniSQL主程序和check_index校验工具。主程序负责交互式输入和脚本输入校验工具负责扫表比对索引项。参数上数据库文件路径、页大小、缓冲池页数都从命令行或配置文件读不要硬编码在源码里。这样答辩时换一个数据目录就能重跑不用改代码重新编译。调试阶段建议开 AddressSanitizer 和 UBSan尤其是解析器和记录序列化部分。很多“玄学崩溃”其实是越界读或未初始化内存普通 gdb 不一定能立刻定位。把-fsanitizeaddress,undefined加进 Debug 构建跑一遍回归脚本能提前发现一批问题。3. 总体架构与存储层设计六个模块如何各管一段3.1 分层架构与调用链miniSQL 的调用链可以按“SQL 进来、结果出去”来切Parser 把文本变成 ASTAnalyzer 查系统目录做语义检查Planner 生成执行计划Executor 调算子算子通过 Record Manager 读写记录Record Manager 通过 Buffer Pool 拿页Buffer Pool 最终落到 Disk Manager。Index Manager 横在 Executor 和 Record Manager 之间负责索引项的增删查。模块主要职责对外接口Parser词法、语法分析产出 ASTparse(sql) - StatementCatalog表、列、索引元数据getTable(name)、getIndexes(table)Record Manager记录插入、删除、更新、扫描insertRecord、deleteRecord、scanBuffer Pool页缓存、pin/unpin、脏页刷盘fetchPage、unpinPage、flushIndex ManagerB 树查找、插入、删除、范围扫描insertEntry、deleteEntry、rangeScanExecutor算子流水线、计划执行execute(plan) - ResultSet这张表建议贴在项目 README 里答辩时按调用链讲比按文件讲清楚得多。模块之间的依赖要单向Executor 依赖 Record/IndexRecord 依赖 BufferBuffer 依赖 DiskCatalog 被 Parser 之后的 Analyzer 和 Executor 使用。不要让 Buffer Pool 反向调用 Executor否则后面加功能会缠成一团。3.2 页式存储与缓冲池管理页是磁盘和内存之间的最小单位。一个页里通常放页头、槽目录和记录数据。页头记录页类型、槽数量、空闲空间偏移、下一条页号槽目录存每条记录的偏移和长度记录数据从页尾向前长。删除记录时只把槽标记为空空间留给后续插入复用。// 页头结构固定在页起始位置字段按 4 字节对齐 struct PageHeader { uint16_t page_type; // 0数据页, 1索引页, 2目录页 uint16_t slot_count; // 当前槽数量 uint16_t free_offset; // 空闲区起始偏移从页尾向前增长 uint16_t free_space; // 剩余连续空闲字节数 int32_t next_page; // 下一条页号-1 表示无 int32_t prev_page; // 上一条页号-1 表示无 }; // 槽目录项记录在页内的位置 struct Slot { uint16_t offset; // 记录起始偏移 uint16_t length; // 记录长度 uint8_t flags; // 0空槽, 1有效, 2已删除 };free_offset和free_space要一起维护插入时从空闲区分配删除时把槽置为已删除但不立即合并等页内碎片超过阈值再做一次紧凑化。紧凑化会移动记录位置所以必须同步更新槽目录和索引里的 RID如果首版不想处理这个复杂度可以只做“删除后空间复用”不移动已有记录。缓冲池的核心是 pin 计数。fetchPage(page_id)先查页表命中就把 pin 加一返回未命中就找一个未 pin 的页框脏页先刷盘再从磁盘读入。unpinPage(page_id, is_dirty)把 pin 减一脏标记或上去。pin 计数大于零的页不能被替换这是保证执行器持有页指针期间页不被换出的底线。提示缓冲池页数不要设得太小。测试脚本一次扫几万行时页数太小会频繁刷盘跑起来像卡死。可以先设 128 到 256 个页框再根据机器内存调。3.3 系统目录与元数据表系统目录是 miniSQL 的黑匣子表存不存在、列什么类型、索引建在哪些列上都靠它回答。首版可以用固定的系统表来存元数据比如__tables、__columns、__indexes启动时加载到内存DDL 变更后写回。这样比直接序列化 C 结构更稳调试时也能用 SQL 查。struct ColumnMeta { std::string table_name; std::string column_name; uint8_t type; // 0int, 1float, 2char uint16_t length; // char(n) 的 n其他类型为固定长度 bool not_null; bool is_primary; }; struct IndexMeta { std::string index_name; std::string table_name; std::vectorstd::string columns; // 首版建议单列索引 bool is_unique; int32_t root_page; // B 树根页号 };root_page很关键。B 树分裂时根可能变化索引元数据要跟着更新如果只在内存里维护根页号进程一退出索引就找不到了。建索引时先扫表拿 RID再批量插入 B 树比逐条INSERT触发索引维护更快也更容易做失败回滚。3.4 记录组织与变长字段处理记录组织要解决两个问题一条记录怎么序列化以及删除后空间怎么复用。定长字段直接按偏移写变长char(n)可以在记录头里存长度后面跟实际字节。记录头建议带一个 null bitmap非空约束在插入前检查不依赖存储层报错。// 记录布局记录头 null bitmap 定长/变长字段数据 // 记录头里存字段数量和总长度便于反序列化 struct RecordHeader { uint16_t field_count; uint16_t record_size; uint8_t null_bitmap[2]; // 最多支持 16 个字段按需扩展 };更新变长字段是经典坑新值比旧值长当前槽放不下只能删旧记录、插新记录再更新所有索引里的 RID。这个动作不是原子的中途失败会出现“记录没了、索引还在”。首版的稳妥做法是限制UPDATE只改定长字段或者把变长字段更新走“删除 插入”并加一致性校验工具。不要让执行器悄悄搬家却不通知索引。4. 核心模块实现从 SQL 解析到执行器与索引4.1 词法语法分析与 AST 设计词法和语法可以手写递归下降不必上 parser generator。miniSQL 的语法子集不大手写反而容易控制错误位置。Token 类型覆盖关键字、标识符、数字、字符串、比较符、逗号和括号。Parser 对外只暴露一个parse内部按语句类型分派到parseCreate、parseInsert、parseSelect等函数。enum class TokenType { KEYWORD, IDENT, NUMBER, STRING, EQ, NE, LT, LE, GT, GE, COMMA, LPAREN, RPAREN, SEMI, END }; struct Token { TokenType type; std::string text; size_t pos; // 在原始 SQL 中的位置报错时带上 }; // AST 基类所有语句节点继承它 struct Statement { virtual ~Statement() default; virtual std::string name() const 0; }; struct CreateTableStmt : Statement { std::string table; std::vectorColumnDef columns; std::string name() const override { return CreateTable; } };pos字段是我强烈建议保留的。解析失败时输出“第 12 个字符附近期望)”比只报“语法错误”好排查得多。AST 节点用std::unique_ptr管理避免手写 delete。语义分析阶段再查 Catalog确认表存在、列类型匹配、主键不重复定义这些检查放在 Parser 里会让解析器变重放在 Analyzer 里更合适。4.2 执行器与算子流水线执行器用火山模型每个算子实现open、next、close。next返回一行或结束标记。SeqScan扫记录页IndexScan调 B 树范围扫描拿 RID 再回表Filter做谓词判断Project选列Insert、Delete、Update调 Record Manager 和 Index Manager。算子之间用std::unique_ptrExecutor串起来。class Executor { public: virtual ~Executor() default; virtual void open() 0; // 返回 true 表示取到一行row 里是列值和 RID virtual bool next(Row row) 0; virtual void close() 0; }; class IndexScan : public Executor { public: IndexScan(IndexManager *idx, RecordManager *rec, const std::string index_name, const Range range) : idx_(idx), rec_(rec), index_name_(index_name), range_(range) {} void open() override { // 先拿到索引项迭代器再逐条回表 iter_ idx_-rangeScan(index_name_, range_); } bool next(Row row) override { RID rid; if (!iter_-next(rid)) return false; return rec_-getRecord(rid, row); // 回表读完整记录 } void close() override { iter_.reset(); } private: IndexManager *idx_; RecordManager *rec_; std::string index_name_; Range range_; std::unique_ptrIndexIterator iter_; };IndexScan的关键是“索引项只存 key 和 RID回表再取完整行”。如果查询只涉及索引列可以做覆盖索引直接返回省掉回表首版不做也没关系但要在执行计划里说明。open里拿迭代器close里释放异常路径也要保证close被调用否则缓冲池的 pin 会泄漏。4.3 B 树索引的插入删除与范围扫描B 树的节点分内部节点和叶子节点。内部节点存 key 和孩子页号叶子节点存 key 和 RID 列表叶子之间用next指针串起来做范围扫描。阶数按页大小算max_keys (page_size - header_size) / (key_size ptr_size)。插入时从根往下找到叶子插进去满了就分裂把中间 key 提上去。删除时先删叶子项低于半满再尝试借位或合并。// B 树叶子节点key 与 RID 列表next 指向下一条叶子页 struct LeafNode { PageHeader header; uint16_t key_count; int32_t next_leaf; // 范围扫描用 // 后面紧跟 key_count 个 Key 和对应的 RID 列表 }; // 查找返回第一个 key 的位置供等值和范围扫描复用 int LeafNode::lowerBound(const Key key, const KeyComparator cmp) { int lo 0, hi key_count; while (lo hi) { int mid (lo hi) / 2; if (cmp(getKey(mid), key) 0) lo mid 1; else hi mid; } return lo; }非唯一索引要把同一个 key 的多个 RID 挂在叶子项上或者把 RID 拼进 key 里保证唯一。前者查询时遍历 RID 列表后者实现简单但 key 变长。课程设计里建议用“key RID 列表”并在删除时按 RID 精确删除避免误删同 key 的其他记录。范围扫描从lowerBound开始沿next_leaf往后走直到超过上界。4.4 简单查询优化与执行计划输出首版不追求复杂优化但要有“索引选择”规则等值条件命中索引列就走IndexScan范围条件命中索引列也走IndexScan否则走SeqScan。多个条件用AND连接时选过滤性最强的索引其余条件留给Filter。这条规则用一张小表就能说清楚。查询条件可用索引计划id 10idx_idIndexScan(idx_id) - Filterage 20 AND age 30idx_ageIndexScan(idx_age) - Filtername A无SeqScan - Filterid 10 AND age 20idx_id、idx_ageIndexScan(idx_id) - Filter(age)执行计划要能打印出来答辩时直接EXPLAIN SELECT ...展示走没走索引。实现上可以在 Planner 里生成计划树每个节点带type和cost估算cost 不用很准能比较“全表扫页数”和“索引扫描预估行数”即可。不要为了优化而优化先把计划打印和索引选择做对再考虑谓词下推。5. 避坑与排查最容易翻车的五件事5.1 页内空闲空间与记录迁移现象更新一条char(100)字段后原来能查到的记录突然查不到或者索引扫描返回旧值。原因通常是新记录比旧槽长页内放不下记录被搬到另一页但索引里的 RID 没更新。解决方式有两种一是更新前判断新长度超过旧槽就删旧插新并在同一个执行器事务里更新所有索引二是首版限制变长字段更新只允许改定长字段。无论选哪种都要在UPDATE路径上打日志记录旧 RID 和新 RID。5.2 索引与记录不一致现象SELECT走索引查出一条已经删除的记录或者全表扫能查到、索引查不到。原因多半是删除顺序不对先删了记录再删索引中途异常退出或者索引删除时按 key 删误删了同 key 的其他 RID。解决方式是固定维护顺序插入时先写记录再插索引删除时先删索引再删记录并在check_index工具里做全量比对。工具逻辑很简单扫全表建 RID 集合扫索引建另一个集合两边差集打印出来。5.3 事务缺失下的并发写现象测试脚本并发插入时偶发页损坏或者缓冲池里同一页被两个线程同时改。原因是没有事务和锁页的 pin/unpin 不是线程安全的B 树分裂时父节点和子节点也没加锁。课程设计通常默认单线程但测试脚本可能用多进程跑。解决方式是在文档里明确“单线程执行”或者在表级加读写锁缓冲池的页表加互斥量。不要假装支持并发却不加锁答辩时被问一句“两个客户端同时插入怎么办”就会露馅。5.4 内存泄漏与异常路径现象跑十万行插入后内存持续上涨或者解析一条错误 SQL 后进程越来越慢。原因常见于 AST 节点手动new没delete、异常抛出后缓冲池页没unpin、B 树迭代器没释放。解决方式是用std::unique_ptr管理 AST 和算子缓冲池用 RAII 封装PageGuard构造时fetchPage析构时unpinPage。调试时开 AddressSanitizer跑一遍错误 SQL 回归集泄漏点会直接打出来。5.5 测试数据与边界条件现象本地测试全过答辩现场换一组数据就崩。原因通常是只测了“正常路径”空表、char超长、int溢出、重复主键、删除不存在的行、索引列为NULL。解决方式是准备一组边界 SQL每次改完存储或索引都跑一遍。测试集至少覆盖空表扫描、单页插满、跨页插入、删除后复用槽、索引分裂、索引合并、范围扫描边界。跑完用 diff 比对期望输出别靠肉眼。6. 验收与答辩用一套可复现的测试脚本说话验收时最怕“演示到一半卡住”。我一般会把验收拆成固定脚本按顺序跑每步都有期望输出。下面这个脚本结构可以直接改成自己的#!/usr/bin/env bash set -e DB./build/miniSQL rm -rf /tmp/minisql_test mkdir -p /tmp/minisql_test # 1. 建表与插入 $DB --db /tmp/minisql_test --file test/sql/01_create_insert.sql \ /tmp/out1.txt diff /tmp/out1.txt test/expected/01_create_insert.out # 2. 无索引查询与执行计划 $DB --db /tmp/minisql_test --file test/sql/02_seq_scan.sql \ /tmp/out2.txt diff /tmp/out2.txt test/expected/02_seq_scan.out # 3. 建索引后走 IndexScan $DB --db /tmp/minisql_test --file test/sql/03_index_scan.sql \ /tmp/out3.txt diff /tmp/out3.txt test/expected/03_index_scan.out # 4. 删除后一致性校验 $DB --db /tmp/minisql_test --file test/sql/04_delete.sql /tmp/out4.txt diff /tmp/out4.txt test/expected/04_delete.out ./build/check_index /tmp/minisql_test脚本只做三件事跑 SQL、比对输出、跑一致性校验。--db指定数据目录--file指定 SQL 文件输出重定向到临时文件再 diff。check_index返回非零就说明索引和记录不一致现场直接暴露问题比口头解释可信。验收项操作通过标准建表与元数据执行CREATE TABLE后查系统表列类型、约束、主键正确插入与全表扫插入 1000 行后SELECT *行数、字段值一致索引等值查询建索引后EXPLAIN 查询计划为IndexScan结果正确索引范围查询WHERE id BETWEEN ...边界包含正确无重复行删除与索引维护删除部分行后校验check_index退出码为 0错误处理重复主键、类型不匹配报错信息带位置进程不崩答辩演示顺序也有讲究先建表插入跑一条无索引查询并EXPLAIN展示全表扫再建索引跑同一条查询展示IndexScan接着做范围查询和删除最后跑check_index。这套顺序能把“为什么需要索引”讲清楚也能自然带出 B 树分裂和 RID 回表。老师常问的三个问题提前准备页大小为什么选 4KB、B 树分裂时根节点怎么变、索引选择规则在什么情况下会选错。答不上来的细节不要编直接说“首版按单列索引处理多列索引在扩展点里”。从那以后我每次带这类课程设计都强制先写验收脚本再写功能跑不通就不往下加模块。希望帮到你。本文还有配套的精品资源点击获取
