[数据库理论]slotted-page structure

这篇文章中主要介绍一下数据库中常用在动态分配空间的一种数据结构
--- slotted-page structure （分页槽结构体）
在数据库中，用于组织、存放数据的记录结构体有两种，一种是变长类型的记录，
一种是固定长度类型的记录。固定型的暂不讨论，变长型记录（Variable-Length Records）
变长的方式有如下三种：（根据存放数据的单位大小的不同而不同）
1. 在一个数据文件中存放多种类型的文件 -- 以数据文件为单位的变长
2. 在一个记录中可以存放多种不同长度的域( 记录： records 通常是数据库表中的一行，
域:fields 通常是数据库表中一行中的一个字段 ) --以记录变长为单位
3.  在一个记录中可以存放重复的域，比如说一个域的类型可以是数组或是集合 --以记录为单位的变长
slotted-page structure 便属于前一种， 它通常用于在一个数据块中组织数据。
在每个数据块的起始处有一个记录头，在记录头中通常包含有记录下面三种信息的变量字段：

1. 在这个块中总共包含了多少个记录项(record)
2. 块中的空闲空间结束地址
3. 包含有每个记录项(record) 在系统中存放确切的地址信息和该记录项的长度

第三条相当于告诉使用者，在这个块中指向每个记录项 (record) 的指针和需要访问该整个记录(record)
指针需要移动的位置

下面的图示简单描绘了在 slotted-page structure 中空间的分配状况


记录在 block 中从block 结构体的结尾的地址处连续的分配。
块(block) 中的空闲空间也同样是连续的，空闲空间位于头记录中用于记录块中每个记录
位于块中的具体位置的地址链表与最新被分配空间的记录项之间。
也就是说大致的过程是这样的：

(块开始地址)|记录项信息链表的增长方向 --->| (头)空闲空间(不断减少) (尾) |<--- < 记录增长的方向 记录头|(块结尾地址)

如果是向这种结构中插入一个记录项的话，
1. 首先在空闲的结尾处为其分配一块用来存放记录项的空间 
2. 然后包含了该记录项所在的(起始地址的信息,记录项长度) 的记录被作为一个小记录单元
  被插入到记录项信息链表中

如果想从这种结构中删除一条记录项的话，
1. 首先将该系统为记录项在块中分配的空间进行释放
2. 然后将记录项信息链表中的小记录删除，将其值置为-1 或者是使用其他的方法，使用户无法访问即可。

记录项也可以在原先的基础之上进行扩充空间和缩减空间，扩充空间的话只要空闲空间足够有即可。
因为这种组织方式是在块中进行的，块的大小与操作系统的页面大小，和操作系统的内存
与磁盘交换数据的单位页的大小大体上都是一致的。
所以可推知块的大小大概是 4 到 8 kb ，基数就小，所以在块内的记录之间移动指针扩容，缩容
所消耗的代价并不大。

这种分页槽结构体的实现没有让指针直接指向记录项，如果想要访问记录中的内容的话，则必须要
先通过指向头记录中的小记录中的指针，通过小记录中的(指向block 中记录的指针，记录长度）
来实现对记录的访问。
这种间接访问使用指针的方法实现了让指针只游走于一个快结构体中，不会造成指针越位访问
而造成的错误。

我们回过头来再来看引出这个话题的，源码中的数据结构的代码：

struct dmsPageHeader
{
   char _eyeCatcher[DMS_PAGE_EYECATCHER_LEN] ;
   unsigned int _size ; // 记录了block 的总长度
   unsigned int _flag ; // 标识符，用于标示该block 是否被 dropped
   unsigned int _numSlots ;  // 该变量用于记录在 block 中一种有多少个槽位 ，
                            //  这里的槽 = 上文所说的 record
   unsigned int _slotOffset ; // 这个变量用来标定的是 槽 距离结构体的起始位置是多少
   unsigned int _freeSpace ;  // 这个变量用来记录的是，这个block 中的空闲 空间的地址是多少
   unsigned int _freeOffset ; // 这个变量用于记录的是 空闲空间在 block 中的起始地址是多少
   char _data[0] ;            // 这个变量用于记录的是 record 也就是实际存放数据的空间
                              // 虽然看起来只是一个字节，是可以作为地址指针来使用的，现用现申请
                              // &dmsPageHeader->_data[0] = (...)malloc() ;
} ;

理论与实践之间多多少少还是有些不同的， 多半是因为这个结构体变长的还不够，
槽位个数固定，槽位的大小也是固定的， 所以在头文件中无需组织一个链表这样的结构体，
因为个数固定，所以block 的大小也就基本定了， 而槽位大小固定，那么知道了首地址之后，
每次将指针向后依次移动一个槽位大小便可以依次访问每个槽（record）中的数据了。
同时 _numSlots 记录了一共有多少个 槽， 一个循环便可以搞定。