简介这份资源是浙江大学数据库设计课程的期末大程成果——miniSQL迷你数据库系统面向正在学习数据库原理、希望动手理解SQL底层实现的高校学生与开发者。压缩包共29个文件约885KB以C/C源码为主体包含9个cpp与9个h文件覆盖缓冲管理、记录管理、索引管理、B树、目录与解释器等核心模块另附可执行文件、测试文件、说明文档及一份PDF设计报告可直接运行或自行编译研究。目前已有1532人学习下载。读者可从中获得一套完整的数据库引擎实现范例通过源码理解SELECT、INSERT、UPDATE、DELETE及JOIN等语句的解析与执行路径结合设计报告梳理关系模型、ACID属性、查询优化与索引结构如何落地为工程代码并借助测试用例验证系统在并发场景下的正确性与稳定性适合作为课程设计参考与数据库内核入门实践材料。1. 从一道“写不出执行计划”的期末题说起这门课到底考什么数据库期末大程很多人第一反应是“建几张表、写几条 SQL 就完事”。真到验收现场导师随口一句“这条查询走的是全表扫描还是索引”当场卡壳的不在少数。这门课的考核重心从来不是 SQL 语法背得熟不熟而是你能不能把一个 miniSQL 从词法、语法、执行到存储这条链路讲清楚能不能在 C/C 层面把 B 树索引、缓冲池、连接算法这些模块落地。分值分布上功能实现占大头但答辩追问和设计文档往往决定你是及格还是优秀。适合已经写过增删改查、但对“数据库内部怎么跑起来”还停留在黑匣子认知的备考者。下面按考点模块拆开讲每一块都配真题和答题思路照着练就能对上验收老师的胃口。2. 高频考点miniSQL 四大模块的分值分布与必答清单2.1 词法与语法分析手写递归下降是主流路线这类题通常这么考给一段带嵌套条件的 SQL问你解析后生成什么样的语法树或者让你指出递归下降解析器在哪个函数里处理WHERE子句。miniSQL 的解析层一般分两步走词法分析把字符流切成 token语法分析按文法规则递归下降构造 AST。C/C 实现里常见做法是手写 lexer 配合一个Parser类每个非终结符对应一个成员函数。// 词法分析核心从字符流中切出 token跳过空白 Token Lexer::nextToken() { while (pos input.size() isspace(input[pos])) pos; // 跳过空白字符 if (pos input.size()) return {TokenType::END, }; char c input[pos]; if (isalpha(c)) { // 标识符或关键字 size_t start pos; while (pos input.size() isalnum(input[pos])) pos; return {TokenType::IDENT, input.substr(start, pos - start)}; } if (isdigit(c)) { // 数字字面量 size_t start pos; while (pos input.size() isdigit(input[pos])) pos; return {TokenType::NUMBER, input.substr(start, pos - start)}; } pos; return {TokenType::SYMBOL, std::string(1, c)}; // 单字符符号如 }这段代码的关键在于pos的推进必须严格单调任何回退都会让后续 token 错位。参数上input是整条 SQL 字符串TokenType枚举至少要覆盖 IDENT、NUMBER、SYMBOL、END 四类。失败时最先看的是pos有没有在异常分支里被多推一格这是血泪经验里最常见的翻车点。面试官最想听的是你能说清“为什么手写而不是用工具生成”答案落在可控性和调试成本上而不是背概念。真题演练请描述SELECT * FROM t WHERE a 1 AND b 2的解析过程。答题思路分三层先说词法阶段切出 SELECT、星号、FROM、表名、WHERE、列名、比较符、数字这些 token再说语法阶段parseSelect调用parseWhereparseWhere用循环处理 AND 连接的条件项每个条件项调用parseCondition生成比较节点最后说 AST 根节点是 SelectStmt其 where 字段是一棵左深的 AND 树。这样答既展示了流程又暴露了你对数据结构的理解。2.2 存储与索引B 树的扇出和分裂是追问重灾区存储层考什么考的是你知不知道页page是磁盘 IO 的基本单位以及 B 树为什么适合做索引。miniSQL 里通常固定页大小比如 4KB内部节点只存 key 和子页指针叶子节点存 key 和记录指针叶子之间用链表串起来支持范围扫描。扇出fanout的计算是高频追问一个内部节点能挂多少子指针取决于(页大小 - 节点头) / (key 大小 指针大小)。// B 树节点分裂的简化逻辑叶子节点满时一分为二 void BPlusNode::split(BPlusNode* newNode) { int mid keys.size() / 2; // 从中间切开 newNode new BPlusNode(isLeaf); // 新节点继承叶子属性 newNode-keys.assign(keys.begin() mid, keys.end()); // 后半段 key 搬走 keys.erase(keys.begin() mid, keys.end()); // 原节点保留前半段 if (isLeaf) { // 叶子节点要维护链表 newNode-next next; next newNode; } }mid取中点保证两边负载均衡isLeaf决定新节点是否要接叶子链表next指针的更新顺序不能反先接新节点再改原节点否则链会断。这类题面试官最爱追问“分裂后父节点的 key 怎么更新”你要答出把新节点的最小 key 上推到父节点父节点满了继续递归分裂直到根节点分裂时树高加一。易错的地方是叶子分裂和内部节点分裂的 key 处理规则不同内部节点的中间 key 是上推而不是保留这一点答错直接暴露没动手写过。真题演练给定页大小 4096 字节key 为 8 字节整数指针 4 字节节点头 24 字节求内部节点扇出。答题思路是先算可用空间 4096 减 24 得 4072每个槽位占 key 加指针 12 字节4072 除以 12 向下取整得 339所以扇出约 339。答完补一句“实际实现会留一点余量防止溢出”显得你有工程意识。2.3 查询执行连接算法选错整个验收节奏就乱了执行层的高频考点是连接算法和谓词下推。miniSQL 规模小通常实现嵌套循环连接Nested Loop Join就够但答辩时老师会问“如果有索引能不能更快”你要能说出索引嵌套循环连接Index Nested Loop Join的思路外表每取一行用连接键去内表索引上查把内层全表扫描换成索引查找。谓词下推则是把 WHERE 条件下推到扫描层减少中间结果集。// 嵌套循环连接外表每一行都扫一遍内表 for (auto outerRow : outerTable-scan()) { // 外层逐行 for (auto innerRow : innerTable-scan()) { // 内层全扫 if (match(outerRow, innerRow, joinKey)) { // 连接条件判断 result.push_back(merge(outerRow, innerRow)); // 拼接输出 } } }match负责比较连接键merge把两行拼成结果行。复杂度是外层行数乘内层行数数据量一大就慢所以答题时要主动提“如果内表连接键上有 B 树索引内层可以改成索引查找复杂度降到外层行数乘树高”。面试官最想听的是你对代价的敏感度而不是背出算法名字。踩坑最多的是把连接条件和过滤条件混在一起下推连接条件不能下推到单表扫描否则语义就错了。真题演练两张表各 1000 行无索引嵌套循环连接要做多少次比较。答题思路是直接答 1000 乘 1000 等于一百万次然后补一句“若内表建索引比较次数降到约 1000 乘 log 量级”把优化空间也带出来。3. 真题演练从建表到事务五类必刷题的答题模板3.1 建表与约束主键、外键、唯一索引怎么答才不漏分建表题看着简单失分往往在约束的完整性上。答题模板分四步先写列定义和类型再标主键再标外键并说明引用关系最后补唯一约束和默认值。C/C 实现层面建表语句解析后要落成表元数据schema包括列名、类型、是否主键、外键指向哪张表的哪一列。CREATE TABLE student ( id INT PRIMARY KEY, -- 主键唯一且非空 name VARCHAR(32) NOT NULL, -- 非空约束 dept_id INT, FOREIGN KEY (dept_id) REFERENCES dept(id) -- 外键引用 );答题时要说清主键在存储层通常对应一棵 B 树索引外键约束在插入时要做引用检查。老师追问“外键检查放在哪一层”答在执行器的插入算子之前做查被引用表的主键索引是否存在对应值。易错点是只写约束不解释实现位置显得只会背语法。3.2 索引设计与最左前缀一道题考出你有没有真用过给一条多列查询问你怎么建索引是高频题。答题思路先看 WHERE 里等值条件和范围条件的顺序等值在前范围在后遵循最左前缀原则。比如WHERE a 1 AND b 2建(a, b)联合索引比(b, a)更有效因为 a 等值定位后 b 可以直接范围扫。真题演练查询SELECT * FROM orders WHERE customer_id 10 AND amount 100怎么建索引。答题思路是建(customer_id, amount)联合索引解释 customer_id 等值匹配走索引定位amount 在其后做范围过滤避免回表前扫太多行。补一句“如果 select 的列都在索引里还能覆盖索引”把加分点带上。3.3 事务与并发ACID 在 miniSQL 里怎么落地事务题考的是你对 ACID 四个特性的实现映射。原子性靠日志undo log持久性靠重做日志redo log刷盘隔离性靠锁或 MVCC一致性是前几者共同保证的结果。miniSQL 规模下常见做法是简化版的两阶段锁或者干脆只讲清原理。答题模板先点出四个特性再逐个映射到模块最后说清本项目的取舍。比如“本项目实现了简化的事务管理原子性通过操作前记录 undo 信息实现隔离级别默认读已提交”。面试官最想听的是你知道取舍在哪而不是假装什么都实现了。翻车点是把一致性说成单独模块其实它是结果不是手段。3.4 易错点五个验收现场最常见的失分动作错在哪一把 B 树和 B 树混为一谈。为什么错B 树内部节点也存数据B 树数据全在叶子且叶子有链表范围查询效率差一个量级。怎么答对开口先点“数据只在叶子、叶子成链、内部节点只做导航”这三条。错在哪二索引越多越好。为什么错每个索引都是一棵额外的 B 树插入更新要维护多棵树写放大明显。怎么答对说清“读多写少才多加索引写密集场景要克制”。错在哪三连接条件当过滤条件下推。为什么错连接条件涉及两张表下推到单表扫描会改变语义。怎么答对明确“单表谓词可下推连接谓词留在连接算子”。错在哪四事务隔离级别答成实现细节。为什么错隔离级别是语义约定锁和 MVCC 是实现手段混答显得概念不清。怎么答对先答级别定义再答实现方式。错在哪五页大小和扇出计算不写单位。为什么错字节和 KB 混用导致数量级错。怎么答对计算时统一成字节最后再换算。3.5 设计文档与答辩怎么把代码讲成设计答辩不是复述代码是讲决策。答题结构用“问题、方案、取舍、验证”四段式。比如讲索引模块问题是范围查询慢方案是 B 树叶子链表取舍是牺牲少量写性能换范围扫描验证是给出扫描 N 行的 IO 次数对比。老师追问“为什么不用哈希索引”答哈希不支持范围查询等值查询快但范围场景直接失效。这类题通常这么答就能稳住节奏别一上来就贴代码。4. 答题技巧把验收追问变成你的加分环节验收现场最怕的不是不会是答得散。我的习惯是每道题先给结论再给理由最后补一句边界条件。比如问“B 树分裂后父节点怎么处理”先答“把新节点最小 key 上推”再答“父节点满则递归分裂”最后补“根分裂时树高加一”。这个三段式能覆盖绝大多数追问。再一个技巧是主动暴露取舍老师问“你的连接算法为什么选嵌套循环”别硬说它最好答“数据量小、实现简单若内表有索引可换索引连接”反而显得你想过。押题方向上词法语法、B 树扇出与分裂、连接算法代价、事务 ACID 映射这四块几乎必问建表和索引设计是送分题但别轻敌。练习时拿一张纸把每个模块的“是什么、怎么做、为什么这么选、失败看什么”四问写一遍写不出来的就是你的盲区。从那以后我每次准备这类答辩都强制走一遍这四问卡壳的地方就是第二天要补的地方。希望帮到你。本文还有配套的精品资源点击获取
)
