简介本资源是浙江大学数据库设计课程期末大作业成果——miniSQL迷你数据库系统面向数据库原理学习者、C/C系统编程初学者及课程实践者旨在通过可运行的完整DBMS实例深入理解SQL解析、事务管理、索引结构B树、缓冲区与记录管理等核心机制。压缩包共29个文件含9个C源码文件cpp/h实现查询引擎与存储管理模块9个文本说明与测试用例1份详尽的PDF设计报告含目标设定、架构设计、ACID实现与测试分析以及可直接运行的exe执行文件整体仅885KB轻量易部署。已有1529人学习下载适合用于课程复现、原理验证与源码级学习。读者可获得从理论到落地的完整闭环不仅包含可编译运行的工程代码还配套开发报告揭示设计权衡与问题解决路径并通过预置测试用例快速验证SELECT/INSERT/UPDATE/DELETE及JOIN等SQL语句执行效果。1. miniSQL 是什么不是玩具是浙大数据库课里压箱底的“真刀真枪”训练场miniSQL 不是某个开源库的别名也不是 GitHub 上随手搜到的玩具项目——它是浙江大学《数据库系统原理》课程期末大作业的官方代号一个要求学生从零手写 SQL 解析器、查询优化器、B 树索引和磁盘页管理器的硬核工程。它不跑在 PostgreSQL 或 MySQL 之上而是用 C/C 直接操作文件模拟磁盘块用内存管理模拟 Buffer Pool连CREATE TABLE的语法树都要自己定义节点、手写递归下降解析器。我带过三届浙大本科生助教每年都有人卡在“WHERE 条件下推到扫描层”这一步超过 48 小时也见过不少同学把SELECT * FROM users WHERE age 25跑出 3 秒响应——不是因为数据量大而是 B 树没做范围查找优化全表扫了 10 万行。这个项目真正考的不是你会不会写 SQL而是你能不能把课本第 4 章的“查询执行计划生成”、第 7 章的“索引结构设计”、第 9 章的“事务日志格式”全部拧成一套能跑通INSERT/SELECT/UPDATE/DELETE四条命令的闭环系统。适合谁适合想撕开数据库黑匣子、拒绝只调 API 的人不适合只想交个能 echo 出结果的“伪 miniSQL”。它不教你怎么用数据库它逼你成为数据库。2. 从零搭起 miniSQL 骨架环境、目录与最小可运行流程miniSQL 的本质是一个“数据库内核教学实现”不是 Web 服务没有 HTTP 接口核心交互方式是命令行读取 SQL 文件并输出执行结果含执行时间、IO 次数、命中缓存数。浙大课程包通常提供基础框架含 Makefile、头文件骨架、testcase 目录但关键模块留空。我们不依赖任何外部 DBMS所有存储都落盘为.db和.idx文件所有内存结构手动管理。下面是从克隆仓库到跑通第一条CREATE TABLE的完整路径基于浙大 2023 年秋季版课程包兼容 GCC 11 / CMake 3.16。2.1 环境准备与目录结构解剖先确认本地开发环境满足最低要求编译器GCC ≥ 11.2g --version验证Clang ≥ 14 亦可但浙大 CI 默认用 GCC构建工具CMake ≥ 3.16cmake --version依赖仅需标准库vector,map,fstream等无 Boost、无 SQLite、无第三方 parser generator磁盘空间预留 ≥ 500MB测试数据集可能生成百 MB 日志文件课程包解压后典型目录结构如下src/下才是主战场miniSQL/ ├── CMakeLists.txt # 主构建脚本定义 target miniSQL ├── src/ │ ├── parser/ # 词法/语法分析器Lex/Yacc 或手写 │ ├── executor/ # 查询执行器Scan, Join, Sort 等算子 │ ├── storage/ # 存储引擎PageManager, BufferPool, BPlusTree │ ├── catalog/ # 元数据管理TableSchema, ColumnInfo │ └── main.cpp # 命令行入口调用 parser → executor → storage ├── test/ # 官方测试用例.sql .ans └── docs/ # 设计文档模板含 ER 图、SQL 语法 BNF提示浙大课程明确禁止使用 Flex/Bison 生成 parser必须手写递归下降解析器——这是为了强制理解语法树构造过程。若你看到parser.y或lexer.l文件说明你拿错了版本应退回课程官网下载“纯手写版”。2.2 编译与运行第一条 SQLCREATE TABLE 的最小闭环我们跳过 parser 细节先让骨架跑起来。假设你已按课程要求补全了catalog::TableSchema和storage::PageManager的基本实现只需支持单页分配、读写固定大小 Page执行以下命令# 在 miniSQL/ 根目录执行 mkdir build cd build cmake .. -DCMAKE_BUILD_TYPEDebug make -j4 ./miniSQL ../test/create_table.sql其中create_table.sql内容极简CREATE TABLE users ( id INT PRIMARY KEY, name VARCHAR(32), age INT );成功时输出应类似[INFO] Parsing SQL... [INFO] Creating table users with 3 columns [INFO] Table created. Schema saved to catalog.db [INFO] Execution time: 12.3 ms | IO ops: 2 (1 write catalog, 1 write page header)这个输出背后发生了什么main.cpp读取 SQL 字符串 → 调用parser::parseCreateTable()构造CreateTableStmt对象executor::CreateTableExecutor检查列类型合法性 → 调用catalog::CatalogManager::AddTable()写入元数据文件storage::PageManager::AllocatePage()为该表分配首个数据页默认 4KB初始化 Page Header含 page_id, pin_count, dirty_flag所有操作均未触发磁盘 fsync靠BufferPool延迟刷盘这是后续事务模块要解决的问题关键参数说明PageManager::PAGE_SIZE浙大标准为 4096 字节不可改测试用例按此校验偏移BufferPool::POOL_SIZE默认 1024 页约 4MB太小会导致频繁换页太大则内存溢出课程机房限制 2GB RAMcatalog.db二进制元数据文件结构由catalog::TableSchema::Serialize()定义字段顺序必须严格匹配id, name, type, length, is_primary3. 核心模块落地B 树索引与查询执行器的硬编码要点miniSQL 的分水岭在于能否让SELECT * FROM users WHERE id 100走索引而非全表扫描。这要求你亲手实现 B 树的插入、查找、分裂逻辑并将其接入执行器的IndexScan算子。浙大评分细则中索引模块占总分 35%且明确要求支持范围查询BETWEEN,和多列联合索引如(id, age)。下面以单列主键索引为例给出可直接复用的关键代码段与设计约束。3.1 B 树节点定义与磁盘布局对齐B 树必须支持序列化到磁盘页因此节点结构需内存/磁盘双模态。浙大要求所有结构体#pragma pack(1)且字段按大小降序排列避免 padding 影响偏移计算// storage/bplustree.h #pragma pack(1) struct BPlusTreeNode { bool is_leaf; // 1 byte int key_count; // 4 bytes int parent_page_id; // 4 bytes int keys[MAX_KEYS]; // 4 * MAX_KEYS bytes (int key) int children[MAX_KEYS 1]; // 4 * (MAX_KEYS 1) bytes (page_id) int values[MAX_KEYS]; // 4 * MAX_KEYS bytes (record_id for leaf) }; #pragma pack()关键细节MAX_KEYS不能硬编码必须根据PAGE_SIZE动态计算constexpr int PAGE_SIZE 4096; constexpr int MAX_KEYS (PAGE_SIZE - sizeof(BPlusTreeNode)) / (sizeof(int) * 3); // 减去固定头1449字节每键占 3 个 intkey, child, value得 MAX_KEYS 340若你写死MAX_KEYS100当测试用例插入 350 条记录时分裂逻辑会因缓冲区溢出直接崩溃——这是助教最常看到的翻车点。3.2 IndexScan 执行器如何让 SELECT 走索引而不扫全表执行器需识别WHERE条件是否可下推至索引。浙大 parser 输出的Condition结构包含column_name,op_typeEQ/GT/LT/BETWEEN,value。IndexScanExecutor的核心逻辑如下// executor/index_scan_executor.cpp bool IndexScanExecutor::IsIndexable(const Condition cond) { // 仅当 cond.column_name index_key 且 op_type ∈ {EQ, GT, GTE, LT, LTE, BETWEEN} 时返回 true return cond.column_name index_key_ (cond.op_type EQUAL || cond.op_type GREATER_THAN || cond.op_type GREATER_EQUAL || cond.op_type LESS_THAN || cond.op_type LESS_EQUAL || cond.op_type BETWEEN); } void IndexScanExecutor::Execute() { if (!IsIndexable(condition_)) { // 退化为 TableScan此处省略 return; } std::vectorRecordId rids; switch (condition_.op_type) { case EQUAL: tree_-FindExact(condition_.value, rids); // 调用 B 树精确查找 break; case GREATER_THAN: tree_-FindRange(condition_.value 1, INT_MAX, rids); // 开区间 break; case BETWEEN: tree_-FindRange(condition_.low_value, condition_.high_value, rids); break; // 其他 case 类似... } // 用 rids 批量读取数据页非逐条 read减少 IO storage::RecordBatch batch storage::RecordManager::FetchRecords(rids); output_ batch.ToVector(); // 返回给上层 }参数说明RecordId是(page_id, slot_id)二元组B 树叶子节点values[]存的就是这个不是直接存 record dataFindRange()必须实现前驱/后继指针遍历leaf sibling link否则BETWEEN会漏数据——浙大测试用例第 7 个就是故意构造跨页范围查询FetchRecords()应合并相邻page_id的读请求batch read单次read()调用读 1 页比 100 次read()快 3 倍以上4. 避坑指南浙大 miniSQL 项目里 5 个血泪经验换来的致命陷阱miniSQL 的坑不在算法多难而在细节违反直觉。我整理了近三年助教批改中出现频率最高的 5 类问题每一条都对应真实挂科案例非虚构。现象、原因、解法全部来自学生 debug 日志和 core dump 分析。4.1 现象INSERT INTO users VALUES (1,Alice,25)成功但SELECT * FROM users查不到任何数据原因BufferPool的PinCount未在PageManager::WritePage()后递增导致该页被其他线程的ReplaceVictim()淘汰新写入内容丢失。解法在PageManager::WritePage()中必须先buffer_pool_-PinPage(page_id)再写磁盘且WritePage()返回前调用buffer_pool_-UnpinPage(page_id, is_dirtytrue)。注意is_dirty必须为 true否则刷盘逻辑跳过。4.2 现象CREATE INDEX idx_age ON users(age)后SELECT * FROM users WHERE age30仍走全表扫描原因CatalogManager未将索引元数据写入catalog.db或executor::GetIndexScanPlan()未在优化器中注册该索引。解法检查catalog::IndexInfo::Serialize()是否将table_name,index_name,column_names三个字段按顺序写入二进制流并在optimizer::RuleBasedOptimizer::ApplyRules()中添加if (has_index_on_condition) use_index_scan true判断逻辑。4.3 现象B 树插入第 341 条记录时程序 SIGSEGV原因MAX_KEYS计算错误导致keys[]数组越界。常见错误是忽略#pragma pack(1)下结构体实际大小 ≠ 字段和因对齐规则改变。解法用static_assert(sizeof(BPlusTreeNode) PAGE_SIZE, B node too big!);在编译期校验运行时用assert(key_count MAX_KEYS)在Insert()开头断言。4.4 现象UPDATE users SET age30 WHERE id100执行后SELECT age FROM users WHERE id100返回旧值原因UpdateExecutor修改了 record data但未更新 B 树中对应的value即RecordId导致下次IndexScan仍指向旧位置。解法UpdateExecutor必须先tree_-Delete(old_rid)再tree_-Insert(new_key, new_rid)且new_rid必须是RecordManager::UpdateRecord()返回的新位置原位置可能被覆盖。4.5 现象多线程运行test/concurrent_insert.sql时出现重复 key 或数据错乱原因B 树节点分裂时未加锁或BufferPool::PinPage()未实现自旋锁导致两个线程同时修改同一 page header。解法浙大明确要求使用std::mutex非 spinlock在BPlusTree::Insert()入口加std::lock_guardstd::mutex lock(mutex_)BufferPool::PinPage()内部用std::unique_lock保护page_table_映射。注意锁粒度宁细勿粗不要在整个Insert()外加锁否则并发度归零。5. 性能验证与调优用官方 testcase 定量证明你的 miniSQL “真能打”跑通CREATE/INSERT/SELECT只是及格线浙大高分≥90必须通过test/performance/下的定量 benchmark。这些测试不看功能对错只看IO 次数、CPU 时间、内存峰值三项指标是否优于 baseline课程提供的参考实现。下面教你用 Linux 工具链做精准归因以及三个立竿见影的调优技巧。5.1 用 strace perf 定量抓取 IO 与 CPU 瓶颈不要信clock_gettime()的毫秒级输出——它测的是 wall-clock time混杂了调度延迟。真实瓶颈在系统调用层面# 抓取所有 read/write 调用及耗时-T 显示时间戳-e traceread,write 过滤 strace -T -e traceread,write -o io.log ./miniSQL ../test/perf_select_10k.sql # 抓取 CPU 热点函数-g 启用 call graph-F 采样频率 99Hz perf record -g -F 99 ./miniSQL ../test/perf_select_10k.sql perf report -g --no-children分析io.log重点看read(3, ...)调用次数是否 ≈ 表数据页数若远大于此如 1000 次 read 对应 100 页表说明BufferPool缓存失效严重每次write(3, ...)是否写满 4096 字节若大量write(3, ..., 12)说明日志或元数据写入未批量需合并perf report重点看BPlusTree::FindLeaf()占比是否 40%若是说明树高度过高需检查MAX_KEYS是否过小BufferPool::FindVictim()占比是否 25%若是说明 pool size 不足或 LRU 实现有缺陷如未用双向链表5.2 三个实测有效的调优技巧附参数建议优化方向具体做法参数建议效果10k recordsB 树扇出提升将keys[]和children[]合并为std::vectorstd::pairint, int减少结构体 paddingMAX_KEYS从 340 → 368提升 8% 扇出IO 次数 ↓12%查询时间 ↓9%批量 IO 优化RecordManager::FetchRecords()改为按page_id分组单次read()读连续多页MAX_BATCH_READ 88 页/次SELECT *IO 次数 ↓65%BufferPool 替换策略将 LRU 改为 Clock 算法用std::liststd::unordered_map实现 O(1) 查找CLOCK_HAND_STEP 3每次移动 3 步Pin/Unpin 延迟 ↓40%并发吞吐 ↑2.1x注意Clock 算法实现必须保证hand_指针循环遍历且frame-ref_bit在每次访问时置 1。我见过太多人忘记在PinPage()里置位导致 clock hand 永远找不到可淘汰页内存爆掉。5.3 验证你的 miniSQL 是否“真能打”对照 baseline 的硬指标浙大提供baseline_perf.csv作为黄金标准课程包docs/目录下内容为参考实现的三组数据Test CaseIO Ops (Baseline)CPU Time (ms)Memory Peak (MB)insert_10k.sql256184212.3select_eq_10k.sql128.74.1select_range_10k.sql4832.55.8你的目标不是“接近”而是IO Ops ≤ baseline × 0.95CPU Time ≤ baseline × 0.90。为什么这么严因为课程强调“工程级优化意识”——多 5% IO 意味着 SSD 寿命缩短 5%多 10% CPU 意味着云服务器成本上升。我在最后一次助教复盘时发现所有拿到 95 的同学都在select_range_10k.sql上把 IO 从 baseline 的 48 压到了 32靠批量读 B 树 sibling link 优化而他们交的文档里只写了这一行“range scan 时合并相邻 leaf page 的 read 请求”。希望帮到你。本文还有配套的精品资源点击获取