文件格式

一句话

你以为「文件格式」是字节怎么摆的琐碎收尾，其实它是上一章那棵漂亮的 B-Tree 能不能在真硬件上跑起来的落地层。这一章的核心命题只有一句：内存里由分配器、指针和垃圾回收替你做的三件事——放下变长对象、回收释放的空间、稳定地引用一个对象——到了磁盘上都得自己重造一遍。重造出来的产物，就是本章的全部内容：定长的页、页内的槽目录（slotted page）、装数据的 cell、管空洞的空闲清单，外加认得出自己的版本号与发现得了损坏的校验和。

Glossary · 术语表

坐标

本章是《Database Internals》Part I「存储引擎」的第 3 章。上承第 2 章——那一章论证了 B-Tree 为什么是磁盘上的默认答案，但只画了树的形状，没说「一个节点在磁盘上到底长什么样」；下启第 4 章「实现 B-Tree」的分裂、合并、并发与页管理，那些操作全部建立在本章的页布局之上。对应现实：你用 PostgreSQL 的 pageinspect 扩展 dump 出来的那一页、InnoDB 的索引页、SQLite 文件里的 b-tree 页，就是这一章的实物。

这章要解决什么

根子是：内存的编程模型和磁盘的编程模型在四个地方断裂了，而我们习惯的数据结构全是照着内存那套写的。粒度——内存按字节随机访问，磁盘只能整页来回，而一次随机 I/O 的代价基本与你要 1 个字节还是 8 KiB 无关（NVMe 上几十到上百微秒，机械盘上 5–10 毫秒），于是「页里怎么排」直接决定一次 I/O 换回多少有用数据。引用——内存指针是虚拟地址、重启就废，磁盘上必须换成能持久保存的坐标「页 ID + 页内偏移量」。分配与回收——没有 malloc/free、没有垃圾回收，删除留下的空洞得自己登记、自己复用、自己整理。可信度——内存里读到的基本就是写进去的，磁盘上不一定：位翻转、写错地址、撕裂写，都会还你一坨看起来完全合法的垃圾。

不解决会怎样？给个量级：若图省事让每条记录占一个定长槽位，槽位得按最长记录定，比如 512 字节；一条 80 字节的订单占满整格就浪费 84%，8 KiB 的页只装得下 16 条。反过来，若让变长记录按键紧密排列，中间插一条就得 memmove 几 KB，删除留下的洞还永远回不来。本章要找的，是同时躲开这两种蠢的排法。

表 1 · 内存里免费、磁盘上必须自建的四件事

核心内容，讲透

一、先把数据变成字节：定长、变长与位打包

最底下一层是二进制编码（binary encoding）：一个值怎么变成一串字节。定长的数字按固定宽度写，但字节序必须在格式里定死。磁盘格式偏爱大端（big-endian，高位字节在前，也叫网络字节序），理由很实际：大端存的无符号整数，按字节逐位比较的结果就等于数值比较的结果——键可以直接 memcmp 比大小，不必先反序列化。SQLite 的文件头就明文规定：多字节字段一律大端。

变长的数据（字符串、blob）有两条老路：C 风格的结束符（读到 \0 为止——得逐字节扫，内容里还不能出现 \0），和长度前缀（先写长度再写内容）。数据库一律选后者：读之前就知道有多长，能一次读完，也能直接跳过。位打包用来省那些只有几种取值的字段——PostgreSQL 的行头就带一个 null bitmap，每列 1 bit 记「这列是不是 NULL」。

二、文件的骨架：魔数、版本、定长页

再往上是文件整体：头部 + 一长串等长的页。头部放全局信息——魔数、格式版本、页大小；SQLite 的文件前 16 个字节永远是 SQLite format 3\0。为什么非得定长页？因为定长意味着第 n 页在哪 = n × 页大小，一次乘法就寻址，不需要任何「页目录」式的间接层，也让页缓存里的槽位可以随便互换复用。这是整套设计里最不起眼、却最省事的一条约束。

三、slotted page：这一章的心脏

现在到了本章的主角。设计一个页内布局，要同时满足三个诉求：

• ① 存变长记录，且额外开销要小；
• ② 删除的空间能回收再用；
• ③ 引用一条记录时不暴露它的物理位置——否则页一压缩、记录一挪窝，所有指向它的引用就全废了。

