简介本资源为CMU-15445数据库系统课程Bustub项目的个人实现源码面向正在学习数据库系统原理、准备课程项目或希望深入理解DBMS内部机制的高校学生与开发者。项目围绕存储管理、查询优化、事务处理等核心议题展开适合作为课程实践参考与个人技术能力展示。压缩包共1195个文件约33.89MB以C源码为主包含260个h头文件、209个cpp与149个cc实现文件另有51个C文件、47个Python脚本及大量y、slt、yh测试用例辅以HTML、JavaScript、CSS构建前端界面Shell与Ruby用于自动化任务并配有Dockerfile、CMake、Bazel等构建与部署配置。目前已有162人学习关注。通过该源码可系统了解Bustub的目录组织、模块划分与测试体系掌握数据库系统从存储层到执行层的实现思路积累C工程实践与版本控制经验为课程项目或简历展示提供有力支撑。1. 从零手写 Bustub为什么数据库内核这门手艺值得你花三个月很多人第一次听到「基于 CMU-15445 课程的 Bustub 数据库系统个人实现」这个说法第一反应是「这不就是抄一遍课程作业吗」。我一开始也这么想直到自己动手把磁盘管理器、缓冲池、B 树索引、查询执行器一层层搭起来才发现这件事和「抄作业」完全是两码事。Bustub 是一个教学用的关系型数据库内核骨架它把 SQL 解析、查询优化、执行引擎、存储引擎、并发控制这些模块的接口都留好了但核心逻辑是空的需要你自己填。你填进去的每一行代码都会在真实的数据页、真实的锁竞争、真实的崩溃恢复场景里被检验。这个方向适合谁适合那些写了两三年 CRUD 业务、想往底层走但一直找不到入口的后端工程师适合在校学生想用一个能写进简历、又能真正讲清楚「数据库为什么这么设计」的项目也适合已经工作但想系统补一补存储引擎、索引结构、事务隔离这些硬知识的从业者。它不要求你先精通数据库理论但要求你愿意读代码、愿意调试、愿意接受「跑通了但性能很差」这个中间状态。接下来我会按「先立住理论、再动手复现」的顺序把 Bustub 的实现路径、关键参数、常见翻车点讲清楚让你看完能直接开干。2. Bustub 的模块拆解与最小可运行环境搭建2.1 先搞清楚 Bustub 到底包含哪些子系统Bustub 的代码结构大致分成四层。最底层是存储层包含磁盘管理器Disk Manager、缓冲池管理器Buffer Pool Manager和页表Page Table。磁盘管理器负责把数据库文件按页读写缓冲池管理器负责在内存里缓存热点页页表负责记录哪些页在内存里、哪些页被换出。中间层是索引层主要是 B 树索引和可扩展哈希表用来加速等值查询和范围查询。再往上是执行层包含执行器Executor、表达式求值Expression Evaluation和查询计划Plan Node。最上层是 SQL 解析和优化Bustub 用 PostgreSQL 的解析器把 SQL 转成抽象语法树再生成逻辑计划和物理计划。理解这个分层很重要因为你在实现的时候会反复在层与层之间穿梭。比如你实现 B 树索引需要调用缓冲池管理器拿页你实现执行器需要调用索引接口做查找。如果一开始就扎进某个模块的细节很容易迷失。我的建议是先画一张模块依赖图标清楚每个模块对外暴露的接口然后从存储层开始往上填。2.2 用 CMake 在本地跑通第一个测试用例Bustub 用 CMake 构建依赖 C17 和几个第三方库。下面是我在本地跑通第一个测试用例的完整命令你可以直接抄。# 克隆代码仓库这里用占位路径实际替换成你自己的仓库地址 git clone your-bustub-repo bustub cd bustub # 创建构建目录保持源码目录干净 mkdir build cd build # 配置 CMake开启调试信息和测试 cmake -DCMAKE_BUILD_TYPEDebug .. # 编译-j 后面跟你的 CPU 核心数我一般用 8 make -j8 # 运行第一个测试缓冲池管理器的基础测试 ./test/buffer_pool_manager_test这段命令的逻辑很直接先拿代码再建构建目录然后用 CMake 生成 Makefile最后编译并运行测试。参数上要注意CMAKE_BUILD_TYPE调试阶段一定用Debug因为 Bustub 的很多断言只在 Debug 模式下生效Release 模式下这些断言会被关掉你可能会漏掉一些隐蔽的错误。-j8里的 8 根据你机器调整太大容易内存爆掉太小编译慢。跑完第一个测试你会看到类似[ PASSED ]的输出。如果没通过先别急着改代码检查一下你的编译器版本是不是支持 C17以及第三方库有没有正确链接。常见做法是先跑make看有没有编译错误再跑测试看有没有断言失败。2.3 缓冲池管理器的三个必调参数缓冲池管理器是 Bustub 里第一个需要你完整实现的模块它直接决定后续所有模块的性能。有三个参数你必须理解并调对。第一个是pool_size_也就是缓冲池能容纳多少页。这个值设得太小页会频繁换入换出性能急剧下降设得太大内存占用高而且可能超过测试环境的内存限制。我一般会先设成 10 到 50 之间跑通功能后再根据测试用例的规模调整。第二个是replacer的类型。Bustub 默认用 LRU-K 替换算法K 值决定了你参考最近多少次访问。K 越大对历史访问模式越敏感但实现复杂度也越高。新手建议先用朴素的 LRU等所有测试通过后再换成 LRU-K。第三个是disk_manager_的页大小。Bustub 默认页大小是 4096 字节这个值在磁盘管理器和缓冲池管理器里必须一致。如果你改了页大小记得同步改所有相关配置否则会出现页号错乱。提示缓冲池管理器的测试用例里有一个「脏页写回」的场景很多人第一次跑会失败原因是忘记在换出脏页时调用WritePage。检查你的FlushPage和UnpinPage逻辑确保脏页在被换出前写回磁盘。3. B 树索引的实现从插入分裂到并发控制3.1 B 树的节点布局与插入分裂逻辑B 树是 Bustub 里最考验代码能力的模块。它的核心难点在于插入时的节点分裂和删除时的节点合并。先看节点布局内部节点存 key 和子节点指针叶子节点存 key 和 value或者指向记录的指针。Bustub 的 B 树模板参数里KeyType 和 ValueType 由你指定比较函数也由你传入。插入逻辑分三步。第一步从根节点开始找到应该插入的叶子节点。第二步在叶子节点里按序插入 key-value。第三步如果叶子节点满了分裂成两个节点把中间 key 推到父节点。如果父节点也满了继续向上分裂直到根节点。如果根节点分裂树高增加一层。下面是一个简化的插入分裂代码片段帮你理解关键逻辑。// 假设叶子节点容量为 leaf_max_size_ if (leaf-GetSize() leaf_max_size_) { // 直接插入保持有序 leaf-Insert(key, value); } else { // 叶子满了先插入再分裂 leaf-Insert(key, value); auto new_leaf SplitLeaf(leaf); // 分裂成两个叶子 // 把新叶子的第一个 key 推到父节点 InsertIntoParent(leaf, new_leaf-KeyAt(0), new_leaf); }这段代码的关键在于SplitLeaf和InsertIntoParent。SplitLeaf要把原叶子的一半数据挪到新叶子并维护好叶子之间的链表指针。InsertIntoParent要处理父节点满的情况递归向上。参数上leaf_max_size_决定了叶子节点的容量我一般设成 4 到 8 之间太小树高增长快太大分裂开销大。3.2 删除时的合并与重分配怎么不翻车删除比插入更麻烦因为你要处理节点合并和重分配。当叶子节点删除一个 key 后如果它的 size 小于leaf_max_size_ / 2就要考虑合并。合并分两种情况如果兄弟节点有富余就从兄弟借一个 key 过来这叫重分配如果兄弟节点也刚好在阈值附近就把两个节点合并成一个然后从父节点删掉一个 key。这里最容易翻车的地方是父节点的 key 更新。当你从兄弟借 key 时父节点里对应的分隔 key 必须更新否则后续查找会走错路径。我见过很多人只改了叶子节点的数据忘了改父节点的 key结果测试用例里范围查询全部失败。另一个坑是根节点的特殊处理。如果根节点是内部节点且只剩一个子节点要把这个子节点提升为新的根树高减一。这个逻辑不写树会越来越高最终查询性能退化。3.3 并发 B 树的 latch 策略与常见死锁Bustub 的 B 树要求支持并发操作这就引入了 latch轻量级锁。常见的策略是 crab walking从根节点开始先加住子节点的 latch再释放父节点的 latch像螃蟹一样往下走。插入时用写 latch查找时用读 latch。死锁通常发生在两个线程同时向上分裂的时候。线程 A 持有叶子节点的写 latch等待父节点的写 latch线程 B 持有另一个叶子节点的写 latch也在等同一个父节点。如果两个线程都不释放手里的 latch就死锁了。解决办法是统一加锁顺序永远先加父节点再加子节点。或者用 latch coupling 的变体在发现父节点不需要修改时提前释放。注意Bustub 的并发测试用例里有一个「混合读写」场景很多人跑的时候会卡住。先检查你的 latch 有没有在异常路径上释放再检查加锁顺序是否一致。调试并发问题可以用gdb挂上去看线程栈或者加日志打印每个线程持有的 latch。4. 查询执行器与表达式求值让 SQL 真正跑起来4.1 执行器的火山模型与迭代器接口Bustub 的执行器采用火山模型每个执行器实现一个Next()方法返回一个元组Tuple。上层执行器调用下层的Next()一层层拉取数据。比如SeqScanExecutor负责全表扫描IndexScanExecutor负责索引扫描InsertExecutor负责插入JoinExecutor负责连接。实现执行器的关键是理解Tuple和Schema。Tuple是数据行Schema描述列的类型和名称。你在实现SeqScanExecutor时需要从表堆Table Heap里逐行读取然后按 Schema 组装成 Tuple 返回。这里要注意迭代器的生命周期Next()返回 false 表示没有更多数据但你不能重复调用已经返回 false 的迭代器。4.2 表达式求值的类型转换与 NULL 处理表达式求值负责计算WHERE条件、SELECT列表和JOIN条件。Bustub 的表达式类型包括列引用、常量、比较运算、逻辑运算和算术运算。实现时最容易出错的是类型转换和 NULL 处理。类型转换方面Bustub 要求整数和浮点数之间可以隐式转换但字符串和数字之间不行。如果你在比较时遇到类型不匹配要先做类型提升。NULL 处理方面任何涉及 NULL 的比较结果都是 NULL而不是 true 或 false。在WHERE条件里NULL 会被当成 false 处理但在SELECT列表里NULL 要原样返回。// 比较表达式的求值逻辑 auto lhs left_-Evaluate(tuple, schema); auto rhs right_-Evaluate(tuple, schema); // 如果任意一边是 NULL直接返回 NULL if (lhs.IsNull() || rhs.IsNull()) { return Value::CreateNullValue(); } // 类型提升整数和浮点数比较时把整数转成浮点数 if (lhs.GetType() TypeId::INTEGER rhs.GetType() TypeId::DECIMAL) { lhs lhs.CastAs(TypeId::DECIMAL); } // 执行比较 switch (comp_type_) { case ComparisonType::Equal: return Value(lhs.CompareEquals(rhs)); // 其他比较类型类似 }这段代码的关键是 NULL 检查和类型提升。参数上CompareEquals返回的是std::optionalbool因为比较结果可能是 NULL。你要根据上下文决定怎么处理这个 optional。4.3 聚合与排序执行器的内存管理聚合执行器Aggregation和排序执行器Sort是内存消耗大户。聚合需要维护一个哈希表把 group by 的 key 映射到聚合状态。排序需要把所有数据读进内存排完再输出。如果数据量超过内存这两个执行器都会崩。Bustub 的教学版本通常不要求外部排序和外部聚合但你要知道这个边界。在实际测试里如果数据量不大直接全量读入内存没问题。但如果你的测试用例有几万行数据就要考虑分块处理。常见做法是先用LIMIT限制数据量或者把排序改成基于索引的有序扫描。提示聚合执行器的哈希表 key 要用Value的哈希函数不要自己写。Bustub 的Value类已经实现了Hash()和operator直接用就行。自己写哈希容易漏掉 NULL 和类型转换的情况。5. 避坑与排查Bustub 实现中最容易翻车的五个地方5.1 现象缓冲池测试通过但 B 树测试随机失败原因缓冲池管理器的UnpinPage没有正确处理is_dirty标志。当你在 B 树里修改了一个页但没有标记为脏页缓冲池换出时不会写回磁盘导致数据丢失。测试用例随机失败是因为换出顺序不确定。解决每次修改页内容后调用UnpinPage时把is_dirty设为 true。检查你的 B 树代码里所有UnpinPage调用确保修改过的页都标记了脏页。5.2 现象插入数据后查询不到但表堆里明明有数据原因索引和执行器的 Schema 不一致。比如你在插入时用了索引但索引的 key 类型和表堆的列类型不匹配导致索引查找走错路径。解决检查IndexScanExecutor里构造 key 的逻辑确保 key 的类型和索引定义一致。如果索引是INTEGER类型但你在构造 key 时用了DECIMAL查找就会失败。5.3 现象并发测试卡死gdb 显示线程都在等 latch原因latch 加锁顺序不一致或者异常路径上没有释放 latch。比如在 B 树插入时如果中途抛异常已经加上的 latch 没有释放其他线程就永远等下去。解决用 RAII 封装 latch确保析构时自动释放。Bustub 提供了std::lock_guard和std::unique_lock优先用它们。如果必须手动加锁用 try-catch 包住在 catch 里释放。5.4 现象表达式求值结果不对但逻辑看起来没问题原因Value的比较函数没有处理类型提升。比如INTEGER和DECIMAL比较时直接调CompareEquals会返回错误结果因为底层是按不同类型比较的。解决在比较前先做类型提升把INTEGER转成DECIMAL。Bustub 的Value::CastAs可以帮你做转换但要注意转换可能失败失败时返回 NULL。5.5 现象编译通过但运行时报段错误原因空指针解引用。Bustub 里很多接口返回指针比如FetchPage返回Page*如果页不存在会返回nullptr。你没有检查就直接用就崩了。解决所有返回指针的接口用之前先判空。如果为空要么返回错误要么抛异常。调试段错误可以用gdb的bt命令看调用栈定位到具体哪一行。6. 进阶技巧用 Bustub 验证你的索引设计直觉6.1 用自定义比较函数测试 B 树的灵活性Bustub 的 B 树支持自定义比较函数这意味着你可以用同一套代码实现不同排序规则的索引。比如你可以实现一个按字符串长度排序的索引或者按复合 key 排序的索引。这个技巧在面试里很加分因为面试官经常问「如果索引的排序规则不是默认的你怎么改」。具体做法是在构造 B 树时传入一个 lambda 作为比较函数。比如按字符串长度比较auto comparator [](const std::string a, const std::string b) { if (a.length() ! b.length()) { return a.length() b.length(); } return a b; // 长度相同按字典序 }; BPlusTreestd::string, RID, decltype(comparator) tree(index, comparator, ...);这个技巧的关键是理解 B 树的模板参数。KeyType和ValueType由你指定Comparator决定排序规则。你可以用这个特性测试不同索引设计对查询性能的影响。6.2 用性能计数器定位瓶颈Bustub 的缓冲池管理器里可以加性能计数器统计页命中率、换出次数、脏页写回次数。这些数据能帮你定位性能瓶颈。比如你发现页命中率很低说明缓冲池太小或者你的访问模式有问题。我一般会在缓冲池管理器里加三个计数器hit_count_、miss_count_、evict_count_。每次FetchPage时更新测试跑完后打印出来。如果命中率低于 80%就要考虑调大缓冲池或者优化访问模式。6.3 用崩溃恢复测试验证持久化逻辑Bustub 的存储层支持崩溃恢复你可以模拟在写入过程中断电然后重启数据库看数据是否一致。这个测试能验证你的脏页写回和日志逻辑是否正确。具体做法是在WritePage里加一个随机延迟模拟磁盘写入慢。然后在测试里插入一批数据中途强制退出进程再重新打开数据库检查数据是否完整。如果数据丢失说明你的脏页写回逻辑有问题。注意崩溃恢复测试要在 Debug 模式下跑因为 Release 模式下编译器可能优化掉一些中间状态。另外测试前先备份数据库文件避免数据损坏。我自己做 Bustub 的时候最大的教训是「不要跳过测试」。有一次我为了赶进度跳过了 B 树的并发测试结果在后续的查询执行器里遇到随机崩溃排查了两天才发现是 B 树的 latch 没释放。从那以后我养成了一个习惯每实现一个模块先把对应的测试全部跑通再往上走。这个习惯帮我省了很多后悔药。希望帮到你。本文还有配套的精品资源点击获取