简介这份资源是卡内基梅隆大学CMU-15-445数据库系统课程的学习资料合集面向希望深入理解数据库底层实现的高校学生与后端开发工程师。内容围绕缓冲池管理器、B树索引、并发控制与记录恢复机制等核心模块展开并配有C11编程实践、课程视频总结与实验指导建议适合在完成课程实验或准备数据库相关面试时对照查阅。压缩包共121个文件以55个h头文件与46个cpp源文件为主体另有md笔记、txt说明、png图示及少量c、cc与docx文档整体约2.64MB目录结构便于按实验模块定位代码。目前已有66人学习下载。读者可从中获取B树、锁管理器、表页等关键组件的实现思路与测试用例结合笔记与实验建议梳理数据库系统的设计脉络为构建高性能、高可靠性的存储引擎打下基础。1. 从 CMU-15-445 的 BusTub 说起这套实验代码到底能帮你打通哪些数据库底层关节如果你正在啃《数据库系统概念》第七版或者刚被 MVCC 多版本并发控制绕得头晕又或者想找一个能真正跑起来的数据库内核实验来练手那 CMU-15-445 的 BusTub 大概率是你绕不开的一站。这套资源不是那种只给你 PPT 和视频的“观光型”课程包它把缓冲池管理器、B 树索引、并发控制、记录恢复这些数据库系统里最硬的骨头全部拆成了可编译、可测试、可调试的 C 工程。你拿到的是一个能直接cmake构建的代码库里面有b_plus_tree.cpp、lock_manager_test.cpp、table_page.cpp这些实打实的实现文件也有sqlite3.c、shell.c这种拿来就能用的参考实现。它适合谁适合那些已经不满足于写 SQL、想看看页表怎么换入换出、锁怎么加、日志怎么回滚的人。换句话说这是给数据库系统学习者的“解剖台”不是“科普展板”。2. 把 BusTub 跑起来环境、构建与第一个可执行测试2.1 工具链选型为什么是 C11 和 CMake这套代码的底层语言标准是 C11/C11这不是随便选的。数据库内核里大量涉及内存布局控制、原子操作、无锁数据结构C11 提供的std::atomic、std::thread、std::unique_ptr刚好卡在“够用且不臃肿”的甜点区。你不需要上 C20 的协程也不用碰 C17 的std::optional因为 BusTub 的代码风格偏底层很多地方直接操作裸指针和页帧。构建系统用的是 CMake这是 CMU 课程一贯的选择好处是跨平台Linux 和 macOS 都能跑Windows 下用 WSL2 也基本无障碍。我一般会先确认三件事编译器版本、CMake 版本、以及有没有装gtest。BusTub 的测试用例依赖 Google Test但资源包里已经带了gmock-gtest-all.cc和gmock_main.cc所以你不需要额外去 apt 装。这一点很关键很多人在这一步翻车是因为系统里已经有一个旧版 gtest链接时符号冲突报一堆undefined reference。2.2 从零构建命令与参数说明假设你已经把压缩包解压到了CMU-15-445-master目录终端进入该目录后标准操作是mkdir build cd build cmake -DCMAKE_BUILD_TYPEDebug .. make -j$(nproc)这三行命令里-DCMAKE_BUILD_TYPEDebug是必须的因为 BusTub 的很多断言和assert只在 Debug 模式下生效。如果你用 Release 模式跑测试有些越界访问和空指针解引用会被优化掉测试可能“假通过”但实际逻辑是错的。-j$(nproc)是并行编译BusTub 的代码量不小单线程编译可能要十几分钟并行能压到两三分钟。编译完成后你会看到build目录下生成了一堆可执行文件比如b_plus_tree_test、lock_manager_test、buffer_pool_manager_test。这些就是你的“验收工具”。我习惯先跑一个最简单的./test/b_plus_tree_test --gtest_filter*InsertTest*--gtest_filter是 Google Test 的参数用来只跑匹配的用例。BusTub 的 B 树测试有几十个全跑一遍可能要几分钟但如果你只关心插入逻辑用过滤器能省不少时间。注意测试可执行文件的路径通常在build/test/下但不同版本的 CMakeLists 可能把输出目录设到build/bin/你find . -name *_test一下就能确认。2.3 目录结构速览哪些文件对应哪些实验资源包里的文件不是随便堆的每个文件名都对应一个具体的实验模块。我整理了一个快速对照表方便你按需切入文件名对应实验/模块核心考察点buffer_pool_manager.cpp缓冲池管理器LRU-K 替换策略、页帧管理、脏页写回b_plus_tree.cppB 树索引插入/删除/查找、节点分裂与合并b_plus_tree_internal_page.cppB 树内部节点键值路由、子指针维护lock_manager.cpp并发控制两阶段锁、死锁检测、锁升级table_page.cpp表页/记录管理槽位页结构、记录插入与删除virtual_table.cpp虚拟表/执行器迭代器模型、谓词下推sqlite3.c/shell.c参考实现SQLite 内核源码用于对比学习这个表不是让你全看而是让你知道当你卡在某个实验时该去翻哪个文件。比如你发现 B 树的删除操作导致树结构不平衡那就直接盯b_plus_tree.cpp里的Remove和Coalesce函数不用在缓冲池的代码里浪费时间。3. 缓冲池管理器与 B 树索引从页帧到磁盘的完整链路3.1 缓冲池的 LRU-K 替换策略为什么不是简单的 LRU缓冲池管理器的核心任务是把磁盘上的页按需加载到内存页帧里并在内存不够时决定淘汰谁。BusTub 用的是 LRU-K而不是教科书里常见的 LRU。LRU-K 的关键区别在于它记录每个页最近 K 次访问的时间戳淘汰时看第 K 次访问的时间而不是最后一次。这样做的好处是能识别出“看似最近访问、实则只访问了一次”的扫描型负载避免全表扫描把热页挤出去。在buffer_pool_manager.cpp里你会看到LRUKReplacer类维护了一个std::unordered_mapframe_id_t, std::listsize_t来存访问历史。K 的值默认是 2但你可以通过构造函数参数改。我一般会先跑buffer_pool_manager_test里的SampleTest确认基本的NewPage、FetchPage、UnpinPage能过再去调 LRU-K 的淘汰逻辑。这里有个血泪经验UnpinPage的is_dirty参数一定要传对否则脏页不会被写回测试里会报“页内容不一致”但你查半天查不出原因因为数据其实还在内存里只是没落盘。3.2 B 树的插入与分裂代码块与参数说明B 树是这套实验里最耗时的部分没有之一。它的核心难点在于节点分裂时的键值分配和父节点更新。下面这段代码是b_plus_tree.cpp里插入操作的关键片段我加了注释方便你对照// 在叶子节点中插入键值对 if (leaf-GetSize() leaf-GetMaxSize()) { leaf-InsertAt(idx, key, value); // 直接插入不分裂 } else { // 叶子节点已满需要分裂 auto *new_leaf new LeafPage(...); int split_idx leaf-GetSize() / 2; // 从中间分裂 // 把后半部分键值对搬到新叶子 for (int i split_idx; i leaf-GetSize(); i) { new_leaf-InsertAt(i - split_idx, leaf-KeyAt(i), leaf-ValueAt(i)); } leaf-SetSize(split_idx); // 原叶子只保留前半部分 // 把新叶子的第一个键插入父节点 parent-InsertAt(parent_idx, new_leaf-KeyAt(0), new_leaf); }这段代码里GetMaxSize()通常等于leaf_max_size - 1因为 B 树的一个节点要留一个空位给“溢出”键。split_idx取GetSize() / 2是标准做法但有些实现会偏向左边或右边取决于你的删除逻辑怎么处理合并。如果你在删除时发现合并后节点大小经常超过max_size那可能是分裂时偏了。参数leaf_max_size和internal_max_size在b_plus_tree.h里定义默认值分别是 2 和 3用于测试实际生产环境会设到几百。你可以在测试里改这两个值观察树高变化。3.3 并发控制中的锁管理器两阶段锁与死锁检测lock_manager.cpp实现的是两阶段锁2PL的简化版。每个事务在访问记录前必须申请锁锁的类型有共享锁S和排他锁X。BusTub 的锁管理器用一个std::unordered_maptxn_id_t, std::unordered_setLockDataId来记录每个事务持有的锁同时用一个等待图来检测死锁。死锁检测的周期通常是 50ms这个值在lock_manager.h里可以调。如果你把周期设得太短CPU 会浪费在遍历等待图上设得太长死锁事务会卡很久。我一般会先跑lock_manager_test里的DeadlockTest确认两个事务互相等待时能正确回滚一个。这里有个容易忽略的点锁的粒度。BusTub 的锁是加在记录 ID 上的不是页上。这意味着如果你在table_page.cpp里做全表扫描每个记录都要申请锁开销很大。常见做法是先用意向锁IS/IX在表级或页级声明意图再在记录级加锁。但 BusTub 的实验为了简化没有强制要求意向锁你可以自己加但要注意别和测试用例的预期冲突。4. 记录恢复与 C11 编程日志、回滚与底层内存操作4.1 日志记录与恢复机制WAL 的简化实现记录恢复机制的核心是 Write-Ahead LoggingWAL。BusTub 的恢复模块要求你在修改页之前先把日志记录写到磁盘。日志记录的类型包括Insert、Delete、Update每条日志包含事务 ID、页 ID、槽位 ID、前后镜像。恢复时系统先做 Analysis 确定哪些事务需要 Redo、哪些需要 Undo然后做 Redo 把已提交事务的修改重放最后做 Undo 把未提交事务的修改回滚。在table_page.cpp里你会看到InsertRecord和DeleteRecord函数在修改槽位数组之前会调用log_manager-AppendLog()。这个调用不能省否则崩溃后数据就丢了。我见过有人为了“提高性能”把日志关掉结果测试里的RecoveryTest直接挂掉因为模拟崩溃后重启数据页和日志对不上。参数方面log_manager的缓冲区大小默认是 8KB你可以调大但要注意刷盘频率。如果缓冲区太大崩溃时未刷盘的日志会丢失恢复就不完整了。4.2 C11 编程在数据库内核中的体现原子操作与内存序C11 标准引入的std::atomic和内存序memory order在 BusTub 的并发控制里用得很多。比如在lock_manager.cpp里锁表的读写用std::atomicbool做自旋锁内存序用std::memory_order_acquire和std::memory_order_release来保证可见性。如果你用默认的std::memory_order_seq_cst性能会差一些但不容易出错。我一般建议新手先用seq_cst等测试全过了再逐步换成acquire/release用-fsanitizethread跑一遍确认没有数据竞争。另一个 C11 的特性是_Static_assert在b_plus_tree_internal_page.cpp里用来检查页大小是否对齐。这个断言在编译期生效如果页结构体的大小和PAGE_SIZE不匹配编译直接报错比运行时报错好查得多。你可以在CMakeLists.txt里加-DCMAKE_C_FLAGS-stdc11来强制 C11 标准但 BusTub 默认已经配好了不用改。4.3 虚拟表与执行器迭代器模型怎么接virtual_table.cpp实现的是执行器层的迭代器模型。每个执行器如 SeqScan、IndexScan、Insert都继承自AbstractExecutor提供Init()和Next()两个接口。Next()返回一个Tuple和RID上层执行器通过循环调用Next()来拉取数据。这种“拉”模型Pull-based比“推”模型Push-based更容易实现谓词下推和 Limit 短路。如果你在实现IndexScan时发现Next()返回了重复记录那可能是 B 树的迭代器没有正确跳过已删除的槽位。检查b_plus_tree.cpp里的Begin()和Next()确认它们在遇到Delete标记时能跳过。5. 避坑与排查那些让实验卡三天的常见问题5.1 编译通过但测试挂页帧 ID 越界现象buffer_pool_manager_test里NewPage返回的page_id是负数或者FetchPage直接段错误。 原因page_id是int32_t但页帧 ID 是frame_id_t两者在Page对象里转换时没做边界检查。BusTub 的DiskManager默认分配的页 ID 从 0 开始如果你手动构造了一个超出pool_size的页 IDFetchPage会去访问pages_数组的越界位置。 解决在FetchPage开头加assert(page_id 0 page_id disk_manager_-GetNumPages())Debug 模式下会直接断在越界前比段错误好查。5.2 B 树删除后树结构断裂合并顺序错了现象删除一个键后再查找相邻键返回nullptr但树的高度没变。 原因在Coalesce或Redistribute时先更新了父节点的键再移动子节点的指针导致中间状态被其他线程看到如果是并发测试或者父节点的路由键和子节点的实际最小键不一致。 解决先移动子节点的键值对再更新父节点的路由键。如果是并发场景给父节点加写锁确保原子性。我一般会在Remove里加一个assert(parent-KeyAt(idx) child-KeyAt(0))跑测试时如果断言失败就能定位到是哪一步顺序错了。5.3 锁管理器死锁检测误报等待图没清理现象lock_manager_test里两个事务明明没有循环等待却被判定死锁其中一个被回滚。 原因等待图用的是std::unordered_maptxn_id_t, std::unordered_settxn_id_t当事务释放锁时只删了锁表里的记录没删等待图里的边。残留的边导致下一轮检测时误判。 解决在Unlock函数里遍历等待图把所有指向该事务的边删掉。如果性能敏感可以用一个反向索引std::unordered_maptxn_id_t, std::unordered_settxn_id_t来加速删除。5.4 恢复测试失败日志刷盘时机不对现象RecoveryTest模拟崩溃后重启发现已提交事务的修改丢了。 原因log_manager的Flush只在缓冲区满时调用但测试里的崩溃是立即发生的缓冲区里的日志还没落盘。 解决在事务提交时强制调用log_manager-Flush()确保提交日志先于数据页落盘。这是 WAL 的基本要求但很多人为了“优化”把它去掉结果恢复测试必挂。5.5 内存泄漏导致测试超时页帧没释放现象跑完buffer_pool_manager_test后进程不退出或者valgrind报一堆definitely lost。 原因NewPage分配的Page对象在UnpinPage时没有delete因为 BusTub 的页帧是复用的但测试里可能反复NewPage而不DeletePage。 解决在DeletePage里显式delete页对象并把pages_数组对应位置置空。如果你用std::unique_ptr管理页帧这个问题自动消失但 BusTub 的原始代码用的是裸指针需要手动处理。6. 进阶验证用 SQLite 源码对比 B 树实现与性能调优技巧6.1 为什么拿 sqlite3.c 做参照资源包里的sqlite3.c和shell.c不是让你编译 SQLite 的而是给你一个工业级 B 树实现的参照。SQLite 的 B 树在btree.c里虽然代码风格和 BusTub 不同但核心逻辑——节点分裂、合并、平衡——是一样的。你可以把 BusTub 的b_plus_tree.cpp和 SQLite 的btree.c并排看重点对比两处一是分裂时键的分配策略SQLite 用的是“平衡分裂”BusTub 用的是“中间分裂”二是删除时的合并条件SQLite 允许节点在删除后暂时低于半满延迟合并而 BusTub 要求立即合并。这两种策略没有绝对优劣但 SQLite 的延迟合并在高并发写入下表现更好因为减少了锁的持有时间。6.2 性能调优调整页大小与缓冲池容量BusTub 的默认页大小是 4KB缓冲池大小是 10 个页帧。这个配置在测试里够用但如果你想模拟真实负载可以改buffer_pool_manager.h里的POOL_SIZE和disk_manager.h里的PAGE_SIZE。我一般会把POOL_SIZE设到 1000PAGE_SIZE保持 4KB然后用b_plus_tree_test里的InsertTest跑 10 万条记录观察disk_manager的读写次数。如果读写次数远大于树高乘以记录数说明缓冲池命中率低可能是 LRU-K 的 K 值设得太小或者页帧淘汰太频繁。把 K 从 2 调到 5再跑一遍通常能看到 I/O 次数下降 30% 左右。6.3 一个具体技巧用 gtest 的 death test 验证断言BusTub 的测试里有很多assert但assert在 Release 模式下会被禁用。如果你想确保某个非法操作一定会触发断言可以用 Google Test 的 death testTEST(BPlusTreeTest, InvalidPageIdDeathTest) { ASSERT_DEATH({ auto *page buffer_pool_manager-FetchPage(-1); }, page_id 0); }ASSERT_DEATH会 fork 一个子进程执行代码块如果子进程没有异常退出测试就失败。这个技巧在验证边界条件时特别有用因为你可以把“非法输入必须崩溃”写成测试用例而不是靠人工检查。注意death test 在 Debug 模式下才能捕获assertRelease 模式下assert被优化掉子进程不会崩溃测试会报错。所以跑 death test 时一定要用-DCMAKE_BUILD_TYPEDebug。从那以后我每次改完 B 树的删除逻辑都会先跑一遍 death test再跑常规测试最后用valgrind检查内存。这套流程走下来基本能拦住 90% 的低级错误。希望帮到你。本文还有配套的精品资源点击获取