简介：这是一份基于CMU-15445课程Bustub数据库系统的个人实现源码包，面向数据库方向学生、系统开发者及准备相关项目面试的求职者，可用于深入理解存储管理、查询优化、事务处理等DBMS核心机制。包内共1195个文件，压缩后约33.89MB，以260个h头文件、209个cpp及149个cc源文件为主，辅以Python脚本、Shell工具、HTML/CSS前端资源及Bazel、CMake等构建配置，覆盖从核心代码到环境部署、测试脚本的完整工程链路。已有162人学习下载。代码遵循学术规范未公开托管，适合放入个人简历展示，阅读时可结合项目结构梳理Bustub各模块实现思路，参考C++内存管理与并发控制写法，利用Dockerfile与测试文件辅助本地编译验证，快速建立从理论到工程实现的整体认知。
1. CMU-15445 与 Bustub：一门课和一个能写进简历的内核项目
做后端的人迟早会撞上这样一个问题：天天用 MySQL、PostgreSQL，可真要说出一条 SQL 从客户端到磁盘的完整路径，大多数人是懵的。CMU-15445 这门课就是来解决这个问题的，而 Bustub 是这门课的配套项目——一个麻雀虽小、五脏俱全的关系型数据库内核，从缓冲池、B+Tree 索引、查询执行器到并发控制，全部要求你亲手写一遍。
我身边不少人最初只是冲着“课程名气大”去的，结果写着写着发现，这几乎是目前能接触到的最好的数据库内核入门源码实践。它不像读 PostgreSQL 源码那样动辄百万行，也不像做某个 CRUD 项目那样毫无技术含量。Bustub 让你在一个学期内把数据库最核心的几十个文件啃完，每一行代码都踩在真实工程问题上。这篇文章就围绕“个人实现”这条主线，讲清楚这个项目怎么搭、怎么写、怎么避坑，以及最终怎么能变成一份拿得出手的设计源码。
2. 把 Bustub 跑起来：环境、构建与三级测试目标
2.1 构建环境选型：为什么绕不开 Linux 和 Clang
先说结论：不要用 Windows 原生环境做这个项目。Bustub 的构建脚本、测试框架和内存检测工具全部围绕 Linux 设计，Windows 下即使勉强跑通，也会在教学环境依赖、内存调试和性能验证上浪费大量时间。我见过有人在 WSL 里折腾三天，最后发现是文件权限和路径长度问题导致编译失败。
一个干净的 Ubuntu 20.04/22.04 虚拟机或者云主机是最稳妥的选择。依赖项并不复杂：Clang、CMake、Flex、Bison 以及一个较新版本的 C++ 标准库。有个容易被忽略的点：Bustub 官方推荐 Clang 而不是 GCC，因为它的测试框架里有不少依赖 LLVM 工具链的编译期行为。如果你用 GCC 编译，某些模板特化和内存对齐相关的代码可能会产生诡异的行为，这不是“玄学”，是工具链差异。
# 安装必要依赖（Ubuntu 22.04 为例） sudo apt update sudo apt install -y clang cmake flex bison libreadline-dev zlib1g-dev # 克隆并编译 git clone https://github.com/cmu-db/bustub.git cd bustub mkdir build && cd build cmake -DCMAKE_BUILD_TYPE=Debug .. make -j$(nproc)我一般会把-DCMAKE_BUILD_TYPE=Debug作为默认选项，因为本项目大量依赖断言和调试符号来定位问题。Release 模式虽然在跑步测试时更快，但一旦遇到段错误，你面对的就是一堆没有行号信息的黑匣子。等代码完全稳定了，再切 Release 做性能验证不迟。
2.2 代码结构速览：先认清哪些文件是你该写的
Bustub 的源码树并不复杂，但第一次打开时容易迷失。核心目录就是src/和src/include/，头文件和实现文件一一对应。你需要重点关注的并不是全部代码，而是标有TODO(P0)、TODO(P1)这类标记的文件——这些才是你要实现的“个人设计”部分。
# 查看所有待实现的 TODO 标记 grep -rn "TODO(P" src/ src/include/ | wc -l # 按优先级查看分布 grep -rn "TODO(P0)" src/ src/include/ | head -20完成这个命令后，你会看到大约 30 个左右的 TODO 点分布在缓冲池、B+Tree、执行器和并发控制模块中。这是个很关键的“范围认知”阶段：很多人在 P0 的 LRU-K 替换策略上较劲太久，却不知道 P1 的 B+Tree 才是真正的重头戏。
2.3 三级测试目标：本地测试、Grace Grade 与性能基准
这个项目的测试体系分成三层。第一层是 Google Test 单元测试，覆盖每个模块的基本功能；第二层是课程官方的 Grace Grade 评分系统，跑的是更全面的测试集；第三层是性能基准，比如 Leaderboard 测试，要求你的 B+Tree 在特定并发场景下达到一定的吞吐量。
我的建议是不要把精力全部放在“通过所有本地测试”上。本地测试只是保底，Grace Grade 会做很多边界情况和并发压力测试，这些才是拉开分数差距的地方。一个务实的目标顺序是：先保证单线程功能全部通过，再优化并发控制的正确性，最后才是性能调优。
# 只跑当前模块的测试，而不是全量测试 cd build ./bustub-test --gtest_filter="BufferPoolManager*" # 查看测试用例列表 ./bustub-test --gtest_list_tests | head -50这一步的意义在于让你建立“增量式开发”的节奏。Bustub 的模块依赖关系很强，比如 P3 的查询执行器依赖 P1 的缓冲池，如果你不从最小可运行版本开始积累，很容易陷入“写了三百行代码，一编译全是错，根本不知道从哪改起”的困局。
3. 逐模块拆解：从 LRU-K 到事务管理器，四个必写的核心组件
3.1 缓冲池管理：LRU-K 替换策略为什么比 LRU 更适合数据库
缓冲池是数据库的内存缓存层，Bustub 在 P0 阶段就要求实现 LRU-K 替换策略。和传统的 LRU 不同，LRU-K 关注的是“访问历史次数和最近访问时间”的二元组合，它的核心思想是：如果一个页在最近 K 次访问中表现出高频率，它就应该被保留，而不是仅因为“刚刚被访问过”就享受高优先级。
这个设计的合理性在数据库场景中非常明显。全表扫描会让大量页变成“一次性访问”的状态，如果只使用 LRU，这些刚被扫过的页会占据缓冲池，导致真正被频繁访问的索引页被挤出去。LRU-K 通过记录访问历史，能够更准确地识别哪些页是“长期热点”。
// src/include/buffer/lru_k_replacer.h 中的核心接口 class LRUKReplacer { public: // 记录一次访问历史，frame_id 是缓冲池帧编号 void RecordAccess(frame_id_t frame_id) { // 维护访问历史队列和 eviction 候选集 // 具体实现要点：使用 std::list 存储 frame 的访问记录 auto &history = access_history_[frame_id]; history.push_back(current_timestamp_++); if (history.size() > k_) { history.pop_front(); // 只保留最近 K 次访问 } } };我当时实现时踩了一个隐蔽的坑：RecordAccess和Evict之间的同步问题。LRU-K 要求只淘汰“不可固定的帧”（未被 pin 住的页），而判断一个帧是否可淘汰的时机点非常微妙。正确做法是：每次Evict时先遍历所有帧的访问历史，找出最早一次访问时间最小的那个，并且跳过所有 pin 计数大于零的帧。这块逻辑如果不加锁，在并发测试下会出数据竞争，而 GTest 的 TSan 配置会自动检测到这种问题。
3.2 B+Tree 索引：插入分裂与删除合并的边界条件
B+Tree 是 Bustub 课程里最难啃的骨头，也是工程价值最高的一块。与教科书里简单的二叉树不同，B+Tree 的插入和删除需要处理节点分裂、节点合并、根节点变化、叶子节点链表维护等一堆边界条件。课程给了一个可视化调试工具b_plus_tree_printer，但实际开发时的核心工具是 logging 和 gdb。
插入操作的关键路径是：从根节点向下搜索，找到目标叶子节点，插入键值对，如果溢出则分裂。这里的难点在于分裂时需要把中间键上提到父节点，并且正确连接新的兄弟节点。如果父节点也满了，需要递归分裂直到根节点。
// 插入分裂的核心逻辑（简化版） void BPlusTree::InsertIntoLeaf(LeafNode *leaf, const KeyType &key, const ValueType &value) { if (leaf->IsFull()) { // 1. 创建新的叶子节点 auto *new_leaf = NewLeafNode(); // 2. 将后半部分键值对移动到新节点 leaf->MoveHalfTo(new_leaf); // 3. 在父节点中插入新的分隔键 InsertIntoParent(leaf, new_leaf->GetFirstKey(), new_leaf); } else { leaf->Insert(key, value); } }删除操作比插入更繁琐。删除后的下溢（小于最小填充数）需要优先尝试向兄弟节点借键（rotation），不行才做合并（merge）。Bustub 的测试用例设计得很刁钻，专门设计了连续删除后索引结构仍然保持正确的场景。我花了整整一个周末的时间重写了三版删除逻辑才全部通过，最后发现原来借键时不仅要更新父节点的分隔键，还要同步更新叶子链表的 prev/next 指针，这是一个每周都有几十人在讨论区问的经典坑点。
3.3 查询执行器：火山模型与表达式求值的拆解
P3 的查询执行器是 Bustub 里最有“数据库感觉”的部分。这一阶段要求实现一系列执行器节点：SeqScan、Insert、Delete、IndexScan、Aggregation、Limit、NestedLoopJoin 等。整个架构使用的是标准的火山模型——每个执行器都实现Next()接口，每次调用返回一条元组。
对这部分的个人实现，我的经验是不要从 NestedLoopJoin 开始写，而应先完成 SeqScan 和 Insert/Delete 这三个最基础的节点。因为它们构成了表读写的基础路径，后面的 IndexScan 和 Join 都依赖于对 Tuple 和 TableHeap 的理解。
// SeqScan 执行器的核心实现 bool SeqScanExecutor::Next(Tuple *tuple, RID *rid) { // 从头开始扫描表堆，每次调用返回下一个满足条件的元组 while (table_iterator_ != table_info_->table_->End()) { auto [cur_tuple, cur_rid] = *table_iterator_; ++table_iterator_; // 执行谓词过滤（如果存在 WHERE 条件） if (predicate_ == nullptr || predicate_->Evaluate(&cur_tuple, &schema_).GetAs<bool>()) { *tuple = cur_tuple; *rid = cur_rid; return true; } } return false; }这里有一个非常容易翻车的细节：predicate_->Evaluate的调用时机。很多人会写成先取下一个元组再判断谓词，导致最后一条有效元组被跳过。这个 bug 的诡异之处在于它只在特定数据分布下才会出现，单测里很难发现。我在跑 TPC-H 风格的测试时才暴露出来。
3.4 并发控制：锁管理器与死锁检测的工程化实现
P4 的锁管理器是课程里最后一个大模块。Bustub 要求实现共享锁、排他锁、意向锁以及死锁检测。这里的难点不是锁的语义——那部分教科书讲得很清楚——而是“锁的升级”“锁的等待队列”和“死锁检测”三者之间的交互。
死锁检测的实现思路并不复杂：构建一个等待者-持有者的有向图，定期检测环，发现环后选择一个 victim 事务回滚。但真正的工程难点在于“什么时候检测”“怎么选择 victim”“回滚后其他事务应该做什么反应”。
// 死锁检测的核心数据结构 class LockManager { // 等待者 -> 持有者 的映射（边） std::unordered_map<txn_id_t, std::unordered_set<txn_id_t>> waits_for_; // 定期执行的检测线程 void RunDeadlockDetection() { while (!stop_) { std::this_thread::sleep_for(std::chrono::milliseconds(1000)); std::lock_guard<std::mutex> lock(lock_table_latch_); auto cycle = FindCycle(waits_for_); if (cycle.has_value()) { auto victim = ChooseVictim(cycle.value()); AbortTransaction(victim); } } } };选择 victim 的规则在课程里有明确要求：优先选择事务 ID 较大（较年轻）的事务，同时兼顾已经持有的锁数量。但实际跑测试时发现了一个微妙问题：如果单纯按事务 ID 选，可能会反复选中某个正在做长查询的事务，导致它永远无法完成。更合理的做法是结合“事务年龄 + 持有的锁数量”做加权，让老事务有更高的存活概率。
4. 测试驱动开发：用 GTest 和自定义工具验证每个阶段的正确性
4.1 学会读测试源码：比读源码更重要的事情
Bustub 课程的测试文件里藏着一座金矿——每个测试用例的命名和注释都在告诉你这个模块的边界条件在哪。很多学生等着官方的 Grace Grade 评分，却不知道test/目录下的 GTest 文件其实就是“开卷考试”的范围。
// test/buffer/buffer_pool_manager_test.cpp 中的典型用例 TEST(BufferPoolManagerTest, UnpinAndReusePageTest) { // 核心意图：验证 unpin 后页面可以被重新分配 // 场景：创建一个容量为 1 的缓冲池，连续分配两个页面 auto bpm = std::make_unique<BufferPoolManager>(1); // 容量为 1 page_id_t page_a = bpm->NewPage(); bpm->UnpinPage(page_a, true); page_id_t page_b = bpm->NewPage(); ASSERT_NE(page_a, page_b); // 关键断言 }读测试源码的一个直接收益是：你能精确知道某个函数在什么输入下会被调用，以及期望的输出边界。比如上面的测试如果失败，常见的原因是你的NewPage在缓冲池满了之后没有正确选择一个 victim 页，或者UnpinPage没有正确维护 pin 计数。
4.2 用自定义 SQL 语句做集成验证：从底层到上层的完整链路
Bustub 自带了一个命令行 shell，你可以像使用 MySQL 一样输入 SQL 语句。这个工具在 P3 之后价值极大，因为它能验证从解析、计划到执行的完整链路是否走得通。我习惯在完成每个执行器后，就手工构造几条针对性 SQL 来测试。
-- 创建一个测试表并插入数据 CREATE TABLE test_table (id INT, name VARCHAR(32)); INSERT INTO test_table VALUES (1, 'Alice'); INSERT INTO test_table VALUES (2, 'Bob'); -- 验证顺序扫描和投影 SELECT name FROM test_table WHERE id > 1; -- 验证聚合函数 SELECT COUNT(*) FROM test_table;这里的执行计划会输出到终端，你可以看到每个操作符的名字、涉及的表达式和预估行数。一个非常有用的技巧是：在 shell 里执行EXPLAIN SELECT ...，它会打印出执行计划树。如果你发现某条 SQL 走了 SeqScan 而不是 IndexScan，先不要急着怀疑优化器，先检查你的IndexScanExecutor是否正确处理了索引键的范围条件。
4.3 性能验证：Leaderboard 测试与热点分析
当你功能全部通过后，如果想要冲刺更高的分数，就需要关注 Leaderboard 测试。这个测试集的关注点是：在并发场景下，你的 B+Tree 是否能够承受高吞吐的查询。这时候 Debug 版本的代码就能明显感到性能不足——大量断言检查和日志打印会拖慢速度。
# 编译 Release 版本 cmake -DCMAKE_BUILD_TYPE=Release .. make -j$(nproc) # 运行 Leaderboard 测试 cd build ./bustub-leaderboard-test --gtest_filter="LeaderboardTest.*"性能优化的常见切入点是锁粒度。Bustub 的 B+Tree 在 P2 阶段要求支持并发读写，最朴素的做法是对整棵树加一把大锁，这能保证正确性但性能极差。逐步细化为 latch crabbing 协议后，吞吐量会有质的飞跃。我在优化时发现，叶子节点的 latch 竞争是最大的瓶颈，因为所有读操作最终都要锁叶子节点。通过把叶子节点上的读写锁改成 try-lock 加自旋重试的模式，性能提升了大约 40%。
5. 避坑指南：个人实现中遇到的五个高频问题（现象 → 原因 → 解决）
5.1 编译警告被当成错误：Clang 的 -Werror 陷阱
现象：代码明明看起来没问题，编译却报出几十个error: unused variable或error: implicit conversion。
原因：Bustub 的 CMake 配置开启了-Werror，任何警告都会被升级为编译错误。这其实是课程有意为之，逼迫你写出干净的代码，但在开发初期非常折磨人。
解决：在CMakeLists.txt里找到target_compile_options，注释掉-Werror，但仅限本地方便开发用。提交代码前务必恢复，否则会导致 Grace Grade 评分时直接编译失败。
5.2 B+Tree 删除后索引结构不完整：叶子节点链表断开
现象：删除大量键值后，SELECT查询返回的行数变少，甚至出现std::bad_alloc。
原因：合并叶子节点时，只更新了父节点的指针，没有同步维护叶子节点之间的prev_和next_双向链表。这个 bug 平时很难发现，因为单线程的GetValue只走根到叶的路径，不会用到叶子链表的横向遍历；只有做全表扫描（如SELECT *）时才会触发。
解决：在合并逻辑中专门加一个步骤：合并前先从叶子链表的结构开始检查。写一段校验函数，遍历所有叶子节点，检查prev_->next_ == this是否成立，不成立说明链表指针出了问题。
5.3 事务回滚后没有释放锁：死锁检测失效
现象：并发测试跑到一半突然卡死，所有线程都阻塞在LockTable上。
原因：事务在死锁检测中被选为 victim 后，只做了事务状态回滚，但LockManager里该事务持有的锁没有释放。后续事务在等待这个永远不会释放的锁，系统进入“活锁”状态。
解决：在AbortTransaction的实现中，除了清除事务的WriteSet和还原数据外，必须遍历LockManager的锁表，释放当前事务持有的所有锁，并唤醒对应的等待队列。
5.4 缓冲区页面没有标记 dirty：数据丢失无异常
现象：UPDATE语句执行成功，但重启数据库后数据丢失。
原因：在BufferPoolManager::UnpinPage时，is_dirty参数传入了false。查询执行器在修改页面数据后，没有正确传递脏页标记，导致页面被淘汰时没有写回磁盘。
解决：在TableHeap::UpdateTuple和DeleteTuple中，调用UnpinPage时强制传入true。更稳妥的做法是：让页面在被修改的时刻就标记为脏，而不是依赖调用者传递参数。
5.5 执行器在并发场景下的数据竞争：Tuple 生命周期管理不当
现象：用 TSan 编译跑并发测试，报data race on std::shared_ptr<TableInfo>，或者偶发返回错误数据。
原因：多个执行器节点共享同一个TableInfo和Schema指针，这些对象的所有权在查询计划销毁时统一释放。如果一个执行器还在迭代中，另一个线程销毁了计划，就会产生悬挂指针。
解决：在执行器构造函数中拷贝Schema对象而不是持有引用；对TableInfo使用std::shared_ptr管理，确保在所有执行器生命周期结束后才释放底层资源。
6. 让源码成为“作品”：代码组织、注释规范与进阶方向
当你的 Bustub 全部测试都通过后，面前还有一件更重要的事：如何让这套代码看起来像一个“设计源码”，而不是“作业草稿”。我的做法是花三个晚上做代码整理，重点改三件事。
第一，头文件里的 TODO 注释全部删除，改成自己的实现说明。写清楚“这个函数干了什么”“输入输出约束是什么”“边界情况如何处理”。这不仅是给别人看的，更是给一个月后的自己看的。Bustub 的代码量大，如果不留说明，回头改 bug 时你会遗忘当时的思路。
第二，将分散在多处的条件编译开关统一整理。比如 Hw 版本标记#ifdef ENABLE_LOCK_MANAGER这类宏，按课程阶段分组注释，避免后续阅读时不知道哪些代码是“课程要求添加的”，哪些是“个人扩展的”。
第三，补充一份项目级别的README.md，内容包括：编译步骤、测试命令、模块设计框图、踩坑记录、性能优化前后对比。很多面试官看项目时先打开 README，如果这里写得清晰，会留下“这个工程师有工程素养”的第一印象。
做完这些整理后，才算真正把 Bustub 从“课程项目”变成了“个人作品”。这几周写下的不仅仅是一个数据库内核的代码，更是一套对存储引擎、索引结构、并发控制的直觉理解。以后再去读 MySQL 或 TiDB 的源码，你会发现那些组件的命名和架构设计是那么熟悉。
最后说个我自己的习惯：每次提交一段新代码前，强制自己回答三个问题——这个函数在什么输入下会失败？这个锁的等待条件是什么？如果事务在中间崩溃，数据会变成什么状态？答不上来就回去改代码。经过 Bustub 的洗礼，这套思考方式现在已经成了我读任何后端源码的本能反应。希望帮到你。
本文还有配套的精品资源，点击获取
