Lec 9: Database Storage Structures⚓︎

在本章，我们着重探讨位于底层存储器的数据组织，以及数据的访问方式。

File Organization⚓︎

通常，一个数据库会被映射到多个不同的文件(files) 上，这些文件由底层的操作系统来维护，并永久存储在硬盘上。一份文件包含了数据库的一个记录序列，而这些记录会被映射到硬盘块(blocks) 上，作为存储分配和数据传输的基本单位。为了便于后续讨论，我们约定：

• 一个记录不得大于一个硬盘块的大小（而一个硬盘块可能包含多个记录）
• 每个记录只能被包含在一个硬盘块上

在前面几章的学习中，我们知道记录的长度可以是固定的（比如 INT、CHAR 类型等），也可以是变化的（比如 VARCHAR、NUMERIC 类型，或者数组等），因而我们需要考虑这些不同情况下的文件组织方式。

例子

下面的讲解中，我们将拿一个名为 record 的记录作为例子，它的定义为：

TYPE instructor = RECORD
                      ID VARCHAR(5);
                      name VARCHAR(20);
                      dept_name VARCHAR(20);
                      salary NUMERIC(8, 2);
                  END

下面给出一个关于这类记录的文件：

Fixed-Length Records⚓︎

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

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

对于记录的删除问题（假设删除第 3 条记录），有以下几种解决思路：

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

  

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

  

• 因为通常插入操作比删除操作更频繁，所以就暂且先让被删除记录所在的空间是开放的，然后等待之后的插入。

  • 在文件开头，我们会分配一些特定的字节作为文件头(file header)，里面包含关于文件的信息，这里我们只关心第一个被删除记录（空间空出来了）的地址信息。在这个记录上，我们记录第二个被删除的空余记录，以此类推。所以这些被删除的记录构成了一个链表，通常称为空表(free table)。
  
  • 当插入新记录时，我们将这个记录放在文件头所指的记录上，然后让文件头指向下一个空闲的记录。如果没有空闲空间的话，就讲记录插在文件末尾。

Variable-Length Records⚓︎

在处理变长记录时，需要解决以下问题：

• 如何表示单个的记录，使得提取单个属性较为容易，即便这个属性是变长类型的
• 如何在一个块内存储变长记录，使得从块中提取记录较为容易

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

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

再来看第二个问题——一般情况下，我们用槽式页结构(slotted-page structure) 来组织在块内的记录，如下图所示：

每个块的开头都有一个头 (header)，包含以下信息：

• 头里面的记录数量
• 块内空余空间 (free space) 的结束位置
• 一个包含每个记录的位置和大小的数组

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

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

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

Storing Large Objects⚓︎

略 ...

Organization of Records in Files⚓︎

现在我们来看一下文件内记录的组织方式：

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

下面将会详细介绍前三种文件组织。

Heap File Organization⚓︎

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

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

例子

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

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

例子

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

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

Sequential File Organization⚓︎

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

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

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

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

如果溢出块内的记录不多，那么上述插入策略表现较好。但随着时间的流逝，搜索键顺序和物理顺序之间的关联会逐渐丢失，那样的话顺序处理就变得不那么有效了。此时我们需要重新组织(reorganize) 文件，但这样的操作成本较大，必须在系统负载较低的情况下进行。重新组织的频率取决于插入记录的频率。

B+ 树的文件组织是这种组织的上位替代，我们将在下一讲介绍。

Multitable Clustering File Organization⚓︎

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

例子

假如执行以下查询语句：

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) 是用于定义哪些记录存储在一起的属性。

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

Partitioning⚓︎

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

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

Data-Dictionary Storage⚓︎

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

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

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

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

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

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

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

Database Buffer⚓︎

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

Buffer Manager⚓︎

当数据库系统内的程序需要来自硬盘的数据块时，就会向缓冲区管理器发起请求。

• 如果缓冲区里已经有数据块了，那么缓冲区管理器就会将这个块在主存中的地址发送给请求者
• 如果没有的话，缓冲区管理器首先在缓冲区上为这个块分配空间。如有必要会扔掉一些已有的块，但如果这些即将被扔掉的块相比上次从硬盘中写到主存时有过修改的话，就要将这些块先写回到硬盘中。然后缓冲区管理器从硬盘中将所需的块读到主存中，并将主存地址发送给请求者

