简介基于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/里的BTree和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管理构建依赖只有C17编译器、CMake和Make提交Project时官方用Linux环境评判我自己的开发机是Ubuntu。先跑通一次最小构建git clone bustub仓库地址 bustub cd bustub mkdir -p build cd build cmake -DCMAKE_BUILD_TYPEDebug .. 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保持一致。比如只想跑BTree里插入相关的用例./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到BTree再到执行器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_ptrTrieNode new_root std::make_sharedTrieNode(root_); std::shared_ptrTrieNode cur new_root; for (char ch : key) { auto child cur-GetChild(ch); std::shared_ptrTrieNode new_child; if (child ! nullptr) { new_child std::make_sharedTrieNode(child-Clone()); // 拷贝已有子节点 } else { new_child std::make_sharedTrieNode(); // 新建子节点 } 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 1LRU-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_limitssize_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 2BTree的插入与分裂要同时改三处Project 2是整个Bustub个人实现里工作量最大、坑最深的部分没有之一。BTree的每个叶子节点存键值对内部节点只存键和子指针所有叶子节点用双向链表串起来。它的特点是所有查找路径长度相等且支持顺序扫描。你要实现插入、删除、查找和迭代器四组接口其中最核心的是插入分裂。插入时遇到满节点要分裂我写的骨架// 个人实现骨架描述叶子节点分裂的核心步骤 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_castLeafPage *(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也是合法的BTree只是树形更矮胖测试能否通过取决于官方判分是否检查了严格的分裂比例。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.idPlanner生成的是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_TYPEDebug .. make -j4 b_plus_tree_test ./b_plus_tree_test --gtest_filter*InsertTest1*日志是看执行路径最直接的窗口。但有两点坑要提前说一是日志最多打到LOG_DEBUG级别LOG_TRACE级别的输出生产环境和测试环境默认都不开别指望它二是不要在一行会被调用几百万次的函数里加日志比如迭代器的Next()加了之后一个测试能跑十几分钟你会以为是算法卡死了其实是终端在刷屏。4.2 把BTree整棵树用ASCII画出来BTree是个多叉结构光靠打日志看插入路径很难建立整体感。尤其是分裂、合并这种牵一发动全身的操作画图比断点好用得多。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的另一个用途是跑随机压力测试时抓现场。比如你插十万个随机键后崩了把随机种子打印出来重跑时用-DSEED12345固定同一个序列就能稳定复现同一个崩溃点。这是我调试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 BTree根节点分裂少改一处插入即崩现象是插入到某个节点满后触发分裂紧接着下一次查找有一半的键查不到严重时直接触发断言page_id ! INVALID_PAGE_ID。原因是根节点分裂和普通节点分裂不一样。普通节点分裂是“父节点已经存在把分隔键往上插”根节点分裂时没有父节点必须新建一个页当新根把旧根和新分裂出来的兄弟页都挂到新根下面同时更新root_page_id_。我当时只处理了普通分裂根分裂的代码路径里忘了更新root_page_id_导致整棵树还指向旧的根页而旧根已经被降级成普通内部节点了。解决方法是在InsertIntoParent的入口加一个判断如果parent nullptr走独立的CreateNewRoot分支在这里完成新根页申请、两个子页挂载、root_page_id_更新三个动作缺一不可。这也解释了为什么BTree的插入是所有数据库课程项目里最容易出“查不到数据”bug的结构——边界分支太多每个分支都要完整处理。5.3 嵌套latch死锁只在并发测试里偶然出现现象是Project 2的并发索引测试跑单线程全绿开多线程后偶发卡死几十分钟不动CtrlC都难响应。原因是我在查找叶子页时持有了树级的大锁又在叶子页上申请小锁锁的顺序和另一条并发路径恰好相反形成了AB-BA死锁。Bustub官方使用的并发方案是IndexLatch树路径加锁从根到叶子按顺序加锁父节点的锁在子节点锁拿到后才能释放任何反向获取或者越级释放都会埋雷。解决方法是严格按“根→内部节点→叶子”的顺序拿锁并且用一个RAII风格的守卫对象管理每个latch确保异常路径能释放。我一开始手写unlock漏了异常分支后来改成了构造时加锁、析构时解锁的包装类死锁问题再没复发过。如果你的并发测试卡住第一反应不要看业务逻辑先看所有latch的获取顺序是否构成环。5.4 打开调试宏后测试直接超时现象是有一个慢测试关掉日志跑5秒打开#define BUSTUB_DEBUG后跑了五分钟还没结束开始以为是算法复杂度爆炸。原因是Bustub的BUSTUB_DEBUG宏一旦开启很多数据结构的每个方法都会把状态输出到LOG_DEBUG比如BTree每次插入都要打印整棵树。这在一个循环插入几千个键的测试里就是几十万行输出时间和IO都被日志吃掉了。解决方法是临时代码里不要全量打开调试宏只在自己关心的函数入口输出一行摘要信息比如打插入的key不打树的全貌。需要看树形结构时用第4章的BPlusTreePrinter单次打印而不是让它跟随每个操作输出。记住一个原则日志是给你定位问题用的不是给你证明程序活着用的能把问题逼出来的日志才是有效日志。5.5 内存越界不被当场抓到拖垮P3现象是P2测完没问题做到P3执行器时跑一个很简单的SeqScan就开始随机崩溃崩溃点每次都不一样有时在std::string的析构里有时在memcpy里。原因是P2的某个叶子节点插入时越界写了一个数组把相邻页的头部信息破坏了。这个bug在P2测试里没爆发因为当时的页面内容刚好让越界写入的数据碰巧无害但到了P3越界写入的数据污染了元组存储才在别的模块炸出来。这种“当时没爆、后来爆”的bug是最磨人的因为它让你的排查范围从当前模块扩大到所有以前写过的模块。解决方法是从P2开始就开启AddressSanitizer编译而不是等崩溃了再开。在CMake配置里加上cmake -DCMAKE_BUILD_TYPEDebug -DCMAKE_CXX_FLAGS-fsanitizeaddress -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设到十万跑一个DebugASAN的版本一晚上能验证一百次随机序列。6.2 用EXPLAIN验证执行计划真的走了索引如果你已经把Project 3做到能跑SQL还有一个值得做的验证创建一张表插入几千行然后执行一个带等值谓词的查询用EXPLAIN看执行计划是SeqScan还是IndexScan。Bustub的优化器很基础但至少能让你看到你的索引实现有没有被Planner认可。如果这里显示走了IndexScan恭喜你Bustub里从缓冲池到索引到执行器的整条链路已经在你手里跑通了。这个验证的价值不是测试通过率而是给你一个信心用的里程碑。做完这一步再回头打开MySQL或者TiDB的源码你看到的不再是陌生名词堆砌的黑匣子而是一套你亲手搭过的架构换了个规模、换了个优化深度。我自己当时的习惯是把随机压力测试的N从一万调到一百万顶着ASAN跑一整夜第二天早上看日志有没有REPORT这个习惯救了我很多次。希望帮到你。本文还有配套的精品资源点击获取
