简介本资源是浙江大学数据库设计课程期末大作业成果——miniSQL轻量级数据库管理系统面向数据库原理学习者、C/C系统编程初学者及课程实践者旨在通过完整可运行的DBMS实例深入理解SQL解析、事务处理、B树索引、缓冲区管理等核心机制。压缩包共29个文件含9个C源码文件如Interpreter.cpp、bptree.cpp、RecordManager.cpp、9个头文件API.h、Catalog.h等支撑模块化架构9个文本说明与测试用例1份详尽的PDF设计报告以及1个开箱即用的Windows可执行文件myMiniSQL.exe整体仅885KB轻量易部署。已有1529人下载学习适合结合课程理论开展源码级研读与功能验证。读者可直接运行exe体验基础SELECT/INSERT/UPDATE/DELETE操作对照PDF报告理解设计决策与ACID实现细节并通过源码快速定位索引管理、记录存储、查询解析等关键模块是贯通数据库理论与工程实践的优质教学案例。1. miniSQL 是什么不是玩具是浙大数据库课压轴实战的“最小可行数据库内核”如果你在浙江大学修《数据库系统》这门课期末大程交的不是 SQL 练习题而是一个能CREATE TABLE、INSERT、SELECT * FROM、甚至带WHERE条件和单表连接的命令行数据库——那它大概率就是miniSQL。这不是一个现成的开源项目封装而是课程要求你从零手写的核心模块解析器Parser、查询执行器Executor、数据存储层Storage外加一个极简但可交互的 CLI 前端。它不追求性能不兼容 MySQL 语法但必须能跑通「建表 → 插入 → 查询 → 条件过滤」这一闭环逻辑。很多同学第一眼觉得“就这”直到卡在词法分析状态机跳转错位、WHERE 子句 AST 构建漏节点、或磁盘页读写时字节对齐失败上——才明白真正把数据库原理从课本里拽出来、按字节钉进内存和磁盘的过程才是这门课最硬的验收点。适合谁刚学完关系代数、B树、日志恢复但还没碰过真实 DBMS 代码的本科生也适合想用最小代价验证自己是否真懂“一条 SELECT 怎么走完全流程”的自学者。它不替代 PostgreSQL但它能让你第一次亲手捏出数据库的骨架。2. 从零搭起 miniSQL 的四大核心模块为什么选这些结构而不是直接抄 SQLiteminiSQL 的本质是教学型内核不是生产环境替代品。这意味着它的架构必须满足三个硬约束可理解性 可扩展性模块边界清晰 代码行数最少调试友好 运行速度。我们不追求并发控制或事务隔离级别但必须让每个模块的输入输出能被肉眼验证。下面拆解四个必实现模块的选型逻辑与落地路径。2.1 词法分析器Lexer用确定有限自动机DFA手写拒绝正则黑盒很多同学一上来就想用re模块写 token 匹配结果在SELECT*FROM无空格和SELECT * FROM有空格上反复翻车。miniSQL 要求你显式定义状态转移比如S0初始态遇到字母跳到S1标识符开始遇到数字跳到S2数字字面量遇到*直接进入S3乘号/通配符终态。这样做的好处是当SELECT*FROM解析失败时你能直接打印当前状态和下一个字符定位是*后没识别出FROM还是状态机漏了*到S3的转移。# lexer.py手写 DFA 状态机简化版 class Lexer: def __init__(self, sql: str): self.sql sql.strip() self.pos 0 self.tokens [] def tokenize(self): while self.pos len(self.sql): ch self.sql[self.pos] if ch.isspace(): self.pos 1 continue elif ch.isalpha() or ch _: self._parse_identifier() # 进入 S1 状态处理 elif ch.isdigit(): self._parse_number() elif ch *: self.tokens.append((STAR, *)) self.pos 1 elif ch : # 检查是否为 或 if self.pos 1 len(self.sql) and self.sql[self.pos 1] : self.tokens.append((EQ, )) self.pos 2 else: self.tokens.append((ASSIGN, )) self.pos 1 # ... 其他符号处理 return self.tokens提示_parse_identifier()必须区分关键字如SELECT,FROM和普通标识符如user_name。常见做法是预置KEYWORDS {SELECT, FROM, WHERE, INSERT, INTO}在解析完连续字母后查表命中则生成(SELECT, SELECT)否则生成(IDENTIFIER, user_name)。这是后续语法分析能正确构建 AST 的前提。2.2 语法分析器Parser递归下降 手动错误恢复不依赖 PLY/Yacc浙大期末要求禁用第三方解析框架如 PLY强制手写递归下降分析器。原因很实在PLY 会帮你吞掉错误、自动跳过非法 token而课程要你直面“SELECT FROM users WHERE age 少了个值”这种场景——怎么报错位置、怎么提示用户补全、怎么让解析器不崩掉继续吃下后续语句递归下降的控制权完全在你手里。核心思路是每个非终结符对应一个函数如parse_select_stmt()负责识别SELECT ... FROM ... [WHERE ...]结构。函数内部按预测集Predictive Set匹配 token 序列# parser.py递归下降主干SELECT 语句 def parse_select_stmt(self): # 必须以 SELECT 开头 if not self.match(SELECT): raise ParseError(fExpected SELECT at position {self.pos}, self.pos) # 解析字段列表支持 * 或 字段名逗号分隔 fields self.parse_field_list() # 调用子函数 if not self.match(FROM): raise ParseError(Expected FROM after SELECT fields, self.pos) table_name self.consume(IDENTIFIER) # 获取表名 # WHERE 子句可选 where_clause None if self.match(WHERE): where_clause self.parse_where_clause() # 单条件如 age 25 return SelectStatement(fieldsfields, tabletable_name, wherewhere_clause)注意self.match(token_type)只检查下一个 token 类型是否匹配不消耗self.consume(token_type)才真正取走 token 并推进位置。这个细节能避免“匹配了WHERE却没取走导致后续解析卡死”的经典翻车。2.3 存储引擎Storage用文件模拟页式存储B树索引只做单层miniSQL 不需要实现 WAL 日志或缓冲区管理但必须体现“数据落盘”和“索引加速”。浙大参考实现普遍采用数据文件每张表一个.tbl文件按固定长度记录存储如user_id INT(4), name CHAR(20), age INT(4)→ 每条记录 32 字节索引文件.idx文件用内存 B 树Pythonsortedcontainers不允许必须手写维护主键到物理偏移的映射页管理不实现多级页表但需定义PAGE_SIZE 4096每次读写以页为单位模拟真实 DBMS 的 I/O 行为。关键落地点在于记录序列化与反序列化。例如INT字段必须用struct.pack(i, value)转为 4 字节小端整数读取时用struct.unpack(i, data[0:4])[0]。漏掉字节序或长度会导致所有数值错乱——这是调试阶段最玄学的 bug 来源之一。2.4 查询执行器ExecutorAST 驱动的管道式执行WHERE 下推到扫描层执行器不是简单遍历 AST 执行而是构建执行计划管道TableScanOperator从.tbl文件顺序读取记录FilterOperator接收上游记录根据WHERE条件如age 25计算布尔值只转发True记录ProjectOperator提取指定字段SELECT name, age最终由CLI层格式化输出。这种设计让“SELECT * FROM users WHERE age 25”的执行流清晰可见扫描 → 过滤 → 投影。更重要的是它天然支持优化比如当WHERE条件含主键等值查询WHERE id 100FilterOperator可触发索引查找跳过全表扫描——这就是你在 miniSQL 里第一次亲手实现的“查询优化”。3. 避坑指南浙大往届同学血泪总结的 5 个高频翻车点miniSQL 看似简单但每个模块的边界条件都藏着“不报错但结果错”的深坑。以下是近三届浙大学生提交作业时最高频、最耗时的 5 类问题按现象→原因→解决给出可立即验证的方案。3.1 现象SELECT * FROM users返回空结果但cat users.tbl明明有数据原因记录长度计算错误导致TableScanOperator读取越界。例如定义name CHAR(20)但实际存入Alice5 字节未补\0后续记录起始位置算错。解决严格按 schema 定义填充记录。写入时用name.ljust(20, \0)补齐读取后用.rstrip(\0)去除末尾\0。验证方法用hexdump -C users.tbl | head -n 5查看前几条记录的十六进制确认每条记录严格 32 字节假设 schema 总长 32。3.2 现象WHERE age 25返回所有记录包括age 20的原因FilterOperator中比较操作符解析错误。词法分析将识别为GTtoken但语法分析未将其与右操作数25正确绑定到BinaryExpr节点导致执行时age 25被当成age NonePython 中int None恒为False但某些实现误判为True。解决在parse_where_clause()中强制构建BinaryExpression(leftColumnRef(age), opGT, rightLiteral(25))。调试时打印 ASTprint(ast.dump(where_clause, indent2))确认op字段值为字符串GT且right是Literal而非None。3.3 现象插入中文姓名如张三后查询显示乱码或截断原因CHAR(N)按字节而非字符定义长度UTF-8 下一个汉字占 3 字节CHAR(20)实际只能存 6 个汉字2 字节余量。更糟的是struct.pack对字符串不做编码转换。解决统一用 UTF-8 编码。写入前name.encode(utf-8)不足 20 字节则ljust(20, b\0)读取后data[4:24].rstrip(b\0).decode(utf-8)。注意struct.pack只处理字节串不能直接 pack 字符串。3.4 现象多次INSERT后SELECT只返回最后一条原因.tbl文件以w模式打开每次插入覆盖整个文件而非追加。解决插入逻辑必须用open(users.tbl, ab)追加二进制写入。验证ls -l users.tbl查看文件大小是否随插入递增wc -c users.tbl确认字节数 记录数 × 每条记录字节数。3.5 现象SELECT name FROM users WHERE id 100极慢未走索引原因索引查找函数未正确实现“等值查询跳转”。B树搜索返回None但FilterOperator未捕获该情况降级为全表扫描。解决在Index.search(key)方法中若找到则返回offset未找到必须明确返回None不能抛异常。执行器中if where_expr and isinstance(where_expr, BinaryExpr) and where_expr.op EQ: idx_result index.search(where_expr.right.value) # 假设 right 是 Literal if idx_result is not None: record storage.read_record(idx_result) # 直接读单条 yield record return # 退出不走全表扫描提示浙大测试用例必含主键等值查询此坑不填性能分直接归零。4. 测试驱动开发TDD用 3 类测试用例覆盖 90% 的评分点浙大 miniSQL 评分标准隐含一条铁律能通过测试用例比代码多炫酷更重要。课程提供test_cases/目录但往届经验表明仅靠官方用例不够——必须自己补全边界测试。我们按优先级划分为三类每类给出可直接运行的验证脚本。4.1 基础语法测试确保 Parser 和 Executor 能跑通最小闭环目标CREATE TABLE users (id INT, name CHAR(20)); INSERT INTO users VALUES (1, Alice); SELECT * FROM users;全流程无异常输出含1|Alice。验证脚本test_basic.py#!/bin/bash # 将上述 SQL 写入 test.sql用 miniSQL 执行并检查输出 echo CREATE TABLE users (id INT, name CHAR(20)); test.sql echo INSERT INTO users VALUES (1, \Alice\); test.sql echo SELECT * FROM users; test.sql # 假设你的 CLI 入口是 main.py python main.py test.sql | grep -q 1|Alice echo ✅ 基础语法通过 || echo ❌ 基础语法失败关键点grep必须匹配1|Alice竖线分隔符而非Alice。因为浙大标准输出格式强制字段间用|分隔空格或逗号都不行。4.2 边界条件测试专打存储和类型转换的软肋目标验证CHAR补零、INT溢出、空值处理。用例CREATE TABLE t (a INT, b CHAR(5)); INSERT INTO t VALUES (2147483647, Hi); -- INT 最大值 INSERT INTO t VALUES (-2147483648, Bye); -- INT 最小值 INSERT INTO t VALUES (0, ); -- 空字符串 SELECT * FROM t WHERE a 2147483647;预期三条插入成功最后SELECT返回第一行。验证逻辑检查t.tbl文件大小是否为3 × 记录长度用od -An -ti4 t.tbl查看 INT 字段是否为2147483647和-2147483648注意小端存储od默认大端需加-tx4查十六进制再换算。4.3 错误恢复测试证明你的 Parser 不是纸糊的目标输入非法 SQL 时不崩溃、不静默跳过、报错位置精准。用例SELECT * FROM users WHERE age ; -- 少右操作数 CREAT TABLE users (id INT); -- 关键字拼错预期第一行报错Error at line 1, column 28: Expected expression after 第二行报错Error at line 2: Unexpected token CREAT。验证方法重定向 stderr 到文件python main.py error.sql 2 err.log用grep -E line [0-9], column [0-9] err.log | wc -l检查是否输出 2 行带位置信息的错误。提示浙大自动评测脚本会检查 stderr 输出格式。若你只打印Syntax Error!分数清零。必须包含line X, column Y且X是行号\n计数Y是该行内字符偏移从 0 开始。5. 性能与健壮性进阶给你的 miniSQL 加上“生产级”肌肉做到上面四章你已稳过及格线。但想拿高分、甚至被助教推荐为范例必须在两个方向做出可验证的提升索引效率量化和错误注入下的稳定性。这不是炫技而是证明你真正理解了数据库内核的权衡。5.1 用真实数据集压测索引收益从 10s 到 0.02s 的直观说服力浙大不考理论复杂度但要求你用数据说话。准备一个10000行的users表脚本生成# gen_data.py import random names [Alice, Bob, Charlie, Diana] * 2500 with open(users.tbl, wb) as f: for i in range(10000): # id: int, name: char(20), age: int name_bytes names[i % len(names)].encode(utf-8).ljust(20, b\0) record struct.pack(i20si, i, name_bytes, random.randint(18, 80)) f.write(record)然后对比两种查询无索引SELECT * FROM users WHERE id 9999;全表扫描有索引同上但走 B树主键查找用time python main.py -e SELECT * FROM users WHERE id 9999;记录耗时。理想结果无索引 ≥ 8s10000×32B 顺序读有索引 ≤ 0.02sB树深度≤33次磁盘I/O。如果差距不到 100 倍说明索引未生效或 B树实现有缺陷——回看 3.5 节。5.2 主动注入故障证明你的 Storage 层能扛住磁盘写一半就断电真实数据库怕的不是慢是数据损坏。miniSQL 虽小但可模拟“写入中途崩溃”。方法在storage.write_record()中随机os._exit(1)# storage.py - 仅用于演示提交前删除 import os, random def write_record(self, record: bytes): if random.random() 0.001: # 0.1% 概率模拟崩溃 os._exit(1) # 立即终止不走任何清理 # 正常写入逻辑...然后跑INSERT循环for i in {1..100}; do echo INSERT INTO users VALUES ($i, \Test$i\);; done | python main.py观察崩溃后重启SELECT COUNT(*) FROM users是否仍返回准确行数若出现重复或丢失说明你没实现原子写入如先写日志再写数据。解决方案引入简易 WAL每次INSERT前先write_log(INSERT users ($i, Test$i))崩溃后启动时重放日志。5.3 一个值得坚持的工程习惯为每个模块写--debug开关浙大助教阅卷时最欣赏的不是代码多短而是调试信息是否精准可控。我在每个模块加了--debug-parser、--debug-storage开关python main.py --debug-parser -e SELECT * FROM users WHERE age 25输出[PARSER] Token stream: [(SELECT, SELECT), (STAR, *), (FROM, FROM), (IDENTIFIER, users), (WHERE, WHERE), (IDENTIFIER, age), (GT, ), (NUMBER, 25)] [PARSER] AST: SelectStatement(fields[*], tableusers, whereBinaryExpr(opGT, leftColumnRef(age), rightLiteral(25))) [STORAGE] TableScan: reading 10000 records from users.tbl [FILTER] Applying condition: age 25 → 4231 records passed这比print()强十倍开关可控、模块隔离、信息结构化。助教一眼看到你理解了数据流向分数自然上浮。希望帮到你。本文还有配套的精品资源点击获取