简介：基于CMU-15445课程的Bustub数据库系统个人实现设计源码，主要面向数据库系统学习者、C++后端开发者和准备求职的在校学生。项目以CMU经典课程实验为蓝本，围绕存储管理、查询优化、事务处理等核心模块展开，是一份可直接阅读、编译并运行调试的DBMS课程实践。压缩包共1195个文件，大小约33.89MB，文件类型包括C++头文件与源文件（h/cpp/cc）、C与Python脚本、Markdown说明文档、HTML/CSS/JS前端资源，以及Shell脚本、Docker、Bazel/CMake构建配置等工程化文件；不同类型的文件分别承担核心实现、自动化测试、文档构建、界面展示与部署环境配置等任务，整体目录结构清晰。目前已有162人学习下载。由于代码遵循学术规范未在GitHub公开，这份资源为学习者提供了难得的完整参考，可结合源码、测试脚本和构建文件深入理解Bustub的模块划分与关键机制，也可作为个人简历中的项目亮点，展示系统设计与C++工程实践能力。
1. 为什么拿Bustub当数据库内核的第一台实验台
很多人把《数据库系统概念》第七版翻完，索引、事务、恢复都能画图，但打开MySQL源码仍然像看天书。CMU-15445课程的Bustub就是为了填这个空档而存在的：它是一个几万行的C++小型数据库，解析器、缓冲池、索引、执行器、事务全都有，而且官方骨架刻意把核心函数留空，逼着你亲手实现。你写出来的这套个人实现设计源码，就是一条从教材概念到可运行数据库的完整路径。它对两类人特别合适：一类是想进数据库内核方向的在校生，另一类是工作中需要读MySQL、TiDB源码，但苦于没有小项目打底的一线工程师。
2. 拿到Bustub源码后先跑通构建：目录结构与测试框架
2.1 源码目录里哪些文件该看、哪些该改
Bustub的代码组织方式很清晰：src/include下面放所有公开头文件，src/下放对应的.cpp实现。个人实现的第一步不是拿起键盘就开写，而是先把目录里重复出现的几个前缀认熟：
buffer/：缓冲池管理器、LRU-K替换器、磁盘调度。storage/：page/里的页类型定义（表页、索引页、日志页），table/里的堆表实现，index/里的B+Tree和Hash索引。execution/：执行器算子，每个算子一个文件。concurrency/：事务管理、锁管理器，Project 4才动。parser/和planner/：SQL词法语法解析和逻辑计划生成，默认就能工作，不需要你改。
我的习惯是先把buffer_pool_manager.h、b_plus_tree.h、seq_scan_executor.h这三个头文件读一遍，再看对应实现。这三个文件恰好覆盖了“页怎么存、索引怎么查、查询怎么跑”三条主线，读完你对整份源码的骨架就有数了。读的时候你会看到大量标着TODO的空函数，这不是残缺，是课程故意挖掉的坑位，你的个人实现就是把这些坑位按语义填回去。
2.2 最小构建命令与官方测试的组织方式
Bustub用CMake管理构建，依赖只有C++17编译器、CMake和Make，提交Project时官方用Linux环境评判，我自己的开发机是Ubuntu。先跑通一次最小构建：
git clone <bustub仓库地址> bustub cd bustub mkdir -p build && cd build cmake -DCMAKE_BUILD_TYPE=Debug .. make -j$(nproc) bustub-shell make -j$(nproc) b_plus_tree_test buffer_pool_manager_test第一行克隆按你手头的来源填，课程官方仓库和镜像都能用。这里的几个参数值得说清楚：CMAKE_BUILD_TYPE我建议老老实实用Debug，因为后面要用日志和断点调试，Release下很多调试符号和日志输出会被优化掉；-j$(nproc)是让Make用满所有CPU核心，初次编译会快很多，但如果内存不到16GB，建议改成-j4，否则编译中段OOM会很难受。
跑测试的方式和gtest保持一致。比如只想跑B+Tree里插入相关的用例：
./b_plus_tree_test --gtest_filter=*Insert*--gtest_filter支持通配符，*Insert*会匹配所有带Insert字样的用例。我一般先跑全量单测，再把挂掉的用例用filter单独拎出来。这里有个早该知道的血泪经验：不要编译完直接跑make check这种全量测试，Bustub本体加所有测试target编译时间不短，先单独build两个小测试target，确认编译链路没问题再往全量走。
2.3 用sqllogictest跑通第一行SQL
单元测试验证的是某个部件，sqllogictest验证的是整条SQL链路。Bustub把课程用的SQL测试文件放在sqllogictest/目录下，编译完后build目录里会生成bustub-sqllogictest可执行文件。挑一个最基础的.slt文件跑：
./bustub-sqllogictest ../sqllogictest/test/slt/basic/select.test如果前面的P0到P3实现没做完，这条命令大概率挂在半路。但如果你只想快速确认解析器和执行引擎是不是通的，可以先跑交互式shell：
./bustub-shell bustub> select 1;能返回一行结果，说明从词法解析到表达式执行的最小链路已经通了。这个起点很重要——很多人一上来就埋头写P0，写到P3才发现执行器连一行SQL都跑不动，回头再排查白白浪费几天。先跑通最小链路，再逐层补齐，这是我给所有做这套源码的人的第一条建议。
3. 四个核心项目的实现顺序：从Trie到B+Tree再到执行器
3.1 Project 0：用字典树把“表结构”搬进内存
Project 0是热身，但它选的数据结构很有讲究：Trie（字典树）。Trie的每个节点保存一个字符，从根到叶子拼起来就是完整key，天然适合做前缀查询和字符串类型的索引模拟。Bustub里要求实现一个支持并发读的Trie，核心操作是插入、删除和点查，并且要满足copy-on-write：读操作不加锁，写操作通过TrieStore统一加锁，修改时把路径上涉及的节点复制一份，原节点保持不变。
我实现时最常写的骨架是这样的：
// 个人实现骨架，核心思路是路径复制 auto Trie::Insert(const std::string &key, ValueType value) const -> Trie { std::shared_ptr<TrieNode> new_root = std::make_shared<TrieNode>(root_); std::shared_ptr<TrieNode> cur = new_root; for (char ch : key) { auto child = cur->GetChild(ch); std::shared_ptr<TrieNode> new_child; if (child != nullptr) { new_child = std::make_shared<TrieNode>(child->Clone()); // 拷贝已有子节点 } else { new_child = std::make_shared<TrieNode>(); // 新建子节点 } cur->SetChild(ch, new_child); cur = new_child; } cur->SetValue(std::move(value)); // 叶子节点写值 return Trie(new_root); }逻辑说明：每次Insert都从root_复制一颗新根，然后沿着key路径逐层复制碰到的子节点，最后在叶子节点写入value。这里的Clone()是深拷贝当前节点的children_，不能浅拷贝，否则新旧树会共享子节点，写操作的修改就泄漏到读路径上了。
参数说明：std::shared_ptr是必须的，因为多个版本的Trie要共享没有修改过的子树，引用计数帮你自动管理存活时间；std::move(value)是为了避免大对象拷贝，Bustub的value类型一般是整数或页ID，影响不大但这种写法是课程代码评审的标准要求。删除操作类似，区别是如果删完某个节点后它的children_空了，要把这个节点也从父节点中摘除，否则会产生空路径，导致后续前缀查询踩坑。
3.2 Project 1：LRU-K替换策略的Evict实现
Project 1是缓冲池管理器，核心是个LRU-K替换器。普通LRU只记录页面最近一次访问时间，LRU-K记录每个页面最近K次访问的时间戳，淘汰时优先淘汰“访问次数还没到K次”的页面，其次淘汰“K次访问里最久远那次最老”的页面。这个设计是为了防止全表扫描把热数据页一次性冲刷出去。
Bustub的LRUKReplacer接口暴露了四个核心操作：RecordAccess(frame_id)记录一次访问、SetEvictable(frame_id, bool)设置是否可淘汰、Evict(frame_id*)选一个受害者、Remove(frame_id)移除页面。实现时最关键的Evict逻辑：
// 个人实现骨架，核心是分两个优先级队列淘汰 auto LRUKReplacer::Evict(frame_id_t *frame_id) -> bool { // 第一优先：访问次数不足K次且最早被记录的帧 for (auto &[fid, info] : frame_info_) { if (info.IsEvictable() && info.GetAccessCount() < k_) { *frame_id = fid; Remove(fid); return true; } } // 第二优先：访问满K次，按第K次访问时间戳从小到大淘汰 frame_id_t victim = -1; size_t oldest_kth = std::numeric_limits<size_t>::max(); for (auto &[fid, info] : frame_info_) { if (info.IsEvictable() && info.GetAccessCount() >= k_) { if (info.GetKthAccessTime(k_) < oldest_kth) { oldest_kth = info.GetKthAccessTime(k_); victim = fid; } } } // 返回victim... }逻辑说明：第一轮扫描找“还没集满K次访问”的帧，这些帧通常是刚读入、还没形成访问历史的页面，优先淘汰它们；第二轮在访问次数足够的帧里，比较第K次访问的时间戳，最老的那个就是受害者。时间戳不用全局时钟，用LRUKReplacer内部自增计数器就行，因为只关心相对顺序。
参数说明：k_在课程测试里一般给2，你可以把k_=1退化成普通LRU对比着看效果；IsEvictable()这个标志特别重要，因为缓冲池里有些页面被Executor钉住了（pin住了），这些页面即使最老也不能淘汰，漏掉这个判断会让后续Project 3的NestedLoopJoin直接崩。
3.3 Project 2：B+Tree的插入与分裂要同时改三处
Project 2是整个Bustub个人实现里工作量最大、坑最深的部分，没有之一。B+Tree的每个叶子节点存键值对，内部节点只存键和子指针，所有叶子节点用双向链表串起来。它的特点是所有查找路径长度相等，且支持顺序扫描。你要实现插入、删除、查找和迭代器四组接口，其中最核心的是插入分裂。
插入时遇到满节点要分裂，我写的骨架：
// 个人实现骨架，描述叶子节点分裂的核心步骤 void BPlusTree::InsertIntoLeaf(LeafPage *leaf, const KeyType &key, const ValueType &val) { if (leaf->GetSize() < leaf->GetMaxSize()) { leaf->Insert(key, val); // 没满，直接插 return; } // 满了，分裂 LeafPage *new_leaf = reinterpret_cast<LeafPage *>(NewPage()); KeyType split_key = leaf->SplitHalf(new_leaf); // 前半留原页，后半移新页 if (key <= split_key) { leaf->Insert(key, val); } else { new_leaf->Insert(key, val); } // 把新叶子挂进双向链表 new_leaf->SetNextPageId(leaf->GetNextPageId()); leaf->SetNextPageId(new_leaf->GetPageId()); // 把分裂键上升插入父节点（此处省略父节点递归分裂） InsertIntoParent(leaf, split_key, new_leaf); }逻辑说明：SplitHalf把后半部分移动到新页，返回的是“晋升”到父节点的分隔键。注意插入时要比较key和split_key的大小决定插哪一半，不能先插再分裂，否则分隔键位置会错位。InsertIntoParent是递归的：父节点满了就分裂父节点，一路往上走，直到根节点分裂时生成新的根。根节点分裂有个特殊点：要申请新页做根，再把旧根和它的兄弟挂到新根下，同时更新root_page_id_。
参数说明：GetMaxSize()不是页大小除以元组大小这么简单，叶子节点和内部节点的max_size在Bustub里是显式存的，内部节点的max_size还要减去1（因为第一个key是无效的哨兵）；分裂时SplitHalf的切分点默认是size/2，但人为改成size - 1也是合法的B+Tree，只是树形更矮胖，测试能否通过取决于官方判分是否检查了严格的分裂比例。
Project 2的另一半是迭代器。迭代器从最左叶子开始，沿NextPageId往右走，每次operator++都判断当前叶子是否走完，走完就跳到下一页。这里最常见的错误是迭代器持有了Page但忘记在析构或移动时Unpin，导致跑完一个测试缓冲池就满了。
3.4 Project 3和Project 4：执行器与并发控制怎么和前面衔接
Project 3是查询执行引擎，用的是经典的Volcano模型：每个Executor实现Next()方法，每次返回一个Tuple。你要实现的算子包括SeqScan、Insert、Delete、NestedLoopJoin、HashJoin、Aggregation、Limit等。完成P0到P2之后，你已经有了表和索引的基础设施，执行器做的事情就是在这个基础上把SQL语义翻译成算子调用的流水线。
我的建议是动手前先弄清一个执行计划树的形状：比如select * from t1, t2 where t1.id = t2.id，Planner生成的是NestedLoopJoin，它的左子树是SeqScan(t1)，右子树是SeqScan(t2)，Join的谓词在NestedLoopJoinExecutor内部做匹配。每个算子的Next()要遵循“被调用一次吐一行”的协议，不要自己偷偷在一个Next()里把整个表读完——这点和写普通应用程序的直觉完全不同。
Project 4做的是并发控制：给执行器加上事务ID绑定和锁管理。它的核心是2PL（两阶段锁），事务在读之前对元组加读锁，写之前加写锁，提交时统一释放。我个人的体感是：P4本身不难，难在它要求你的P3实现满足“同一时间只有一个线程在跑某个事务”的测试前提，如果你的执行器里有静态变量或者没有正确Unpin，并发测试一开就崩。所以做P4前，先把P3的每个算子在一个单线程事务里反复跑，确认无状态泄漏再碰并发。
4. 把断点调试进Bustub：日志、打印、gdb三件套
4.1 日志级别与DEBUG模式：哪些输出能信
Bustub沿用了Google的日志框架，代码里到处是LOG_INFO("...")、LOG_DEBUG("...")。这些日志不是装饰，是官方留给你的调试后门。但前提是你必须用Debug模式编译，Release模式下LOG_DEBUG会被预处理器直接删掉，你打了也白打。我一般会在怀疑的入口加一行自己的标记日志：
LOG_INFO("Insert called with key=%ld", key); // 临时调试用然后用filter跑单个用例：
cmake -DCMAKE_BUILD_TYPE=Debug .. make -j4 b_plus_tree_test ./b_plus_tree_test --gtest_filter=*InsertTest1*日志是看执行路径最直接的窗口。但有两点坑要提前说：一是日志最多打到LOG_DEBUG级别，LOG_TRACE级别的输出生产环境和测试环境默认都不开，别指望它；二是不要在一行会被调用几百万次的函数里加日志，比如迭代器的Next()，加了之后一个测试能跑十几分钟，你会以为是算法卡死了，其实是终端在刷屏。
4.2 把B+Tree整棵树用ASCII画出来
B+Tree是个多叉结构，光靠打日志看插入路径，很难建立整体感。尤其是分裂、合并这种牵一发动全身的操作，画图比断点好用得多。Bustub把自己实现时的调试工具也带上了：b_plus_tree_printer.h。这玩意儿能把整棵树按层打印成ASCII树形图，更关键的是它支持把每一步操作后的树状态输出，像小时候玩汉诺塔一样一步步看。
// 在测试代码里插入这两行，观察当前整棵树 BPlusTreePrinter printer; printer.Print(b_plus_tree, "after_insert_42");如果你拿到的源码里没有这个工具，自己写一个也不难：从根页开始，按层遍历，每一层输出该层所有节点的键数组，然后换行继续往下。叶子的next指针单独打一遍，检查双向链表是否断裂。我见过太多“单个插入全对，连续插入崩掉”的案例，最后都是靠这棵树形图一眼看出根节点分裂后子页ID没更新。
4.3 用gdb脚本一键跑完一条SQL的执行计划
极端场景下日志和打印都不够用，比如内存越界把某个对象的vtable写坏了，程序崩溃时的调用栈完全是随机的。这时候上gdb，而且要上脚本化的gdb，不要手工next-next。方法是先选定一个关键断点——我一般选NestedLoopJoinExecutor::Next()或者BPlusTree::Insert，然后用gdb的commands自动打印上下文：
set pagination off break src/storage/index/b_plus_tree.cpp:键 commands silent printf "insert key = %ld, value = %ld\n", key, value continue end run --gtest_filter=*BPlusTreeInsert*注意断点的行号要换成你机器上实际的行位置(gdb) info line b_plus_tree.cc查。这个脚本的效果是：每次有键插入时自动打印一行，完全不用手点。崩溃时bt看到的调用栈，配合前面打印的插入序列，基本能定位是哪个键触发了问题。
脚本化gdb的另一个用途是跑随机压力测试时抓现场。比如你插十万个随机键后崩了，把随机种子打印出来，重跑时用-DSEED=12345固定同一个序列，就能稳定复现同一个崩溃点。这是我调试P2时用得最多的组合拳：随机数固定+断点条件+自动打印。
5. 避坑：Bustub个人实现期间踩过的5条记录
5.1 LRU-K的k值语义搞反导致P1全挂
现象是：缓冲池测试里有一个固定场景，先插入一批页，再访问其中几个，最后插入新页触发淘汰，预期是淘汰掉最久没访问的冷页，但实际淘汰的全是新插入的热页，测试全挂。
原因是我把k_理解成了“保留最近k次访问的页面”，写Evict时把访问次数不足k的帧直接当普通帧按LRU排序了，完全没做优先保护。LRU-K的正确语义是：访问次数少于k的帧在一个低优先级池子里，满k次的帧才进入正常淘汰池，且低优先级池子要优先被清空。
解决方法是把frame_info_拆成两个集合，一个装< k次访问的，一个装>= k次访问的；Evict先从第一个集合挑，空了再在第二个集合里按第k次访问时间排序。改完后再跑LRUKReplacerTest全绿。这个坑的教训是：替换策略的测试对淘汰顺序极其敏感，动手前先把“谁先死”的口语规则写在一张纸上。
5.2 B+Tree根节点分裂少改一处，插入即崩
现象是：插入到某个节点满后触发分裂，紧接着下一次查找有一半的键查不到，严重时直接触发断言page_id != INVALID_PAGE_ID。
原因是：根节点分裂和普通节点分裂不一样。普通节点分裂是“父节点已经存在，把分隔键往上插”；根节点分裂时没有父节点，必须新建一个页当新根，把旧根和新分裂出来的兄弟页都挂到新根下面，同时更新root_page_id_。我当时只处理了普通分裂，根分裂的代码路径里忘了更新root_page_id_，导致整棵树还指向旧的根页，而旧根已经被降级成普通内部节点了。
解决方法是：在InsertIntoParent的入口加一个判断，如果parent == nullptr，走独立的CreateNewRoot分支，在这里完成新根页申请、两个子页挂载、root_page_id_更新三个动作，缺一不可。这也解释了为什么B+Tree的插入是所有数据库课程项目里最容易出“查不到数据”bug的结构——边界分支太多，每个分支都要完整处理。
5.3 嵌套latch死锁：只在并发测试里偶然出现
现象是：Project 2的并发索引测试跑单线程全绿，开多线程后偶发卡死，几十分钟不动，Ctrl+C都难响应。
原因是：我在查找叶子页时持有了树级的大锁，又在叶子页上申请小锁，锁的顺序和另一条并发路径恰好相反，形成了AB-BA死锁。Bustub官方使用的并发方案是IndexLatch树路径加锁：从根到叶子按顺序加锁，父节点的锁在子节点锁拿到后才能释放，任何反向获取或者越级释放都会埋雷。
解决方法是：严格按“根→内部节点→叶子”的顺序拿锁，并且用一个RAII风格的守卫对象管理每个latch，确保异常路径能释放。我一开始手写unlock，漏了异常分支，后来改成了构造时加锁、析构时解锁的包装类，死锁问题再没复发过。如果你的并发测试卡住，第一反应不要看业务逻辑，先看所有latch的获取顺序是否构成环。
5.4 打开调试宏后测试直接超时
现象是：有一个慢测试，关掉日志跑5秒，打开#define BUSTUB_DEBUG后跑了五分钟还没结束，开始以为是算法复杂度爆炸。
原因是：Bustub的BUSTUB_DEBUG宏一旦开启，很多数据结构的每个方法都会把状态输出到LOG_DEBUG，比如B+Tree每次插入都要打印整棵树。这在一个循环插入几千个键的测试里就是几十万行输出，时间和IO都被日志吃掉了。
解决方法是：临时代码里不要全量打开调试宏，只在自己关心的函数入口输出一行摘要信息，比如打插入的key，不打树的全貌。需要看树形结构时，用第4章的BPlusTreePrinter单次打印，而不是让它跟随每个操作输出。记住一个原则：日志是给你定位问题用的，不是给你证明程序活着用的，能把问题逼出来的日志才是有效日志。
5.5 内存越界不被当场抓到，拖垮P3
现象是：P2测完没问题，做到P3执行器时，跑一个很简单的SeqScan就开始随机崩溃，崩溃点每次都不一样，有时在std::string的析构里，有时在memcpy里。
原因是：P2的某个叶子节点插入时越界写了一个数组，把相邻页的头部信息破坏了。这个bug在P2测试里没爆发，因为当时的页面内容刚好让越界写入的数据碰巧无害，但到了P3，越界写入的数据污染了元组存储，才在别的模块炸出来。这种“当时没爆、后来爆”的bug是最磨人的，因为它让你的排查范围从当前模块扩大到所有以前写过的模块。
解决方法是：从P2开始就开启AddressSanitizer编译，而不是等崩溃了再开。在CMake配置里加上：
cmake -DCMAKE_BUILD_TYPE=Debug -DCMAKE_CXX_FLAGS="-fsanitize=address -fno-omit-frame-pointer" ..ASAN会在越界发生的瞬间直接报错，带精确的行号和访问地址。我后面做P3和P4时全程开着ASAN，跑官方测试时偶尔因为ASAN的开销导致超时，就换到普通模式跑一遍确认——先保正确，再保速度。这个习惯帮我省掉了至少两天的无头排查，很多翻车现场其实是埋在前一个Project里的地雷。
6. 验证你的实现：用一条SQL和一张图证明索引真的被用上了
6.1 一个可复现的随机压力测试
官方测试覆盖的是标准路径，但个人实现最容易出的问题恰好是标准路径之外的长尾逻辑：叶子和内部节点的分裂比例不均衡、删除后合并的下界处理、根节点降级。我写了一个模板测试，每次随机插入N个键，再全量遍历验证：
// 个人自测代码，验证插入后所有键都在且有序 for (int i = 0; i < N; i++) { tree.Insert(keys[i], values[i]); } auto it = tree.Begin(); int count = 0; KeyType prev{}; while (it != tree.End()) { if (count > 0 && it->first <= prev) { LOG_ERROR("order broken at %d", count); break; } prev = it->first; count++; ++it; } assert(count == N); // 数量对得上，顺序也严格递增这段代码做三件事：一是断言所有插进去的键都能遍历出来（检验有没有分裂时丢键），二是断言遍历结果严格递增（检验叶子链表的顺序），三是统计数量和N一致（防止键被重复或丢失）。我一般把N设到十万，跑一个Debug+ASAN的版本，一晚上能验证一百次随机序列。
6.2 用EXPLAIN验证执行计划真的走了索引
如果你已经把Project 3做到能跑SQL，还有一个值得做的验证：创建一张表，插入几千行，然后执行一个带等值谓词的查询，用EXPLAIN看执行计划是SeqScan还是IndexScan。Bustub的优化器很基础，但至少能让你看到你的索引实现有没有被Planner认可。如果这里显示走了IndexScan，恭喜你，Bustub里从缓冲池到索引到执行器的整条链路已经在你手里跑通了。
这个验证的价值不是测试通过率，而是给你一个信心用的里程碑。做完这一步，再回头打开MySQL或者TiDB的源码，你看到的不再是陌生名词堆砌的黑匣子，而是一套你亲手搭过的架构换了个规模、换了个优化深度。我自己当时的习惯是把随机压力测试的N从一万调到一百万，顶着ASAN跑一整夜，第二天早上看日志有没有REPORT，这个习惯救了我很多次。希望帮到你。
本文还有配套的精品资源，点击获取
