Chapter 09 : Data Storage Structures¶

约 3813 个字 2 行代码 13 张图片预计阅读时间 19 分钟

File Organization¶

数据库是以一系列文件的形式存储的
每个文件都是一个记录序列
记录是一系列字段

我们假设记录大小是固定的（稍后我们可以考虑可变长度记录），每个文件仅包含一种特定类型的记录，不同的文件用于不同的关系，一个记录不得大于一个硬盘块的大小（而一个硬盘块可能包含多个记录）

接下来我们以下图所示的一系列记录为例：

Fixed-Length Records¶

一个很简单的方法是：直接为变长类型赋予最大字节数的空间。因此每个 instructor 记录就要占据 53 个字节的空间。但这种方法会带来以下问题：

除非块的大小正好是 53 的倍数（通常不太可能），否则有些记录可能会跨过块的边界，即某些记录会位于两个块内。访问这样的记录就需要两次读 / 写操作了
- 解决方案：为每个块仅分配能够完全容纳得下的记录，多出来的小空间直接忽略掉
同时，我们很难删除这样的记录，因为删除记录后需要用其他记录填补这块空间，或者直接忽视这块空间

删除记录

假设我们需要删除 3 号记录，有几种解决方法：

整体前移覆盖替换等待插入

将被删除记录后面的所有记录向前移动，填补被删除记录所在的空间。这种方法需要移动大量的记录，效率不高

直接拿最后一条记录填补被删除的记录所在空间，但这样做会导致额外的块访问

因为通常插入操作比删除操作更频繁，所以就暂且先让被删除记录所在的空间是开放的，然后等待之后的插入
在文件开头，我们会分配一些特定的字节作为文件头（File Header），里面包含关于文件的信息，这里我们只关心第一个被删除记录（空间空出来了）的地址信息。在这个记录上，我们记录第二个被删除的空余记录，以此类推。所以这些被删除的记录构成了一个链表，通常称为空表（Free List）

当插入新记录时，我们将这个记录放在文件头所指的记录上，然后让文件头指向下一个空闲的记录。如果没有空闲空间的话，就将记录插在文件末尾

Variable-Length Records¶

对于变长记录，主要会出现两个问题：如何表示单个的记录，使得提取单个属性较为容易，即便这个属性是变长类型的？如何在一个块内存储变长记录，使得从块中提取记录较为容易？

可变长度记录在数据库系统中以多种方式出现：
- 在文件中存储多个记录类型
- 允许一个或多个字段（如字符串（varchar））具有可变长度的记录类型
- 允许重复字段的记录类型（在某些较旧的数据模型中使用）

对于第一个问题，通常，变长属性被表示为两部分：定长的信息（偏移量（数据起始位置） + 长度（变长属性的大小）），以及变长属性值。例如，Instructor 的结构图如下所示：

可以看到，这个记录先存的是三个变长属性的定长信息，然后是一个定长属性值，最后是变长属性值。而在定长属性值和变长属性值之间有一组 0，称为空位图（Null Bitmap），用于记录属性值是否为空。在这个例子中，由于一条记录有 4 个属性，因此用 4 个 0 来分别表示每个属性值的情况。假如 salary 为空，那么空位图的第 4 位就会被设为 1。有些情况下，空位图会被放在记录的开头位置，这样做可以节省空间（因为一旦空位图全为 1，后面就不需要存数据了），但代价是需要先从记录中提取属性。这种方式对于具有大量字段，且大多数为空值的记录而言很有用

对于第二个问题，一般情况下，我们用槽式页结构（Slotted-Page Structure）来组织在块内的记录，如下图所示：

每个块的开头都有一个头（Header），包含以下信息：

头里面的记录数量
块内空余空间（Free Space）的结束位置
一个包含每个记录的位置和大小的数组

在块内，记录被分配到的空间是连续的。而空余空间从头数组的末尾，到第一个记录之间的空间也是连续的。

