如何设计存储引擎

从 MiniDB 的文件落盘开始，逐步长出页、记录、RID、空闲空间、Heap File、Buffer Pool 和脏页刷盘

阅读定位: 这页只讲数据库系统最底下的“数据怎么放、怎么取、怎么改、怎么刷盘”。它不展开 SQL 优化器、B+Tree 细节、完整事务隔离和 MVCC；那些应该在相邻下钻页继续讲。

一句话原则: 存储引擎不是“把对象序列化到文件”。它要在磁盘和内存之间建立稳定地址、可复用空间、可控缓存和可解释的写入顺序。

一、第一版：直接把行追加到文件末尾

MiniDB 最初只有一个目标：插入一条记账记录，重启以后还能读回来。最直觉的设计是 append-only 文件。

entries.heap [len=28][id=1, category=meal, amount=5600] [len=33][id=2, category=transport, amount=2300]

它解决了什么	马上暴露的问题	为什么这是存储引擎问题
重启以后可以顺序读文件恢复数据	按 id 查一行要从头扫到尾	记录没有稳定地址，只有“它大概在文件某处”
追加写很简单	更新只能追加新版本，旧版本越来越多	空间复用和旧记录失效要有规则
文件格式容易实现	删除后文件不会变小，也不知道哪里能再放新行	必须管理空闲空间，而不是只增长文件

阶段验收: 插入 1000 行后重启，数据能恢复；但你必须能解释为什么这还不是一个合格存储引擎：查找慢、更新膨胀、删除不回收。

二、第二版：给记录一个地址 RID

为了不每次从头扫描，记录需要一个地址。最粗暴的地址是文件偏移量：RID = file_offset。

方案	看起来的好处	一更新就坏在哪里
用 file offset 定位记录	索引可以保存 offset，直接 seek 到记录	如果记录变长，原位置放不下，移动后 offset 失效
更新时原地覆盖	短字段改短字段很快	变长字段、删除和碎片会让文件越来越难管理
删除时打 tombstone	不移动后续记录，offset 稳定	空洞越来越多，后续插入不知道怎么复用

这一步的教训: “地址稳定”比“能 seek 到”更难。数据库不能让外部引用因为一次 update 就全部失效。

三、第三版：文件切成 Page，RID 变成 page_id + slot_id

现在 MiniDB 把文件切成固定大小的 page。page 里不直接暴露字节偏移，而是暴露 slot。记录在页内移动，slot 不变，外部 RID 仍然稳定。

RID = (page_id=42, slot_id=3) Page 42: header: page_id = 42 free_start = 128 free_end = 3712 slot directory: slot 3 -> offset=3712, len=56, status=used data area: encoded record bytes

设计选择	解决的问题	验收问题
固定大小 Page	磁盘读写、缓存、刷盘都可以按页管理	读取一条记录时，是否能只加载它所在页
Slot Directory	记录可以在页内移动，RID 不变	压缩页内碎片后，旧 RID 是否仍可用
Free Space 指针	插入时知道页内哪里还能放记录	删除记录后，空间能否被复用
记录状态位	区分 used、deleted、redirected	扫描时是否会跳过已删除记录

四、第四版：变长记录让页开始变脏

真实业务里 category、note、merchant 这些字段都是变长的。更新备注时，记录可能从 40 字节变成 400 字节。原地放不下怎么办？

处理方式	适合什么	代价
页内移动并更新 slot	同一页还有足够空间	需要整理碎片，更新 slot offset
转发指针 redirected record	原页放不下，移动到别的页	读取多一次跳转，长期会增加碎片
溢出页 overflow page	超长文本、大 JSON、附件元数据	读取变复杂，删除要回收链路
限制行大小	第一版 MiniDB 保持简单	功能受限，但边界清楚

阶段验收: 把一条短 note 更新成长 note，再更新回短 note。页内空闲空间、slot、扫描结果都必须保持一致。

五、第五版：表不只是一个页，而是一组 Heap Page

一张表会有很多页。插入新记录时，MiniDB 要知道去哪一页找空间，而不是从第一页试到最后一页。

方案	怎么工作	什么时候会出问题
全表扫描找空页	从 page 0 开始找有空间的页	表一大，插入也变慢
Free Page List	维护“还有可用空间”的页链表	页空间变化时必须同步更新链表
Free Space Map	记录每页大概剩余空间	估算可能不准，但插入定位更快

HeapFile entries: header_page: page_count = 120 free_space_map = [ page 42 -> 1800 bytes free, page 88 -> 600 bytes free ] insert(row): need = encoded_len(row) page = find_page_with_free_space(need) insert_into_slotted_page(page, row)

六、第六版：热页不能反复从磁盘读，Buffer Pool 出场

存储引擎已经能管理页和表，但每次读写都访问磁盘仍然太慢。于是 MiniDB 在磁盘页和执行器之间加 Buffer Pool。

