缓冲池、B+树、锁与日志恢复：数据库内核实验代码包实战-北京尧图网络

简介面向数据库系统深入学习者卡内基梅隆大学CMU-15-445课程实验代码与学习笔记整合了缓冲池管理器、B树索引、并发控制、记录恢复机制、C11编程实践及数据库理论应用等核心主题适合正在攻克数据库内核实验的本科生、研究生或自学者。压缩包共121个文件整体仅2.64MB以55个头文件和46个C源文件为主涵盖B树实现、锁管理器测试、SQLite内核等实验代码同时包含6份Markdown学习笔记、5个txt说明、3张示意图和1份Word版附加文档便于边读代码边对照理论。目前已有66人学习下载。逐模块研读源码并配合课程视频总结与实验指导建议可完成从缓冲池页面置换、B树节点分裂合并到事务锁冲突处理、日志故障恢复的完整实验闭环不仅帮助理解数据库内部运行机制也为后续性能调优与工程实践积累扎实经验。1. 一份数据库系统课程的代码包先别急着跑B树搞懂这三个模块再动手第一次拿到这个15-445课程代码包的时候我以为是网上流传的普通实验源码解压之后才发现里面塞了sqlite3.c、shell.c、gmock-gtest-all.cc这一整套编译链还有b_plus_tree.cpp、lock_manager_test.cpp这些分模块实现。说白了这不是一份给你“读一读”的笔记而是一份要你自己动手把缓冲池、B树、锁管理器、日志恢复逐个写出来的工程量。很多同学抱着“数据库系统是理论课”的心态进来结果被第一周实验里的页面替换策略虐到深夜。这份资源恰好把这些模块按课程进度拆开每个模块都有对应的源文件和测试文件适合已经学过数据库原理、想把手上的理论变成可运行代码的人。接下来我按实际拆包顺序讲清楚每个模块的玩法、参数和踩坑点。2. 缓冲池管理器把磁盘页和内存页的映射关系先搞对2.1 为什么缓冲池是数据库性能的闸门数据库最贵的动作不是算数而是读磁盘。一个页面大小通常是4KB或者8KB机械盘随机读一次要花好几毫秒内存里访问同样的数据只需要几十纳秒。缓冲池存在的原因就是让大部分读操作命中内存避免每次都触发磁盘I/O。这个模块的代码思路很直接维护一个固定大小的帧数组每个帧可以装一页磁盘数据再维护一个页表记录page_id到帧id的映射。当请求的页不在缓冲池里就要从磁盘读入并替换掉一个旧页。这份资源里的table_page.cpp就是用来定义页内部布局的它告诉你每个页的头部存什么、记录槽位怎么排。如果你跳过页结构直接去写替换器后面B树和虚拟表都会接连出错。因为所有上层模块都依赖“页”这个最小单位。2.2 从table_page.cpp看页结构的设计打开table_page.cpp能看到一个典型表页的实现思路。页头部需要记录当前页内的记录数、空闲空间起始偏移、以及每个槽的位置。其实它本质上是一个可变长度记录的容器头部有固定大小的元数据中间是空洞尾部是槽数组。槽数组里的每一项存的是对应记录的起始偏移量删除记录时只需要把槽标记为删除物理空间留给后续插入复用。一个常见的表页头结构长这样struct TablePage { uint32_t num_records_; // 当前记录数 uint32_t free_space_ptr_; // 空闲空间起始偏移从页尾向中间增长 uint32_t slot_count_; // 槽的数量可能大于存活记录数 // 槽数组slot_offsets_[i] 记录第 i 个槽的偏移量0 表示空槽 uint32_t slot_offsets_[0]; };这段代码里的num_records_和slot_count_经常被搞混。slot_count_是已经分配的槽位数量删除记录后槽位不会立刻回收所以slot_count_可以大于num_records_。free_space_ptr_则指向从页尾向中间挤压后的空闲区域起点插入新记录时要先检查剩余空间是否够用。如果你在写Append逻辑时没判断剩余空间就会覆盖掉已有的槽数组那种随机性数据损坏在测试里非常难查。2.3 实现LRU替换器的常见路径缓冲池的替换策略在课程实验里通常要求实现LRU但工程里更好用的是LRU-K。LRU的问题在于一次全表扫描会让刚读入的页占满整个缓冲池把真正高频的页挤出去。LRU-K记录每个页被访问的倒数第K次能区分“偶尔扫一遍”和“持续热点”。在这次资源里没有直接给出替换器源码但你在自己写实验时最稳妥的路线是先实现一个带时间戳的双向链表。下面是一个LRU-K替换器的骨架用C11写刚好struct FrameInfo { size_t frame_id_; size_t pin_count_; std::listsize_t history_; // 保存最近访问的 bucketbucket 按时间递增 }; class LRUKReplacer { public: explicit LRUKReplacer(size_t num_frames, size_t k) : max_size_(num_frames), k_(k) {} void RecordAccess(size_t frame_id) { auto info frame_infos_[frame_id]; info.history_.push_back(current_bucket_); if (info.history_.size() k_) info.history_.pop_front(); // 只有未被 pin 的帧才进入可淘汰集合 if (info.pin_count_ 0) evictable_frames_.insert(frame_id); } bool Evict(size_t *frame_id) { for (auto fid : evictable_frames_) { size_t oldest *frame_infos_[fid].history_.begin(); if (oldest earliest_bucket_) { earliest_bucket_ oldest; *frame_id fid; } } if (*frame_id kInvalidFrameId) return false; evictable_frames_.erase(*frame_id); return true; } private: size_t k_; size_t current_bucket_ 0; std::unordered_mapsize_t, FrameInfo frame_infos_; std::setsize_t evictable_frames_; };这里RecordAccess里的history_记录的是访问次序 bucket不是真实时间戳。桶值越大表示越新。Evict遍历所有可淘汰帧选出历史记录里最早的那个。注意pin_count_不为0的帧绝对不能进evictable_frames_否则正在被线程使用的页会被换出后续读写直接踩内存空指针。这个参数是替换器里的性命开关。2.4 pin/unpin计数最容易翻车的地方缓冲池里每个帧都有一个pin_count表示当前有多少上层模块正在引用这个页。读页时pin用完必须unpin。如果你忘了unpin那个帧永远不被淘汰缓冲池很快满掉反过来如果提前把pin_count置0就会把还在使用的页换出。我在拆这个资源时看到测试文件里专门有反复pin/unpin的用例就是要逼你把这个计数做对。一个正常流程是FetchPage里先查页表命中则pin_count并返回帧指针未命中则选择一个victim帧把脏页写回再读入新页然后pin_count。UnpinPage里减少计数如果减到0把帧标记为evictable。很多同学会忘记在DeletePage时也去清理页表项导致page_id留在页表里指向已经释放的帧这是另一个隐蔽bug。3. B树索引内部页分裂是自找麻烦的地方3.1 为什么数据库偏要选B树而不是B树B树和B树的差别外行看是“数据只存在叶子”内行看是“叶子之间串了链表方便范围扫描”。数据库做范围查询的频率远高于精确点查B树的叶子链表让顺序遍历不需要回根节点重新走一遍。另一个关键点是B树每个节点可以放更多键树更矮磁盘I/O次数更少。这个课程实验里给的b_plus_tree.cpp和b_plus_tree_internal_page.cpp就是在实现这两件事。内部页存储的是“键子页ID”的列表不存真实记录。叶页存储“键值”或者“键记录ID”。由于所有数据都在叶子内部页的分裂和合并逻辑可以完全复用同样的键比较规则。3.2 内部页与叶页的字段设计看b_plus_tree_internal_page.cpp内部页头会有key_count_和most_secure_key_之类的字段但更核心的是它用两个并行的数组一个存键一个存子页ID。注意B树内部页的键数量总是比子指针数少一个因为每个键是其右子树的最小值或者最大值取决于实现。分裂时中间键要上升到父节点而不是留在孩子里——这是和B树最大的区别。struct BPlusTreeInternalPage { uint32_t key_count_; // 键数组大小为 max_size_ - 1 std::vectorint32_t keys_; // 子页面ID数组大小为 max_size_ std::vectorpage_id_t children_; page_id_t ChildAt(uint32_t index) const { return children_[index]; } int32_t KeyAt(uint32_t index) const { // 键数组和子指针数组错位KeyAt(i) 对应 children_[i1] 的起始键 return keys_[index]; } };这里的错位设计是初学者最容易晕的地方。插入一个新键时如果当前节点已满先创建一个右兄弟节点把一半键和指针搬过去然后把中间的键准确说是右兄弟的最小键插入父节点。这个过程要同时更新叶子链表的兄弟指针漏一个后面遍历就断。3.3 插入分裂与删除合并的边界写插入逻辑前我先复盘一次崩溃现场当时我在测试插入500条数据每次跑到200条左右就死循环。后来发现是根节点分裂时我没有创建新的根节点而是试图把旧根一分为二结果导致父指针互相指成了环。正确做法是当根节点满时创建一个新根旧根成为新根的第一个子节点然后再做分裂。这个“先建新根再分裂”的顺序不能反。删除时合并则是另一个极端。如果删除导致叶子节点利用率低于40%就需要从兄弟节点借一个键或直接合并。合并发生时父节点要删除对应的键和指针。这里有个细节如果兄弟节点在左边不能简单把两个页拼在一起因为左叶子的最大键要替换成右叶子的最小键这个键还要更新到父节点。测试文件b_plus_tree_test.cpp里故意构造了删除到只剩一个键的用例就是逼你处理这种边界。3.4 virtual_table.cpp如何把B树暴露给查询层虚拟表模块是课程实验后加的扩展它的作用是把B树包装成SQLite能识别的虚拟表接口。这样你在SQLite里执行SELECT * FROM btree WHERE key1底层调用的是你的B树实现。virtual_table.cpp里主要实现xOpen、xNext、xFilter这些回调。xFilter里解析查询约束然后调用B树的FindKey或BeginScan。这里要特别提醒虚拟表的约束参数是SQLite传来的字符串需要自己解析成整数或字符串不能直接把指针当数值用。否则在64位系统上会出现高32位随机数据变成key导致查询结果诡异。我自己写这段时每周都会遇到一次“为什么查不到明明存在的数据”最后print出key值才发现是高字节没清零。4. 并发控制锁管理器的重入问题是死锁温床4.1 锁表设计锁粒度、锁模式与隔离级别并发控制的本质是让多个事务看起来像是串行执行的。课程实验里的锁管理器通常要求支持表锁和行锁锁模式至少要有SHARED和EXCLUSIVE。实现时用一个哈希表键是锁的标识比如表ID行ID值是一个结构体记录持有该锁的事务集合、等待队列、锁模式。锁升级是个容易被忽略的点。事务先从SHARED拿锁后续要写时再升级为EXCLUSIVE。如果直接升级而另一个事务也持有SHARED锁就变成“共享锁等待排他锁排他锁等待共享锁释放”的循环。解决方法是升级时先申请排他锁如果冲突就回滚整个事务而不是原地等待。这样虽然粗暴但至少不会死锁。4.2 lock_manager_test.cpp从测试反推实现我看lock_manager_test.cpp的时候感觉它就是在逼你处理重入问题。测试里会有同个事务连续LockShared两次同一个资源第二次不应该死锁而只是增加一个引用计数。很多初版实现没做持有检测第二次加锁直接进等待队列然后把自己堵死。// lock_manager_test.cpp 里典型的并发用例 std::thread t1([]() { txn_mgr.Begin(txn1); bool ok lock_mgr.LockShared(txn1, rid1); assert(ok); // 模拟工作 std::this_thread::sleep_for(std::chrono::milliseconds(10)); lock_mgr.Unlock(txn1, rid1); txn_mgr.Commit(txn1); }); std::thread t2([]() { txn_mgr.Begin(txn2); bool ok lock_mgr.LockExclusive(txn2, rid1); assert(ok); lock_mgr.Unlock(txn2, rid1); txn_mgr.Commit(txn2); }); t1.join(); t2.join();这个测试的关键在于两个线程同时启动t1先拿共享锁t2申请排他锁会失败需要等t1释放。如果你的锁管理器没有条件变量t2会直接返回false而不是阻塞测试就会失败。合理做法是每个锁资源维护一个std::condition_variable所有等待该锁的请求挂在那里Unlock时统一唤醒让它们重新竞争。4.3 两阶段锁与死锁检测两阶段锁2PL要求事务分成两个阶段加锁阶段和解锁阶段。一旦开始释放锁就不能再申请新锁。这个规则防止了“先读后写”的一致性隐患但也埋下死锁的雷。课程实验里通常要求实现超时检测或者等待图检测。我选择实现简单的超时每次等待超过500毫秒就主动回滚重新开始。虽然效率不高但能保证测试不会无限挂起。要注意的是回滚后之前持有的锁需要全部释放否则等待图会残留死锁。最好在事务结构里维护一个std::unordered_setlock_id回滚时遍历释放。不然你会看到日志里一堆事务卡在“Request timed out”但锁资源并没被释放最后整个数据库假死。5. 记录恢复机制与C11编程日志先行是可靠性的底线5.1 WAL的核心顺序先日志后数据数据库崩溃恢复最常用的手段是预写日志WAL。它的核心顺序是修改页面之前先把“我要把某个页的某个偏移写成什么值”这条日志刷到磁盘。这样即使数据页还没写崩溃后也能从日志重放。这份资源附带的sqlite3.c就是WAL的教科书级实现别当成普通SQLite源码看它里面封装了层层的日志逻辑。实现WAL时日志记录至少要包含事务ID、页ID、偏移量、旧值、新值、日志序号。每个事务提交时必须把该事务产生的所有日志刷盘再写commit记录。注意顺序不能反先写数据再写日志崩溃后日志里没有提交记录就会产生“数据变了但没有日志”的不可恢复状态。struct LogRecord { uint32_t transaction_id_; page_id_t page_id_; uint32_t offset_; const char *old_value_; const char *new_value_; uint32_t value_length_; uint64_t log_sequence_number_; // LSN单调递增 };这里的log_sequence_number_不只是用来排序还有一个用途是判断数据页是否已经应用了某条日志。每个页头可以记录page_lsn如果page_lsn log_sequence_number_说明这条日志已经作用过redo时跳过。这能避免重复日志导致的数据错乱。我在写恢复时曾经忘记检查page_lsn结果每次崩溃恢复后某些页的值比预期大了一倍。5.2 C11标准给数据库底层带来的原子操作C11标准给数据库开发最实用的东西是stdatomic.h里的原子变量和内存序。在无锁队列、原子计数、或者实现并发日志序列号时用atomic_uint64_t比加互斥锁性能高得多。比如分配LSN多线程同时写日志需要保证序号不重复。用atomic_fetch_add(lsn_counter, 1)一行搞定不需要把整个日志模块锁住。#include stdatomic.h atomic_uint64_t global_lsn 0; uint64_t AllocateLSN() { return atomic_fetch_add_explicit(global_lsn, 1, memory_order_relaxed); }memory_order_relaxed在这里够用因为LSN只要求唯一性不要求立即被其他线程看到全局顺序。但如果你要保护日志缓冲区到磁盘的写入顺序就需要memory_order_release和memory_order_acquire。初学阶段可以无脑用memory_order_seq_cst性能差一些但不会出低级错误。等跑通测试再回头调内存序。5.3 sqlite3.c和shell.c单文件数据库的模块化艺术sqlite3.c是合并版SQLite源码整个数据库引擎压缩在一个C文件里。这对学习模块划分很有价值虽然理论上所有函数都暴露在同一个编译单元但内部按sqlite3Btree*、sqlite3Pager*、sqlite3Vdbe*一套前缀体系划清了模块边界。你在写自己的实验时可以模仿这种命名法比如所有缓冲池函数加Buf*前缀所有B树函数加Btree*前缀。shell.c则是SQLite官方命令行工具它演示了如何通过C接口操作数据库。如果你把虚拟表代码编译进sqlite3shell.c就是天然的测试驱动。跑一个CREATE VIRTUAL TABLE ...就能验证你的B树是否正常。我一般会写一个小的自动化脚本批量往虚拟表里插入几千条数据再用shell查询比对结果。6. 避坑跑实验前先记住这五条血泪教训6.1 现象缓冲池替换时随机崩溃跑Buffer Pool测试时前99%的用例都过了可测试结束前突然段错误而且每次崩溃位置不同。原因是LRU替换器把正在被其他线程使用的帧给淘汰了。典型的实现里Evict()没有检查pin_count_或者检查了但没放进临界区保护。因为pin_count是共享变量两个线程同时改一个帧的计数导致用户态计数变成负数。解决方法是把pin_count用std::atomicsize_t声明并且替换时只在pin_count0的帧集合里选择。记住帧一旦被某个线程pin住即使它的访问历史再旧也不能被换出。6.2 现象B树插入后死循环插入过程中线程卡死在FindParentRecursively里CPU飙满。排查发现是根节点分裂后父节点的键数组和子指针数组长度不匹配。具体说新根只插入了一个键但子指针却有两个导致key_count_和children_.size()相差1。后续查找时二分懒散走到了一条没有对应键的子树上递归出不去。解决方法是每次分裂后断言内部页的键数量子指针数量-1如果不满足直接报错。用assert在debug构建里就能暴露问题。6.3 现象并发测试卡死锁管理器测试跑到中途所有线程阻塞程序不结束。原因是同一个事务在已经持有共享锁的时候又请求同一把锁的排他锁。按照2PL这属于锁升级但实现里没有区分“已持有”和“新请求”直接把第二个请求挂到等待队列里。而这个事务自己不会去释放第一个锁所以永远等自己。解决方法是LockExclusive开头先查txn_locks_是不是已经有了这个资源的锁如果有就先释放旧锁再升级或者直接返回成功并标记升级。我后来统一策略同一个事务请求锁如果已持有且模式足够就直接返回true绝不二次入队。6.4 现象恢复测试丢数据崩溃恢复后发现最后若干条已提交事务的数据没了。核心原因是提交日志没有强制刷盘。在TransactionCommit里如果只把日志写到内存缓冲区操作系统还没落盘就返回成功一旦断电缓冲区全丢。解决方法是调用fsync或fdatasync确保从日志模块到磁盘的链路真实写回。这里要注意SQLite对同步的粒度有PRAGMA synchronousFULL和NORMAL两种课程实验里只有FULL通过正确性测试。如果你用fwrite后没有fflush也可能被用户态缓冲区骗了。6.5 现象编译报C11兼容问题代码里用了std::unique_ptr、auto、nullptr但编译时提示找不到std::to_string。原因通常不是C标准问题而是编译器版本太旧或者Makefile里没开-stdc11。我遇到过某实验室的默认gcc还是4.8它不支持C14的很多特性需要升级。解决方法是把CMakeLists.txt里的CMAKE_CXX_STANDARD显式设为11同时检查代码里有没有std::make_unique这种C14才有的函数。如果必须兼容C11自己手写一个templatetypename T using unique_ptr std::unique_ptrT没有用因为std::unique_ptr本身就是C11的。重点是别用generic lambdas。7. 进阶验证用测试套件和性能剖析把代码钉死在正确性上跑完基础测试后我建议你做三件事。第一件事是用gtest/gmock写一个批量回归测试把b_plus_tree_test.cpp和lock_manager_test.cpp里的用例全部挂到同一个二进制里每改一处代码跑一遍。gmock-gtest-all.cc这份资源已经帮你把测试框架编译好了你只要写一个main函数调用RUN_ALL_TESTS()即可。我在实际项目里还会加一条随机数据测试随机生成10万条key随机插入删除最后做一次全量扫描验证顺序性。这比手写100个固定用例更能暴露隐藏问题。第二件事是用valgrind查内存问题。课程实验最恶心的就是内存泄漏特别是在B树删除合并后没有释放页对象。valgrind --leak-checkfull --error-exitcode1跑一遍如果退出码非0就直接拒绝上线。另一个工具是perf用于找热点函数。缓冲池的FetchPage如果频繁加锁性能一定上不去这时候可以把锁换成spinlock或者分区锁。第三件事是一个具体的性能验证实验先在缓冲池大小为200帧的情况下向B树插入20万条顺序递增的key然后再随机读取这20万个key记录每秒查询次数。你会发现顺序插入很快随机读取较慢。再用LRU-K替换器跑同一组数据对比命中率。如果命中率没提升说明你的K值设大了一般K2对于短周期热点最合适。自从某次因为没做性能剖析上线后数据库查询从毫秒变成秒我每次拿到新代码都会强制走一遍回归测试加valgrind加perf这三个步骤。顺序不能变变了你就会在内存泄漏和异常慢之间来回救火。希望帮到你。本文还有配套的精品资源点击获取

缓冲池、B+树、锁与日志恢复：数据库内核实验代码包实战

相关推荐

用Python绘制二维图：从选型到避坑的完整指南

Cursor Chat 功能实测：把 Base URL 改到 TaoToken 后，对话体验有多顺

CGCS2000行政边界数据处理实战：从Shapefile到GeoPandas

更多资讯

电商全类目属性SQL建模与递归CTE查询实战

基于YOLO的人群计数实战：从检测框到人数统计的调参与避坑指南

QT+SQL教室管理系统：排课冲突检测与数据库设计实战

Vue3响应式核心：ref与reactive的底层原理、应用场景及避坑指南

内存盘运行虚拟机：实时场景下的根文件系统加速实践

pstack-claude：Linux本地崩溃诊断的轻量级AI协作方案

今日更新

PHP htmlentities()函数用法讲解

AI Agent工程实战：从七要素到七个决策点的系统设计指南

AI入局芯片设计验证：验证收敛50倍加速的真相与应对

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？