和虚拟内存的机制十分相似！

如果缓冲区没有多余空间的话，那么就需要驱逐(evict) 某个数据块，即在读入新数据块之前，将这个数据块移除掉。具体的移除策略将在下一小节介绍。

有时会遇到这种情况：在主存读取 / 写入某个数据块时，另一个并发的进程驱逐了这个数据块，并且用不同的数据块来替代它，这样就会导致读到错误的数据，或者破坏数据。因此，有必要在缓冲区中读取数据之前，确保数据块不会被驱逐，具体来说进程会对数据块采取一种钉住(pin) 操作，不让缓冲区管理器驱逐这个数据块。当完成读取操作后，进程就会执行解钉(unpin) 操作，允许数据块被驱逐。在设计数据库时，确保不要对太多的块采取钉住操作，否则这个数据库就没法正常处理了。

如果有多个进程同时读取缓冲区的某个数据块，那么每个进程都会执行钉住和解钉操作，且只有当所有进程执行解钉操作后，该数据块才可以被驱逐。一种简单的方法是保留一个钉计数(pin count)，每个钉住操作就会让这个数 +1，每个解钉操作就会让这个数 -1，只有当这个数等于 0 时才能被驱逐。

向数据块添加或删除某个元组的进程可能需要移动数据块的内容，在这段时间内，不应该有其他进程读取数据块的内容，否则就会导致数据的不一致。为了做到这一点，缓冲区管理器提供了一种锁系统，允许数据库进程在访问数据块前对这个块上一个共享锁或排外锁；当访问完成时，就会释放这个锁。具体的规则如下：

• 任何数量的进程可同时对同一个块上一个共享锁。
• 某个时间点内，只有一个进程被允许对数据块上排外锁，且当某个进程上了排外锁后，其他进程就不得使用共享锁，因此只有当其他进程没有对数据块上锁时，才能赋予某个进程上排外锁的权利。
• 如果某个进程对一个已经被上了共享锁或排外锁的数据块发起排外锁请求，那么这个请求将会一直等到所有先前的锁都被释放时才生效。
• 当某个数据块没有被上锁，或者已经上了共享锁时，那么某个进程的共享锁请求会被接受；但如果这个数据块上了排外锁的话，就要等这个锁被释放后才能接受请求。

上锁的具体操作为：

• 在对数据块执行任何操作前，进程必须先对该数据块进行钉住操作，然后就会对其上锁，这个锁会在解钉操作执行前被释放。
• 在读取某个数据块前，进程必须提供一个共享锁。当读取完成时，进程必须释放该锁。
• 在更新某个数据块前，进程必须提供一个排外锁。当更新完成时，进程必须释放该锁。

上述规则确保了缓冲区访问的安全性，但对于数据库系统的并发访问还是不太够的，这点会在之后的章节中介绍。

有时需要将缓冲区的数据块写回到硬盘中，以确保硬盘中特定数据的一致性，这种写操作被称为强制输出(forced output)。

Buffer-Replacement Strategies⚓︎

替换策略的目标是最小化对硬盘的访问。在操作系统中，我们会假设最近被引用的数据块可能在将来不久后会被再次引用。因此，如果要替换某个数据块的话，那就替换最久没有被引用的数据块，这种方法称为最近最少使用(least recently used, LRU)。

相比操作系统，数据库系统可以更精确地预测未来的访问模式。一个用户对数据库系统的请求包含多个步骤，数据库系统可以阅读这些步骤来提前决定哪些数据块要被用到。所以数据库系统可能会采取比 LRU 更好的替换策略。来看下面的例子：

SELECT *
FROM instructor NATURAL JOIN department;

理想的数据库替换策略需要知道和数据库操作相关的信息，包括正在执行的以及将来执行的。但没有一个已知的策略能够应对所有情况。事实上，大多数数据库系统采用的是 LRU，尽管这个策略也有些问题。

Reordering of Writes and Recovery⚓︎

数据库缓冲区允许在主存执行完写操作后，过一段时间再输出到硬盘上，这样可能导致输出到硬盘的顺序不同于写操作的执行顺序。而且，文件系统也可能会为写操作重新排序，但这样会导致在系统崩溃时硬盘数据的不一致性。

