Cell Layout

通过 flags 标志、enums 枚举跟基础类型我们就可以开始设计 Cell 的布局了，然后再使用 Cell 来构建页，最后用页来组成整棵树。在 Cell 级别，我们将它分成 Key 跟 Key-Value 两种 Cell。Key Cell 保存 Key 跟指向页面内对应位置的指针。Key-Value Cell 则保存了 Key 与其关联的数据记录。

我们假设页面内的 Cell 都是均匀的 (举例来说，所有的 Cell 都能够同时保存 Key 或者是同时保存 Key 跟 Value；类似的，所有的 Cell 都可以保存固定长度跟可变长度的数据，但不能同时保存两种)。这意味着我们可以在页的级别上存储描述 Cell 的元数据，而不是记录在每个 Cell 中。

为了构造一个 Key Cell，我们需要知道下面这些信息

Cell 类型 (可以通过页的元数据得到)
Key 的大小
该 Cell 所指向的子页的 ID
Key 字节数据

可变长度的 Key Cell 的布局看起来应该像这样 (固定长度的则不需要在 Cell 级别上保存长度信息)

0               4              8
+---------------+--------------+------------+
|[int] key_size |[int] page_id |[bytes] key |
+---------------+--------------+------------+

我们将固定长度的数据字段整合到了一起，然后后面再附加 key_size 个字节。严格意义上来说并不是一定要这样处理，但这样可以帮助我们简化偏移量的计算，因为所有固定长度的字段可以使用静态的、预先算好的偏移量来访问，唯一需要计算偏移量的就只有可变长度部分的数据了。

Key-Value Cell 的话，除了不保存页的 ID，而是换成保存具体的数据记录之外，其他的部分都是类似的

Cell 类型 (可以通过页的元数据得到)
Key 的尺寸
Value 的尺寸
Key 字节数据
数据记录的字节记录

0            1              5                9           .. +key_size
+------------+--------------+----------------+-----------+-------------------+
|[byte]flags |[int]key_size |[int]value_size |[bytes]key |[bytes]data_record |
+------------+--------------+----------------+-----------+-------------------+

你应该注意到了其中偏移量跟页面 ID 的区别。因为页都是固定尺寸并且通过页缓存进行管理的，我们只需要存储页的 ID，在之后就可以通过这个 ID 从查询表中找到真实的偏移量。Cell 的偏移量都是相对于当前页面的起始地址：这让我们可以使用更小的数值来表示偏移量，以此保持结构更紧凑。

Variable-Size Data

在 Cell 中使用固定大小的 Key 跟 Value 并不是必须的。Key 跟 Value 都可以有可变的长度。因为可以依据页的头部大小来算出他们的具体偏移量。

我们可以通过跳过头部然后读取 key_size 个字节来定位 Key，类似的，我们可以通过跳过头部然后再跳过 key_size 个字节后再读取 value_size 个字节来定位 Value。

还有许多其他的方法可以达到一样的目标，比如，通过存储整体大小然后通过减法来计算出 Value 的大小。只要我们有足够的信息来记录对 Cell 的切分，就能够重新构建出所需的数据。