槽式页（slotted page，也译「带槽的页」）一次性接住这三条：一页切成三段——页头、从页首往后长的槽目录（一串定长的偏移量，通常每个 2 字节）、从页尾往前长的 cell 区，中间夹着空闲空间。两端相向生长，页头记两个偏移量圈出这块空白的上下界；两个指针撞上了，就是这一页满了。

于是三个诉求各自落地：插入就是把 cell 写进空白区的尾端，再往槽目录里加一个偏移量——变长记录只占它实际需要的字节，加上 2 字节槽位和一个小 cell 头，开销可以压到个位数字节（诉求 ①）。删除把槽标为无效、把 cell 那段空间挂进空闲清单等待复用（诉求 ②）。而槽号是稳定的对外身份——记录在页里挪了位置，只要更新槽里的偏移量，外面拿着「页 ID + 槽号」的引用就完全不必改（诉求 ③）。

PostgreSQL 是这套结构的教科书实物：一页默认 8 KiB，开头 24 字节的页头，随后是每个 4 字节的行指针（ItemIdData，就是槽）从前往后排，元组从页尾往前塞，页头里 pd_lower / pd_upper 两个 2 字节的偏移量正好圈出中间那块空闲区。

四、逻辑序与物理序解耦：为什么插入不用搬家

这是 slotted page 最漂亮、也最容易被读过就忘的一点。B-Tree 要求节点内的键有序，才能在页里二分查找。天真的做法是让 cell 在页里就按键排好——那么往中间插一个键，就得把它后面几 KB 的字节整体后移。

真实做法是：让槽目录有序，cell 物理上随便乱。插入一个中间键时，cell 追加到空白区尾端（谁都不用动），只在槽目录里 memmove 一小段偏移量。算一笔账：一页 8 KiB 装 100 条记录，最坏情况要挪 100 × 2 = 200 字节的偏移量，而不是几 KB 的记录本体——便宜一个数量级以上，而且挪的是缓存友好的连续小数组。查找时也是在这个有序小数组上二分，每一步再顺着偏移量跳过去读键。

顺带一提，InnoDB 走的是个值得对照的变体：记录之间用「下一条」指针连成一条按键有序的单链表，页里的 page directory 只做稀疏索引——每个槽罩住 4–8 条记录。查找先在稀疏目录上二分定位到大致区间，再沿链表线性走几步。目录小了，代价是多几次指针跳转。同一个问题，两种合理答案，这就是本章反复示范的那种权衡。

五、cell 里装什么：两种 cell 与放不下的大对象

B-Tree 有两种节点，页里也就有两种 cell。分隔键 cell（key cell）只装「键 + 子页 ID」，用于内部节点导航；键值 cell（key-value cell）装「键 + 数据」，只出现在叶子。为什么要分？因为内部节点只需要路标，不必背 payload——同样一页能塞下的分隔键就更多，扇出（fan-out）更高、树更矮，正好接上第 2 章那个「31 层塌成 4 层」的结论。cell 的小头部记下自己的总长、键长，以及值长（叶子）或子页 ID（内部），变长字段跟在后面。

那一个值大到一页都装不下怎么办？两条路：其一是溢出页（overflow page）——cell 里只留前一段和一个指向溢出页的指针，剩下的内容串成一条页链，SQLite 就这么干；其二是挪到旁路存储——PostgreSQL 的 TOAST：一行宽过约 2 KB（TOAST_TUPLE_THRESHOLD）就先压缩、再把大字段切块搬进一张附属表，行里只留一个指针。目的是保证 8 KiB 的页至少还能装下 4 行——毕竟一页只装一行的树，扇出低得没法看。

六、空洞、空闲清单与页内压缩

删除一条记录，通常不立刻搬家：把它的槽标为无效，cell 占的那段空间挂进一张空闲清单（availability list / freelist）——每段空洞的头部记下自己的大小和下一段空洞的偏移量，串成一条链。下次插入先在链上找一段够大的：首次适配（first-fit）拿第一个装得下的，快，但常把一大段切剩一点点；最佳适配（best-fit）扫完整条链挑最贴身的，省空间，但要遍历、剩下的边角更小更没用。SQLite 把这些空洞叫 freeblock，还在页头单记一个「零碎字节数」——那些小到连挂进链表都不值当的边角料。

