从零手写miniSQL：数据库课程设计核心实现与避坑指南

简介这份资源是浙江大学数据库设计课程的期末大程成果——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 -stdc17构建用 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 文本转 ASTparse(sql) - Statement*第二层系统管理库表元数据、schema 持久化getTable(name)、createTable()第三层查询执行AST 转执行计划、算子调度execute(Statement*)第四层记录管理记录增删改查、页内槽位管理insertRecord()、scan()第五层索引管理 缓冲池B 树索引、页缓存与磁盘 IOsearch(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::vectorToken tokenize(const std::string sql) { std::vectorToken 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::vectorValue 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::vectorValue 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::vectorValue 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建索引查id500、id BETWEEN 100 AND 200结果与全表扫描一致且走索引可打印计划验证删除与更新删中间若干行、更新若干行再查结果正确索引同步无脏 key事务回滚BEGIN后插入再ROLLBACK数据与索引均回到事务前状态异常输入输入残缺 SQL、未知表名打印错误位置程序不退出答辩技巧上别一上来讲架构图先跑演示让评委看到东西能动再回头讲分层。被问到「为什么不用 B 树用 B 树」答「范围查询走叶子链表内部节点不存数据同样页大小能存更多 key树更矮」。被问到「事务做到什么程度」如实说「语句级原子性隔离性和持久化做了简化」比硬吹完整 ACID 然后被追问穿帮强。代码量、测试用例数这些数字提前统计好写在 PPT 角落评委扫一眼就有底。从那以后我每次带这类课程设计都强制先写验收脚本再写实现脚本跑不通就不算完成这个习惯帮我省掉了无数次「演示前夜发现主流程断了」的慌乱。希望帮到你。本文还有配套的精品资源点击获取