为了应对上述问题，早期的文件系统会在系统重启时执行文件系统一致性检查(file system consistency check)，确保数据结构的一致性；如果发现不一致的情况，就需要采取额外的步骤来恢复一致性。但这些检查会带来很长的时延，而且对于大容量的硬盘系统而言，这个时延会变得更加糟糕。

如果文件系统能够以一个精心挑选的顺序向元数据写入更新的话，就能避免很多情况下的不一致性。但这样做会让一些优化策略失效，比如磁盘臂调度，从而影响到更新效率。

现代的文件系统会用一个硬盘来存放按执行顺序排序的写操作日志，这样的硬盘称为日志硬盘(log disk)。所有对日志硬盘的访问都是顺序的，这样就能消除寻道时间，而且一些连续的块能被一次写入，这样比随机写操作快好几倍。如果在向硬盘执行写操作时发生崩溃，那么系统会读取日志硬盘的内容，找到未完成的写操作并再次执行。当写操作完成后，记录将会从日志硬盘中删除。

支持日志硬盘的文件系统称为日志文件系统(journaling file system)，这种系统允许数据和日志保存在相同的硬盘上，从而降低成本，但代价是降低性能。因为无需进行一致性检查，所以它能让系统重启更快。

Column-Oriented Storage⚓︎

通常数据库系统会将元组中的所有属性放在一条记录里，这样的存储布局称为面向行的存储(row-oriented storage)。相对应的也有面向列的存储(column-oriented storage)，它的做法是单独存储关系中的每个属性，一组连续元组的某个属性值被放在文件中的连续位置上，如下所示：

在最简单的面向列的存储形式中，每个属性被存在单独的文件中，并且通过压缩文件来减小文件大小。

这种面向列的存储适用于数据分析查询——需要处理关系中的多个行，但通常只访问部分属性。推荐理由如下：

• 减小 I/O 次数：如果是面向行的存储的话，就需要从硬盘中获取不相干的属性；而面向列的存储只会获取要用到的属性，这会降低 I/O 次数，从而降低了执行查询的开销。
• 提升了 CPU 高速缓存的性能：当查询处理器获取特定属性的内容时，由于现代 CPU 的架构，会将多个连续字节（称为一个高速缓存行）从内存拿到 CPU 的高速缓存上。面向列的存储能充分利用这个特点。
• 提升压缩能力：压缩能够显著降低从硬盘中检索数据的时间，这通常是查询中最花时间的操作。对于面向列的存储，存储的是相同类型的值，这能够有效提升压缩的效率。
• 向量处理：很多现代 CPU 架构支持向量处理，即允许 CPU 对数组中的一些元素进行并行运算。按列存储的方式能够利用到向量处理的优势，比如比较一个属性和一个常量，聚合运算等等。

面向列的存储也有以下缺点，这使得它尤其没法用在事务处理上：

• 元组重构的成本：从一组单独的列中重构一个元组的成本是很高的，可能会抵消掉面向列的存储带来的好处。
• 元组删除和更新的成本：删除或更新一个被压缩的元组需要重写所有被压缩在一起的元组序列，所以成本很高。
• 解压的成本：从压缩形式中获取数据时需要解压。对于最简单的压缩形式，解压要求读取从文件开头读取所有数据，但很多记录实际上是不需要的。

ORC 和 Parquet 是在很多大数据处理应用中用到的列文件表示。其中 ORC 会将占据几百 MB 的元组序列划分为一种称为条(stripe) 的列表示，而一个 ORC 文件会包含多个这样的条，下图展示了 ORC 文件格式的一些细节：

• 每个条包含了一个索引数据、行数据和条尾，ORC 文件还有一个文件尾，这两个“尾”我们不去考虑
• 行数据包含了各个列的压缩后的序列值
• 索引数据用于快速访问所需的元组

Storage Organization in Main-Memory Databases⚓︎

主存数据库(main-memory database) 是指所有数据都存在内存中的数据库，用于优化性能。主存数据库可能会为内存中的记录保留一个直接指向它们的指针，这样的话访问一条记录就是一趟指针遍历，而这个操作十分高效。

如果主存使用面向列的存储方式，那么某个列的所有值被存储在连续的内存位置上。然而，如果发生了向关系附加记录的情况，为了确保连续的空间分配，需要重新分配已经存在的数据的空间。为了避免这一开销，某个列的逻辑数组会被划分为多个物理数组，并且用一个间接表来存储指向所有物理数组的指针，如下所示：

评论区