等碎片攒到某个阈值——空闲总量够，却没有一段连续放得下新 cell——就触发页内压缩（defragmentation / compaction）：把所有存活 cell 重新紧密码到页尾，同步更新槽目录里的偏移量。代价是整页重写一次，收益是把散碎空间攒回一整块。诉求 ③ 的价值在这一刻兑现：压缩把每个 cell 都挪了窝，但槽号没变，页外所有引用毫发无伤。

七、认得出自己、也发现得了损坏：版本号与校验和

最后两个不起眼却救命的字段。版本：格式一定会变，文件必须自报家门，否则新版程序读老文件就是灾难。Cassandra 干脆把版本写进 SSTable 的文件名——nb-1-big-Data.db 里的 nb 就是格式版本、big 是格式类型，不打开文件就知道该用哪套读法。

校验和：写页时算一个短摘要存进页里，读回来重算一遍，对不上就说明这页坏了——防的是位腐烂、写错地址，以及断电时只写了半页的撕裂写。三点要记住：它防意外不防恶意（不是加密哈希，能改数据的人也能改校验和）；它只在你读到这页时才发现问题（所以认真的系统还会定期主动扫盘，叫 scrubbing）；它管不到内存里的损坏——数据在页缓存里被写坏，照样会带着「正确」的新校验和落盘。

关键权衡与选型

表 2 · 页大小怎么选（括号内为真实默认值）

表 3 · 页内怎么摆变长记录：三条路线

表 4 · 空闲空间怎么管

为什么重要 / 落到真实系统

这一章有三个很具体的兑现口。排障时看得懂：「删了一半数据，表文件为什么一个字节都没小？」——删除只是标记 + 挂空闲清单，复用发生在页内，文件不会缩；PostgreSQL 里得等 VACUUM 把死元组的空间还给页，只有 VACUUM FULL 重写整表才真的缩文件。建模时知道边界：行宽越过约 2 KB，PostgreSQL 就把字段挪进 TOAST 表，本来一次 I/O 拿到的行变成两次——「往主表塞大 JSON」在压测里的断崖不是玄学，是页装不下了。评审和面试时说得清：「B-Tree 页内插入是 O(n) 搬移吗？」——搬的是槽目录里的偏移量，不是记录本体。

易错点与争议

• 把 slotted page 当「数据库的通用页格式」。它是可变、原地更新那一派的答案。LSM 一侧的 SSTable 写完就不再改，根本不需要页内回收机制，空间靠整文件合并释放；列存（Parquet / ORC）则按 row group + column chunk 组织，目标是扫描时只读用得上的列。页格式跟着存储模型走，没有一种通用布局。
• 把槽目录当索引。它只在一页之内定位，页与页之间的导航仍然靠 B-Tree。一页 8 KiB 里二分几步，和跨百万页找一条记录，是两个量级的问题。
• 以为删除立刻腾出磁盘。删除通常只是标记 + 挂空闲清单；空间要等页内压缩才可复用，文件大小往往纹丝不动（PostgreSQL 里还得等 VACUUM，只有 VACUUM FULL 才真的缩文件）。
• 把校验和当完整性保险。它不是加密哈希，防不了有意篡改；只在读到时才校验，坏页可能躺很久；也管不到内存中的损坏。要真做到「读到的就是写进的」，还得配主动扫盘与备份校验。
• 「把内存结构原样落盘」的诱惑。直接 mmap 一个 C 结构体最省事、最快，但格式就此绑死在这台机器的字节序、对齐规则甚至编译器版本上，换个平台就读不了。Petrov 的立场很明确：每个字节都显式定义——这也是主流格式都自己规定字节序的原因。
• 时代局限与争议。本章的前提是「块设备 + 定长页 + 改一点也要整页读写」。近年 NVMe 的原子写、Zoned Namespace（ZNS）盘，以及各类「只顺序整段写」的设计，都在动摇其中几条假设。另一边，页大小无普适最优却常被做成刚性选择：PostgreSQL 的 8 KiB 是编译期常量，想换得重编译并重建集群——这个僵硬本身就是长期被诟病的点。

要点