没有 Buffer Pool 的现象	Buffer Pool 的设计动作	要小心什么
同一页被反复读取	PageId 命中内存 Frame 后直接复用	必须维护 Page Table
执行器正在读的页被换出	pin count 大于 0 的页不能淘汰	执行器用完必须 unpin
内存满了不知道丢谁	用 Clock / LRU 找 victim	脏页淘汰前要先刷盘
修改页后马上刷盘太慢	标记 dirty，延迟刷盘	延迟刷盘会带来崩溃恢复问题

七、第七版：脏页什么时候刷盘

Buffer Pool 让性能变好了，但也制造了新风险：修改后的 page 可能只在内存里。什么时候写回磁盘？

刷盘时机	优点	问题
每次更新后立刻刷	崩溃风险小	性能很差，小更新会变成大量随机 IO
淘汰时刷	减少不必要写入	崩溃时内存里的修改可能没落盘
后台定期刷	平衡性能和风险	要控制刷盘节奏，避免集中抖动
checkpoint 刷一批	缩短恢复时间	需要和日志顺序配合

关键边界: 只讲存储引擎时，我们可以先说“脏页可能延迟刷盘”；但一旦涉及事务提交，就必须接入 WAL。否则 commit 成功但脏页未刷时，崩溃后状态不可解释。

八、第八版：最小崩溃实验

存储引擎页、Buffer Pool、脏页都设计完以后，要故意杀进程。没有崩溃实验，存储引擎只是“正常路径能跑”。

崩溃点	如果没有日志	这一页先给出的结论
记录写了一半	重启后可能读到半条坏记录	页需要校验、长度边界和坏页处理策略
页头更新了，slot 没更新	页内结构自相矛盾	页内修改也要考虑原子顺序
表页写了，索引页没写	表和索引不一致	跨页一致性必须交给事务和 WAL
dirty page 未刷盘	内存修改丢失	commit 语义不能只靠刷数据页

阶段验收: 这一页不要求你完整实现 WAL，但要求你能指出：哪些问题是存储引擎自己能处理的，哪些必须交给事务日志处理。

九、存储引擎 API 应该长什么样

到这里，执行器不应该知道页内 slot 怎么移动、Buffer Pool 怎么淘汰。它应该调用清晰的存储 API。

insert(table_id, row) -> RID read(table_id, RID) -> row update(table_id, RID, new_row) -> new RID or same RID delete(table_id, RID) scan(table_id) -> iterator<RID, row> fetch_page(page_id) -> pinned Page unpin_page(page_id, dirty)

API 设计点	为什么重要	坏设计长什么样
insert 返回 RID	索引需要保存访问路径	insert 只返回 true，后面不知道记录在哪
update 允许 RID 改变	变长记录可能移动	假设永远原地更新，遇到大字段就崩
scan 返回 iterator	执行器可以一行行拉取，不必一次加载全表	scan 返回整个数组，数据大时爆内存
fetch / unpin 成对	Buffer Pool 才知道页能不能淘汰	执行器拿到 Page 指针后忘记释放

十、把这一页收成一条设计线

阶段	遇到的问题	长出的设计	真正吸收点
Append 文件	查找慢，更新删除膨胀	记录地址	持久化不等于可管理
File Offset	变长更新导致地址不稳	Page + Slot	稳定 RID 是存储引擎核心
Slotted Page	页多了，不知道插入去哪	Heap File + Free Space Map	表是页集合，不是单个文件数组
Heap File	热页反复读磁盘	Buffer Pool	数据库有自己的内存层
Buffer Pool	脏页延迟刷盘带来风险	Dirty / Flush / Checkpoint 边界	性能优化会逼出恢复语义
正常路径能跑	崩溃时状态不可解释	接入 WAL / Recovery	存储引擎必须为事务日志留接口

十一、练习：用失败驱动实现

练习	故意制造什么失败	通过标准
实现 slotted page	插入 3 条变长记录，删除中间一条，再插入更短记录	slot 稳定，扫描正确，空闲空间复用
实现 heap file	连续插入直到跨多个页	能通过 RID 读回每条记录，插入不会总扫全表
实现 Buffer Pool	只给 2 个 frame，反复访问 5 个 page	pin 页不被淘汰，dirty 页淘汰前刷盘
实现 update	把短记录改成长记录，再改短	RID 规则清楚，旧空间不泄漏
实现崩溃测试	写页过程中强制退出	能识别坏页或明确说明必须依赖 WAL 恢复

十二、回到主线

如何设计一个数据库

这页是 MiniDB 主线里的第一张下钻页。如果你想回到全局故事，回到如何设计一个数据库。

如何设计 B+Tree 索引

存储引擎解决“记录怎么稳定放在页里”，下一步可以继续看如何设计 B+Tree 索引，把“怎样快速找到记录”拆成叶子页、内部节点、分裂和回表。

如何设计 WAL 和崩溃恢复

当表页和索引页都可能被修改时，跨页一致性和崩溃恢复必须交给如何设计 WAL 和崩溃恢复继续处理。

总结: 存储引擎不是概念堆，而是一连串被失败逼出来的设计：append 文件查找慢，file offset 更新不稳，于是有 page 和 slot；页多了插入慢，于是有 heap file 和 free space map；热页反复读磁盘，于是有 Buffer Pool；脏页延迟刷盘，于是必须给 WAL 和恢复留下接口。