数据库的存储结构

文件的分页

DBMS最常见的做法是将数据库以文件的形式存储在磁盘上。有些DBMS可能使用一组文件来存储数据库，有些DBMS可能只使用单个文件。

从操作系统的角度来看，一个文件就是一个字节流序列，操作系统并不关心和了解文件的内容以及文件之间的关联性。数据库文件的内容只有创建它的DBMS才知道如何解读，因为它是由DBMS以其特定的方式来组织的。

数据库文件的组织和管理由DBMS的存储管理器负责，它将文件划分为页面的集合，并且负责跟踪记录这些页面的使用情况，包括哪些页面存储了什么数据，哪些页面是空闲的等等。页面中可以存储不同类型的数据，比如记录、索引等，但是DBMS通常不会将不同类型的数据混合存储在同一个页面中。

页面标识

每个页面都有一个唯一的标识符。如果数据库是单个文件，那么页面ID可以直接映射为文件内的偏移量；如果数据库包含多个文件，则还需加上文件标识符来进行区分。大多数DBMS都有一个间接层，能够将页面ID（pageid）映射为文件路径(path->fd)和偏移量(offset)。系统上层模块请求一个页面时，先给出页面ID(pageid)，存储管理器将该页面ID转换为文件路径和偏移量，并由此定位到对应页面。

页大小

大多数DBMS使用固定大小的页面，因为支持可变大小的页面会带来很多麻烦。例如，对于可变大小的页面，删除一个页面可能会在数据库文件中留下一个空缺，而由于页面的大小不等，这个空缺位置很难被一个新页填满，从而导致碎片问题。

大多数数据库默认使用4~8KB的页大小，但是许多数据库允许用户在创建数据库实例时自定义页的大小。

需要注意区分以下两个关于页的概念:

• 硬件页： 即磁盘块，大小通常为4 KB，是磁盘I/O的基本单位。
• 数据库页： 大小通常为磁盘块大小的整数倍，是DBMS在磁盘和缓冲池之间交换数据的基本单位。
  二者的区别在于，对硬件页的写操作是原子的，但是对数据库页的写操作则不一定。换言之，如果硬件页的大小为4KB，那么当系统尝试向磁盘写入一个硬件页时，这4KB数据要么全部写入，要么全部不写入，这一点是由存储设备来保证的。但是，如果数据库页大于硬件页，那么DBMS对一个数据库页的写操作将被操作系统分解为对多个硬件页的写操作，此时DBMS必须采取额外措施来确保数据被安全地写入磁盘，因为系统可能会在将一个数据库页写入到磁盘的过程中发生崩溃，从而导致该数据库页的内容出现不一致性错误。

页的组织方式

一个页面的内部结构可以粗略的划分为两部分：
页头 ：页头登记了关于页面内容的元数据，如页面大小、校验和、DBMS版本、事务可见性、压缩信息等。有些系统（如Oracle）要求页面是自包含的，即关于该页的所有描述信息都可以在该页面中找到。
数据区 ：存放数据的区域。这里我们只讨论如何在数据区中存放记录。目前DBMS中最常用的方法是采用槽式页面（slot in page）。这种方法将数据区划分为一个个插槽（slot），每个插槽(slot)中放置一条记录(record)。
槽式页面
在槽式页面结构中，为了登记当前页面中有多少条记录以及每条记录的位置，必须在页头中维护以下信息：

1.本页中已使用的槽的数量；
2.最后一个已使用的槽的起始位置；
3.一个槽数组，登记本页中每个记录的起始位置。

如果允许记录是变长的，我们一开始并不能确定一个页面中能存放多少条记录，因此也就无法确定槽数组的最大长度，也就是说页头所占的区域大小是不确定的。因此比较合理的做法是，向页中插入记录时，槽数组从前向后增长，而被插入的记录数据则是从页尾向前增长。当槽数组和记录数据相遇时，则认为该页面是满页。槽式页面的布局示意图如图2-5所示。

1.插入记录 增
向关系中插入一条记录时，对于堆文件，只需要找到一个有足够空闲空间能放得下这条记录的页面，或当所有已分配页面中都没有足够空闲空间时，就申请一个新的空闲页，然后将记录放置在那里。
2.删除记录 删
从页中删除记录时，需要考虑如何回收该记录的空间。

一种方法是在页内滑动记录，使得记录间没有空隙，从而1.保证页面中未使用的区域一定位于槽数组和已使用区域之间，图2-5表示的就是这种方式。

如果不滑动记录，则需要2.在页头维护一个空闲区列表，以保证当向页中插入一条新记录时，我们能知道该页中的空闲区在哪里(offset)，有多大(size)。当然，页头通常不必存储全部空闲区列表，只存列表的链头就够了，然后可以使用空闲区自身的空间存储下一个空闲区的信息。
3.修改记录 改
如果修改的是定长记录，对页面存储没有影响，因为修改后记录占用的空间与修改前完全相同。但是如果修改的是变长记录，就会碰到与插入和删除类似的问题。

如果修改后的记录比其旧版本长，则我们需要在当前页面中获得更多的空间，这个过程可能涉及记录的滑动。如果当前页面中的空闲区域不够，还需要将记录移动到其他页面。反之，如果记录由于修改而变短，我们可以像删除记录时那样回收其释放的空间。

记录的组织结构

记录本质上就是一个字节序列，如何将这些字节解释为属性类型和值是DBMS的工作。与页面结构类似，记录内部结构也可以分为两部分：

• 记录头 ：存放关于记录的元数据，例如DBMS并发控制协议的可见性信息（即哪个事务创建/修改了此记录的信息）、NULL值的位映射等。注意，关于数据库模式的元数据没有必要存储在记录头里。
• 记录数据 ：包含记录中各个属性的实际数值。如前所述，大多数DBMS不允许记录的长度超过页面的大小，且一个页面中一般只存放同一个关系的记录。

1.定长记录
定长记录全部由定长字段组成，是最简单的记录组织形式。定长记录的插入和删除是比较容易实现的，因为被删除的记录留出的可用空间恰好是插入新的记录所需要的空间。

定长记录在组织时需要注意的一个问题是内存对齐问题。很多处理器需要在数据的开始地址为4或8的倍数时才能实现更高效的内存读写，所以DBMS在组织记录数据时通常会根据情况使所有字段的起始地址是4或8的倍数。采用这种做法时，一个字段前可能会存在一些没有被上一个字段使用的空间，这些空间其实是被浪费掉了。但尽管如此，这样做还是有必要的。因为记录虽然是存放在磁盘而不是内存中，但是对记录的操作仍需在内存中进行，所以在组织记录时需要考虑如何让它在内存能够被高效访问。
2.变长记录
变长记录允许记录中存在一个或多个变长字段。由于变长字段在记录中的偏移位置是不确定的，因此记录中必须包含足够多的信息，让我们能够方便地提取记录的任何字段。变长记录的实现可以采用以下两种方法。

一种简单有效的实现方法，是将所有定长字段放在变长字段之前，然后在记录头写入以下信息：（1）记录长度；（2）除第一个变长字段之外的所有变长字段的偏移位置。之所以不需要存第一个变长字段的偏移位置，是因为我们知道第一个变长字段就紧跟在定长字段之后。一个变长记录的例子如图2-6所示，该记录共包含四个字段，其中有两个变长字段：name和address。