当插入记录时，会为其分配空余空间末尾的一处空间，并且这个记录的位置和大小将会被记在头上。
当删除记录时，会释放它所占据的空间，并且对应的头数组被标记为删除状态（比如将大小设为 -1）。另外，在这个被删除记录之前的记录都需要被移动，这样才能为空余空间腾出这个记录的同等大小的空间。移动的成本不是很大，因为块的大小被限制在一定范围内

这种槽式页结构要求指针不得直接指向记录上，而必须指向对应头数组的元素上，该元素包含了记录的位置。这种间接的方式可以避免块内的分段现象

Organization of Records in Files¶

记录在文件中的组织方式主要有以下几种：

堆（Heap）文件组织：任何记录可以放在文件的任何地方，无需考虑顺序。一个关系可以存放在一个或多个文件中
顺序（Sequential）文件组织：根据每个记录的“搜索键（Search Key）”的值，按顺序存储记录
多表聚集（Mutlitable Clustering）文件组织：来自不同关系的记录被存储在相同的文件内，以减少连接运算的成本
B+ 树文件组织：即便在插入、删除和更新操作改变记录顺序的情况下，也能保持记录的顺序。这块内容将在下一讲介绍。
哈希文件组织：根据一些属性计算哈希函数，用于指明哪个块上放哪个记录

Heap File Organization¶

在堆文件组织中，一个记录可以被放在文件的任意位置上。但一旦确定位置后，一般不能再去移动这个记录了

向文件插入记录时，可以采取始终加在文件末尾的策略。然而，对于记录的删除，我们需要考虑利用删除记录释放的空间，用于存储新记录，以最大化利用空间。大多数数据库会采用一种称为空余空间图（Free-Space Map）的数据结构，用于高效寻找空余空间。这个数据结构通常用一个数组表示，每个元素对应一个块，其值表示对应块的空余空间比例。为了找到能够存储新记录的块，数据库需要扫描空余空间图，来找到有足够空间存储记录的块。如果没有这样的块，那么需要为这个关系赋予一个新的块

对于大型文件，这样的扫描还是太耗时了，此时我们可以创建一个第二级的空余空间图，其元素对应主（第一级）空余空间图中若干个元素（相当于分组）的最大值。对于更大的文件，也可以创建更多层级的空余空间图

Example

假如空余空间图的每个元素的大小为 3 位，当某个元素为 7 时，表明对应块内至少有 ⅞ 的空间是空余的

假如第二级空余空间图中的一个元素对应第一级的 4 个元素，那么其里面的内容为：

如果每次更新就要向硬盘写入空余空间图的话，那么成本太昂贵。所以一般会周期性地写入空余空间图，但这样做硬盘里的空余空间图可能会过时，访问这样的空余空间图就会引发错误

Sequential File Organization¶

顺序文件（Sequential File）用于高效处理有序的记录，它基于搜索键（Search Key）实现。这个搜索键包含了任意的属性，不必是主键或超键。为了更快地检索记录，我们用指针将这些记录连接起来。并且为了最小化块的访问次数，我们将记录按搜索键顺序进行物理存储。如下图展示了 instrutor 记录的顺序文件：

顺序文件组织比较像链表，其好处是让我们能够有序读取记录，这对显示记录，以及某种查询处理算法而言很有用。但维护记录在物理层面上的顺序比较困难，因为记录随时会被插入和删除。

对于删除，通过移动指针就能解决。
对于插入，需要遵循以下规则：
- 在记录按搜索键插入之前，找到这个记录在文件中的位置。
- 如果存在空余记录，且位于和该记录相同的块上，则直接将新记录放在这个空余记录上。否则的话，将新记录插入到溢出块（Overflow Block）。上述两种情况下都需要调整相应的指针，以保持搜索键的顺序。

下图展示了插入一条记录后的顺序文件：

