derbydb的page结构

 

 

 

page是数据库在disk层面的最小存储单元。记录被组织在page中，数据库对磁盘的读取，也是以page为单位。因此，研究page的结构是研究数据库实现的基础。我们可以看一下derbydb的page结构。

 

Derby的page由StoredPage封装。该类维护了page的字节数组（rawDataIn/rawDataOut），并提供了基于DataInput/DataOutput的接口用于访问磁盘。

 

page结构：

 

    +-----------+-------------+----------+-------------------+----------+

    | format id | page header | records  | slot offset table | checksum |

    +-----------+-------------+----------+-------------------+----------+

 

简单地讲，一个page被划分为多个slot，每个slot存储一个record。我们可以把page当作储物柜，一个储物柜被划分为大小不一的格子，每一个格子就是一个record空间。slot offset table保存了records的索引。

 

-- format id

 

    format id是一个4字节的数组，存储了这个page的format id。

 

-- page header

 

    page header的固定长度是56字节。下面是每一个字节的含义：

 

    1 byte  boolean        标识该page是否是一个溢出的page

    2 byte  byte           page的状态

    8 bytes long           page的版本号

    2 bytes unsigned short slog offset table中的slot数目

    4 bytes integer        下一个记录的标识符

    4 bytes integer        该page的代号（未来使用）

    4 bytes integer        该page的上一代号（未来使用）

    4 bytes integer

    2 bytes unsigned short 该page中被删除的行数

    2 bytes unsigned short 为修改用的空闲空间百分比

    2 bytes short          空闲区域，未来使用

    4 bytes long           空闲区域，未来使用（加密算法会写一个随机数到该字段）

    8 bytes long           空闲区域，未来使用

    8 bytes long           空闲区域，未来使用

 

    这里需要指出的是，空闲区域被写入的是0。

 

-- records

 

    records区域用于保存record数据，record记录可以是零个或多个。

 

    在描述records区域之前，我们需要关注一个变量：minimumRecordSize。该属性定义了最小的用户记录长度，这个长度不包括数据库系统添加的record头和字段头。我们可以认为，当一个record被插入时，record总共所需的最少字节数是minimumRecordSize与数据库添加的头长度之和。

 

    举个例子：

 

    假设minimumRecordSize为10。

 

    如果用户的记录长度为7字节，我们使用5字节保存record头和字段头信息，那么被写到磁盘的record实际上占用15字节（10 + 5）。其中，3个字节是空的。

 

    如果用户的记录长度为17字节，我们使用5字节保存record头和字段头信息，那么被写到磁盘的record实际上占用22字节（17 + 5）。

 

    +-------------------------+

    | record1 | record2 | ... |

    +-------------------------+

 

-- slot offset table

 

    正如该区域的名字所指出的那样，该区域保存了每一个record在page的偏移量信息。该表的每一个元素对应每一个record。每一个元素的长度是6或12字节，这个长度取决于page是否小于64K。

 

    每一个元素包括下面几部分：

 

    * 2字节（unsigned short）或4字节（int）的页偏移量。

    * 2字节（unsigned short）或4字节（int）的record长度。

    * 2字节（unsigned short）或4字节（int）的多余空间。

 

    StoredPage的变量slotTableOffsetToFirstEntry定义了第一个slot元素在page的起始位置，可以认为是整个slot offset table的偏移量。这里有一个很有意思的事情是，slot offset table的元素是从后往前写的。所以，一个slot offset table的结构大概是：

 

    +-------------------------------------+----------+

    | ... | slot3 | slot2 | slot1 | slot0 | checksum |

    +-------------------------------------+----------+

 

    | <------   slot offset table   ----->|

 

-- checksum

 

    每个page的最后8字节是校验和。这个校验和是利用java.util.zip.CRC32对整个page计算得到的。

 

StoredPage

 

    前面说到StoredPage封装了一个page的信息，并且提供了众多和外界交互的接口。我们首先考察StoredPage封装的重要数据。

 

    slotsInUse:

 

    是一个整型变量，标识这个page拥有的record数量。这个变量被存储在page的头部，当page从文件读出时，这个变量会从page头读出。

 

    headers:

 

    headers是一个元素为StoredRecordHeader的数组。当page从文件读出时，headers会根据slotsInUse初始化。所以，可以认为，在任意时刻，headers的长度和slotsInUse相同。

 

    pageData:

 

    是一个字节数组，保存了该page的所有原始数据。当一个page从磁盘加载进内存时，这个数组会被初始化。

 

    setIdentity(Object key):

 

    setIdentity方法根据一个PageKey，从FileContainer读取该page的所有数据，并初始化一些实例变量。实际上StoredPage继承了CachedPage，setIdentity方法定义在CachedPage，setIdentity会调用定义在StoredPage的initFromData做真正初始化的动作。