简介本资源为CMU-15445数据库系统课程Bustub项目的个人实现源码面向正在学习数据库系统原理、希望深入理解DBMS内部机制的高校学生与开发者。项目围绕存储管理、查询优化、事务处理等核心议题展开通过完整编码实践将课程理论转化为可运行的数据库系统适合作为课程作业参考或简历项目展示。压缩包共1195个文件约33.89MB以C头文件与源文件为主体辅以Python测试脚本、Shell自动化脚本、HTML/JS/CSS前端资源及Bazel、CMake构建配置另含Docker部署文件与Git版本控制配置目录结构清晰便于按模块研读。目前已有162人学习关注。读者可从中获取数据库系统从存储层到执行层的完整实现思路、构建与测试流程以及代码风格统一、容器化部署等工程化实践参考对提升系统设计与C编程能力具有实际帮助。1. 从零手写 Bustub为什么数据库内核课值得你花三个月啃下来很多人第一次听到「基于 CMU-15445 课程的 Bustub 数据库系统个人实现」时第一反应是——这不就是跟着课程写作业吗但真正动手做过一轮的人会告诉你Bustub 是一个从磁盘管理器、缓冲池、B 树索引、查询执行器一路搭到并发控制与日志恢复的完整教学级数据库内核。它不像造一个玩具 SQL 解析器那样两三天收工而是逼你把「一条 SQL 从解析到落盘」的整条链路亲手接起来。适合谁适合已经会写 CRUD、但对「为什么加了索引就快了」「事务隔离级别到底怎么实现的」只有模糊印象的后端工程师也适合想补系统编程功底的学生。这篇笔记不讲课程大纲只讲我踩过的实现路径、参数取舍和那些文档里不会写的坑。2. 动手前先把 Bustub 的骨架拆清楚四个子系统与依赖顺序在写第一行代码之前如果没搞清楚 Bustub 各模块之间的依赖关系后面一定会返工。我见过太多人一上来就冲 B 树结果发现页面的生命周期管理还没做对索引写完了也跑不通。2.1 磁盘管理器、缓冲池、索引、执行器的调用链Bustub 的存储层从下往上大致是这么一条链DiskManager负责按页读写磁盘文件BufferPoolManager在内存里缓存这些页并管理淘汰上层是Page和TablePage这样的页面结构再往上是TableHeap提供元组级的插入删除索引层BPlusTree建立在页面之上执行器层Executor通过Catalog拿到表和索引的句柄来干活。这条链的关键在于每一层都假设下层已经正确。缓冲池的FetchPage如果没处理好 pin countB 树的节点分裂时就会把还在用的页淘汰掉表现为随机崩溃或者数据静默丢失。所以我的建议是严格按 Project 1 到 Project 4 的顺序推进不要跳。2.2 每个 Project 的验收标准与自测方法课程本身给了本地测试用例但那些用例覆盖不到边界。我一般会自己补三类测试第一类是空操作测试比如对空表建索引、对不存在的键做删除看会不会段错误。第二类是压力测试用脚本生成几万条随机键值对反复插入删除最后全量扫描验证一致性。第三类是并发测试开多个线程同时读写同一张表跑完之后检查有没有丢更新。# 编译并跑单个测试的常见做法 mkdir -p build cd build cmake -DCMAKE_BUILD_TYPEDebug .. make -j$(nproc) # 只跑缓冲池相关测试方便定位 ./test/buffer_pool_manager_test这里-DCMAKE_BUILD_TYPEDebug很关键Release 模式下很多断言会被优化掉你看到的崩溃位置会偏移排查成本翻倍。-j$(nproc)是并行编译Bustub 模板很重单线程编译能等到你怀疑人生。2.3 用 CMake 组织个人实现目录结构与编译开关我自己的做法是在官方骨架基础上加一个my_impl目录把每个 Project 的实现文件单独放方便回滚和对比。CMake 里加一个开关option(ENABLE_MY_DEBUG Enable extra debug logging OFF) if(ENABLE_MY_DEBUG) target_compile_definitions(bustub PRIVATE MY_DEBUG1) endif()这样调试日志可以用#ifdef MY_DEBUG包起来提交前关掉不会污染性能测试结果。参数上MY_DEBUG打开后缓冲池的每次 Fetch/Unpin 都会打印页号虽然慢但定位 pin 泄漏非常有效。3. 缓冲池与 B 树两个最容易被低估的实现难点这两个模块是 Bustub 的分水岭。缓冲池写不对后面全是玄学 bugB 树写不对查询结果时对时错。下面拆开讲。3.1 LRU-K 淘汰器的三个必调参数Bustub 要求实现 LRU-K 淘汰策略核心是记录每个页最近 K 次访问的时间戳。我踩过的坑集中在三个参数上参数含义我的取值说明K历史访问次数2K1 退化成 LRUK 太大内存开销高淘汰阈值可淘汰的最小访问次数K访问次数不足 K 的页优先淘汰时间戳精度记录访问顺序单调递增计数器不要用系统时钟并发下会乱序K2 是课程默认也是实践中最平衡的K1 在扫描型负载下会被污染K3 以上收益递减但每个页要多存一个时间戳。3.2 页面 pin/unpin 的引用计数为什么总出错现象是测试跑着跑着报「page not found」或者数据被覆盖。原因几乎都是 pin count 没配对FetchPage会增加 pin countUnpinPage减少NewPage也增加。如果你在 B 树里拿到一个页、读完就忘了 Unpin缓冲池很快被占满淘汰器又不敢淘汰 pinned 页最后FetchPage返回 nullptr。我的排查习惯是在BufferPoolManager里加一个 map 记录每个 page_id 的 pin 次数析构时打印非零项。这个黑匣子帮我抓过至少五次泄漏。// 调试用在 UnpinPage 里检查计数 auto it pin_count_.find(page_id); if (it ! pin_count_.end() it-second 0) { LOG_ERROR(Unpin on zero pin count, page_id%d, page_id); }3.3 B 树插入分裂的边界根节点、叶节点、兄弟指针B 树最容易翻车的是分裂时的三种情况叶节点分裂要维护叶子链表指针内部节点分裂要把中间键上推根节点分裂要新建根。我建议先把「只插入不删除」跑通再加删除和合并。一个具体细节叶节点分裂后新节点的next_page_id要指向原节点的后继原节点的后继要指向新节点。顺序反了会导致扫描时漏数据。内部节点分裂时中间键是上推到父节点而不是留在任一子节点这点和叶节点不同写的时候容易混。3.4 迭代器与并发安全的取舍Bustub 的 B 树迭代器要求支持正向遍历。简单做法是加一把大锁但这样并发测试过不了。常见做法是 crabbing 协议遍历时先锁子节点再释放父节点。实现上要注意读操作可以用读锁写操作必须写锁且加锁顺序要一致否则死锁。我一般会先实现单线程正确版本再用std::shared_mutex替换最后跑并发测试。如果时间紧至少保证读操作并发安全写操作串行化这样大部分测试也能过。4. 查询执行与事务把 SQL 真正跑起来的那几公里到这一步你的存储和索引已经能用了但离「执行一条 SELECT」还差执行器、优化器和事务管理。4.1 火山模型执行器的算子实现顺序Bustub 用的是火山模型每个算子实现Init和Next。我建议的实现顺序是SeqScan → Filter → Projection → NestedLoopJoin → Aggregation → Sort → Limit。先做单表扫描加过滤能跑通SELECT * FROM t WHERE id 10再往下。Next返回的是Tuple加RID注意 RID 在投影之后可能失效聚合和排序时不要依赖它。Join 算子的输出 schema 要正确拼接左右表的列列偏移算错是常见 bug表现为结果列错位。4.2 事务隔离级别与锁管理器的落地Bustub 的锁管理器要求实现两阶段锁。共享锁和排他锁的兼容矩阵是基础关键是锁升级和死锁检测。我一般用等待图做死锁检测发现环就中止代价最小的事务。隔离级别上课程默认要求可串行化实现方式是严格两阶段锁。如果你只做到读已提交并发测试里的写偏斜场景会挂。参数上锁表的粒度用(txn_id, rid)做键比按表锁并发度高很多。4.3 用 EXPLAIN 验证执行计划是否符合预期写完执行器后用EXPLAIN看计划树是最快的验证手段。如果发现本该走索引的查询走了全表扫描要么是优化器没选对要么是索引没建上。我习惯在优化器里加日志打印每个候选计划的代价对比一下就知道问题在哪。-- 验证索引是否被使用 EXPLAIN SELECT * FROM users WHERE id 42; -- 期望看到 IndexScan 而不是 SeqScan如果输出是 SeqScan先检查Catalog里索引是否注册成功再检查优化器的规则有没有把 IndexScan 规则加进去。5. 避坑与排查那些让我熬夜的典型问题这一章全是血泪经验每条按现象、原因、解决来写。5.1 现象测试随机崩溃gdb 栈指向缓冲池原因pin count 泄漏导致页面被提前淘汰上层拿到的是已失效的指针。解决在UnpinPage和FetchPage里加计数校验跑一遍全量测试找出计数不为零的页号回溯调用链。5.2 现象B 树扫描结果比实际少几条原因叶节点分裂时兄弟指针更新顺序错误或者删除时没有正确合并。解决写一个「插入 N 条再全量扫描」的测试N 从 10 递增到 10000定位到哪个规模开始丢数据然后单步调试分裂逻辑。5.3 现象并发测试报死锁但等待图没检测到环原因加锁顺序不一致两个线程以相反顺序拿锁。解决统一加锁顺序比如永远先锁 page_id 小的页。这个坑很隐蔽因为等待图检测的是事务级环而这里是页级顺序问题。5.4 现象编译通过但链接报 undefined reference原因CMake 里新加的源文件没加到 target。解决检查CMakeLists.txt的add_library或add_executable列表Bustub 的模板工程经常需要手动加文件。5.5 现象Release 模式下测试通过Debug 模式失败原因Debug 模式有断言和未初始化内存检查暴露了 Release 下被掩盖的越界访问。解决永远以 Debug 模式为准Release 只用来跑性能。这个教训我吃过不止一次。6. 进阶技巧用日志恢复和时间旅行调试把正确性钉死到这一步你的 Bustub 已经能跑事务了但怎么证明它真的对我最后会做两件事写一个简单的日志恢复模块以及用「时间旅行」的方式回放操作序列。日志恢复的核心是 WAL任何修改先写日志再写数据页。实现上LogManager负责追加日志记录RecoveryManager在重启时重放。我一般先实现 redo再做 undo。redo 阶段从检查点开始重放所有已提交事务undo 阶段回滚未提交事务。参数上日志刷盘策略用「事务提交时强制刷盘」保证持久性。时间旅行调试是我自己加的一个技巧在缓冲池里记录每次页修改的操作序列和前后镜像测试失败时把序列导出来用一个独立脚本回放逐步缩小出错的操作。这个方法的成本是内存翻倍但定位偶发 bug 的效率极高。# 回放操作序列的简化脚本 import json ops json.load(open(trace.json)) state {} for op in ops: if op[type] write: state[op[page_id]] op[after] elif op[type] read: assert state.get(op[page_id]) op[expect], fMismatch at {op} print(replay ok)这个脚本不依赖数据库本身纯内存回放跑起来很快。我一般会在怀疑某个操作序列有问题时把 trace 导出来跑一遍确认是逻辑错还是并发时序错。最后一个习惯每完成一个 Project我都会把代码打一个 tag写一段「这个版本能过哪些测试、已知哪些边界没覆盖」。三个月后再回头看这段记录比任何文档都有用。希望帮到你。本文还有配套的精品资源点击获取