2.3 记录页面的设计模式-变长记录
记录储存格式
我们提供一种 (NULL位图, 定长数据, 可变列的偏移数组, 变长数据) 的格式存储变长记录。以0.2提到的course表中 (30240262, 'Database', 2) 的一行为例：
| 0 (1B) | 30240262 (4B) | 2 (4B) | 19 (2B) | 'Database' (8B) |
NULL位图和定长数据部分与定长记录相同；可变列偏移数组的长度为 2字节*可变列数，从而在变长部分区分出各可变列的数据。在本例中，19为第一个变长列结束的位置。由于其也是最后一个变长列，所以19也表示本行的长度。
页面布局
页头需要存储槽容量 (有效槽+无效槽总数) 辅助解读页面字节序列，还需要存储空闲空间的字节偏移量和空闲字节数目便于空闲空间管理。解读页面还需要定长部分 (NULL位图+定长数据) 长度、可变列数目等信息，可以保存在页头，也可由表的元数据推算得到。
页身从前向后存储数据，从后向前存储槽目录，槽目录存储记录的字节偏移量。槽目录可以每2字节对应从0开始的自然数槽号，这样在通过槽号访问某槽时只需要O(1)时间，但在插入记录时最好在槽目录中从后向前优先利用无效槽号；也可以在槽目录中只存储有效槽号，不过在通过槽号访问某槽时需要遍历槽目录。某条记录的页号和槽号建议不要轻易修改，否则相关的索引也要修改。
删除记录时可能产生碎片空闲空间，在数据量较小时不处理也无妨。在真实数据库中会有程序定期清理碎片空间，使页内空闲空间尽量连续。
空闲空间管理
我们介绍几种常用的管理页面空闲空间的方式。
链表
与定长记录类似，页面的空闲空间最大为 4096-64 字节，可以按照一定字节数 (如：32字节) 为单位将空闲空间大小分成若干个级别，每一级别维护一个链表。
页目录
可以保留一些页作为页目录而不作为数据页，页目录之间通过链表相连；每个页目录记录若干页的空闲空间大小。
大根堆二叉树
可以为每个表创建一个文件管理表的空闲空间。每个FSM页内为一棵大根堆二叉树，叶节点记录某页的空闲空间大小 (也可以将空闲空间大小分成256个级别，使每个节点仅占用1B)，非叶节点记录两个孩子中的较大值。这样，在需要一定空闲空间大小时，仅比较根节点即可判断表内是否有页面满足要求，然后沿二叉树逐级比较向下直到叶节点，即可找到合适的空闲页面。
如果页面较多，可以构建多级FSM页，高级FSM页的叶节点对应低级FSM页的根节点，且它们具有相同的值。
假设每个页面数据区大小为10B，则每个页面内可以构建出有4个叶节点的满二叉树；假设共有3级FSM页，例：
0 <-- page 0 at level 2 (root page)
0 <-- page 0 at level 1
0 <-- page 0 at level 0
1 <-- page 1 at level 0
2 <-- ...
3
1 <-- page 1 at level 1
4
5
6
7
8
9
假设命中了8号页内数据区偏移量为5的字节，由 n+⌊n/4+1⌋+⌊n/4^2+1⌋=8 解得 n=5，即8号页对应0级5号页；偏移量为5对应FSM页内1号叶节点。由 5*5+1=26 知对应表内26号页。
大根堆二叉树也可以参考PostgreSQL中相应说明。