如果溢出块内的记录不多，那么上述插入策略表现较好。但随着时间的流逝，搜索键顺序和物理顺序之间的关联会逐渐丢失，那样的话顺序处理就变得不那么有效了。此时我们需要重新组织（Reorganize）文件，但这样的操作成本较大

Multitable Clustering File Organization¶

大多数关系数据库系统会将每个关系放在单独的一个或一组文件里。然而，在有些情况下，将多个关系的记录存在单个块内会更加有用

Example

假如我们有 department 和 instructor 两个关系如下：

执行以下查询语句：

select dept_name, building, budget, ID, name, salary
from department natural join instructor;

这条语句将两个关系连接在一起，因此对于 department 中的每个元组，系统必须找到 dept_name 值相同的 instructor 的元组。如果这些关系放在单独的文件上，那么在最坏的情况下，每条记录都位于不同的块，那么这个访问速度就特别地慢了

我们将这两个关系自然连接的结果放在一个文件内：

这两个关系通过键 dept_name 聚集在一个文件内。这样的文件结构提升了处理连接操作的效率

多表聚集文件组织（Multitable Clustering File Organization）是一种将多个关系中有关联的记录存储在一个块内的文件组织。而聚集键（Clustering Key）是用于定义哪些记录存储在一起的属性。

尽管这种文件组织加快了特定的连接查询操作，但是它会影响到处理其他类型的查询的表现

Table Partitioning¶

很多数据库允许将一个关系内的记录划分（Partition）为多个小的关系，并将其单独存储起来，通过减小关系的大小来降低某些运算的开销。

我们还可以将关系划分为多个部分，并将不同的部分存储在不同的存储设备上，比如将经常用到的部分放在 SSD，不怎么用到的就放在磁盘上

Data Dictionary Storage¶

前面我们只考虑了如何表示关系里的内容，而没有考虑如何维护关于关系的数据，比如关系模式等。我们一般称这种“数据的数据”为元数据（Metadata）。像这些元数据会被存在一个称为数据字典（Data Dictionary）或系统目录（System Catalog）的结构内。系统必须存储以下元数据：

关系的名称
每个关系的属性名
属性的值域和长度
视图的名称和定义
完整性约束

此外，很多系统还会保存关于用户的数据，包括：用户名，用户默认的模式，授权用户的密码以及其他信息等等。还有一些数据库可能会存储关于关系和属性的统计和描述数据，比如每个关系的元组数，每个属性不同值的数量等。

数据字典可能还会记下关系的存储组织（堆、顺序、哈希等），以及关系存储的位置——如果关系被存储在操作系统文件中，字典会记下包含这些关系的文件名；如果数据库将所有关系存储在单个文件中，那么字典就会用链表之类的数据结构记下每个关系的记录所在的块。

实际上，我们还要存储和索引相关的信息（下一讲会详细介绍），包括：索引名、被索引的关系名、定义索引的属性、索引构成的类型。

这些元数据信息实际上构成了一个微型的数据库，所以我们可以将其存储在数据库的某个关系内，这样就可以简化系统的整体结构，并且利用到数据库快速访问的优势。下图就是一个小型的例子：

通常，存储数据字典的关系是非规范化的，以确保更快的访问。当数据库系统需要从某个关系中检索数据时，它必须首先查询这个叫做 Relation_metadata 的关系，找到这个关系的位置和存储组织，然后才能获取记录。因为这些系统元数据会被经常访问，因此大多数数据库将其读入到一个位于内存的数据结构内，以便高效访问，而这一步会作为数据库启动的一部分

Database Buffer¶

因为访问硬盘内的数据会比在内存访问慢很多，因此数据库系统的一大目标是最小化硬盘和内存之间的数据块传输次数。一种方法是让主存保存尽可能多的数据块，但显然无法让主存保存所有的数据块，因此我们需要管理主存中的可用空间，而缓冲区（Buffer）就是主存中用于存储硬盘块拷贝的部分空间，而缓冲区的空间分配则由缓冲区管理器（Buffer Manager）负责