MiniDB 是一个纯 Python 写的小型关系数据库，目标是“行为和 SQLite 一模一样”。这篇讲最底下的两层：数据怎么按页放在文件里，B+ 树怎么在这些页上长出来。
文件是一串 4 KB 的页#
数据库文件被切成固定 4096 字节的页。第 0 页是文件头：magic 字符串、页总数、空闲页链表的头、一个每次提交加一的变更计数器。删除数据释放出来的页挂在一条单链表上（每个空闲页的前 4 字节是下一个空闲页的页号），分配新页时先从链表上拿，不够才在文件末尾追加。
每页最后 4 字节是前 4092 字节的 CRC32。读页时校验，对不上就报 database disk image is malformed，而不是把坏数据当真——比起“返回错误结果”，报错要好得多。为此还写了“随机翻转文件里的字节”的模糊测试。
缓存解码后的页对象，而不是字节#
第一个有意思的决定在 pager（页缓存）里：缓存的是解码后的页对象，不是原始字节。每种页类型实现from_bytes() 和 to_bytes()，只在写回磁盘时才序列化。这样 B+ 树可以直接在 Python 列表上 bisect，不用每次访问都把一整页解析一遍——在 Python 里这是数量级的差别。
代价是一个约定：修改页之前必须先调用 pager.write(page)。这个约定后来变成了好几个机制的挂钩点：语句级回滚在这里保存页的前像，事务在这里记录脏页，WAL 在这里知道哪些页要写进日志。
B+ 树按字节判断“满”#
教科书上的 B+ 树按 key 的个数判断节点满不满。MiniDB 按序列化后的字节数：节点超过容量就分裂，低于容量的 1/4 就向兄弟借或合并。这样整数 key + 变长行的表树、变长 key 的索引树能共用同一份代码。
为了保证分裂、借位之后两边都不低于下限，单个 cell 不能太大（不超过容量的 1/5）；更大的值放进 overflow 页链，cell 里只存长度和首页号。索引的 key 一开始有长度上限，后来也支持了 overflow——但没有用“截断前缀、再回表复核”这种省事的办法，因为那样索引顺序就不精确了，会连带破坏覆盖索引、按索引顺序免排序和 UNIQUE 判断。
两个小技巧：
- 根页号终生不变。根分裂时把根的内容搬到新页，根页变成新的内部节点；根只剩一个孩子时把孩子拷回根页。于是 schema 里记的根页号不用随插入删除更新。
- 顺序追加时不均匀分裂。自增 rowid 总是插在最右边，50/50 分裂会让每页只有一半满。改成新 key 落在最右叶子末尾时左节点保留约 75%，10 万行的文件从 23.5 MB 降到 17.1 MB。
测试 B+ 树时有一个很好用的开关：BTree(..., capacity=128) 让节点只用页里的 128 字节，一万条数据就能长出五层以上，所有分裂、合并、借位、根分裂的路径都能覆盖到。生产代码永远是 4096。
记录格式#
一行记录的格式改过三次。现在的版本是：头部每列一个类型码（1/2/4/8 字节整数、零字节的 0 和 1、短文本的长度直接编码在类型码里），后面是负载。每种不同的头部只编译一次成 struct.Struct 加一个生成的组装函数，于是解码一行就是一次 C 调用：10 万行的解码从 0.28 s 降到 0.03 s，文件从 23.6 MB 降到 15.7 MB。
表的 key 是 rowid；INTEGER PRIMARY KEY 是 rowid 的别名（值放在 key 里，记录里对应位置存 NULL）。索引的 key是“各列值的 SQLite 排序键 + rowid”，rowid 保证唯一，排序键保证 B+ 树的顺序和 SQL 比较的顺序一致（NULL < 数 < 文本 < BLOB，1 和 1.0 相等）。
能看见的 B+ 树#
Playground ↗ 里右边那棵树就是这些页：每个方框是一页，显示页号、key 个数和填充率，叶子之间的虚线是兄弟指针。插入两千行，可以看到根节点下面挂着二十个左右的叶子，每页一百多个 key；索引树的 key 显示成 值 | rowid。
对应的决策#
D4（页对象缓存）、D5（文件头与空闲页）、D7（按字节分裂）、D8（根页号固定）、D9（可调容量）、D10 / D57（overflow）、D38（不均匀分裂）、D47（页校验和）、D58（记录格式 3）、D30（索引 key）。
代码、测试与文中引用的设计决策（D 编号，见 DECISIONS.md）：github.com/ayaya114514/MiniDB ↗；浏览器里直接试：MiniDB Playground ↗。