数据库中数据的组织形式

数据库无疑是负责数据存储和管理的，那么数据的存储媒介就作为整个数据库中最重要的一个组件存在，它的性能以及管理数据的方式直接决定了整个数据库的性能。绝大部分的数据库管理系统（Database Management System）都是使用磁盘作为存储介质，而面对着海量的数据以及给定的成本，不能够一味地使用性能最好的存储媒介，比如 HDD 可以存储的数据量很大但是 IO 很慢，而 DRAM 或者 CPU Caches 的数据存取速度极快，但是使用成本特别高且它们是数据易失的，因此我们必须要在性能和成本之间寻找到平衡。本文通过介绍数据库中数据的组织方式，并以此利用局部性和多级别存储来加快数据的存取速度。

在关系型数据库中，我们所直观认为的数据就是某张表中的一条一条的数据记录（record）构成，而在数据库中会将数据分为一块一块的数据，这一个数据块我们称为 page，一个 page 内部可以包含各种各样的数据（比如索引、某几行或很多行记录等）。

记录（record）的存储组织形式

一条记录（record）代表着某张表中的一行数据，它内部包含了很多不同的 field （字段）。通常，存储每条记录时会在开始附带 header 来存储关于这条记录的元数据信息。比如对于表 MovieStar 中的一条记录组织形式可能如下所示：

CREATE TABLE MovieStar(
	name CHAR(30) PRIMARY KEY;
	address VARCHAR(255);
	gender CHAR(1);
	birthday DATE;
);

对于大部分机器来说，由于内存对齐的关系，一般要求数据所占字节数的大小为 4 或者 8 的倍数，这样有利于数据的访问和管理。在上述例子中我们假设所有的 field 所占用字节数需要为 4 的倍数，因此图中各个 field 占用的实际存储大小都要比实际声明时的大小要多或者刚刚好，这样是为了对齐而增加的无用空间。另外，记录的 header 中所存储的元数据会包含该条记录中的各种信息，比如说该记录的长度、schema 信息、创建和修改时间或一些表示状态的 flag 等。对每个 field 的定位可以直接通过 schema 信息来获取到当前 field 的偏移量。

上述的例子中的每个 field 都是定长的，这种定长的记录在插入和删除时都是比较容易管理和实现的，但是我们总会遇到变长 field 的情况出现。当一条记录有一个或者多个变长的 field 存在时，我们为了更高效地对数据进行组织，会选择将所有定长的 field 放在 record 排布区域的前方，而将所有变长 field 放置于后方。

比如仍然用上述 MovieStar 举例，但不同的是， name 和 address 为变长的，此时可以将其位置放于其他 field 之后，只是这样要在 header 中增加一个指针来指向后面变长 field 的位置，配合这个指针以及 schema 信息就可以定位到变长的 field 位置。另外，在上述例子中，name 虽然是变长的，但是不需要在 header 中增加指向它的指针，因为 name 之前的 field 都是定长的，所以根据 schema 信息配合 address 的指针就可以定位 name 的位置以及长度。

对于变长的数据，就肯定会有 NULL 的情况出现，结合上述的数据组织方式，可以很简单地实现 NULL 的表示方法，可以将 NULL 的字段直接在 header 中增加一个 NULL pointer 即可，这样就不需要再为 NULL 的 field 分配存储空间了。

当我们要存储的数据较大，比如 varchar 数据，此类数据往往会大于 1/2 个 page 页大小，此时我们就不能将其向上述的方法一样直接放置于 record page 中，而是需要额外进行存储，然后在 record 中以指针的形式指向额外的存储空间。

此外，我们还有可能遇到的情况就是 BLOB（binary，large objects） 数据，比如图片、音频乃至视频文件，这类数据的特点就是占用存储空间很大。对于此类数据，我们也只能够为其分配额外的存储空间进行存储，但是大部分的 DBMS 是不能为其提供持久化和事务性保障的。

在传统关系型数据库中，通常使用的存储形式是基于行的存储，这种情况的存储在进行数据查询，且查询所侧重的数据对象是一条一条记录时（即 OLTP 查询），通常扫描一个或较少的几个 page 就能够完成所需要查询的数据请求。而当做数据分析时，往往面临的需求是要获取整个表中某一列的所有数据（即 OLAP 查询），此类查询若采用基于行的存储的话，需要扫描很多个 page 才能完成，因此这种场景下往往使用基于列的存储形式会更加有效。

page 的存储组织形式

当获取或者写入数据时，系统都是按照一个或者多个 page 来进行操作，同时保证这个操作是原子的。比如在向磁盘写入 4KB 的 page 时，会保证整个 4KB 的 page 会要不是全部被写入成功，要不就是完全没有写入。

在整个 DBMS 中，有很多种不同概念的 page，比如操作系统层面有自己的 page（通常为 4KB），数据库中也有自己的 page（通常为 4-16KB）。

每一个 page 的大小不管是在内存还是磁盘中都是固定的，这样能够更高效地进行数据的组织和管理。每个 page 在开始也都会有一块存储空间来存储进行该 page 内容的元数据，比如 page 的大小、checksum 位等。page 内可以存储记录、索引信息、日志等数据，对于大部分系统来说每个 page 都是会存储单一种类数据，而不会在一个 page 中同时存储记录和索引这样的混合数据。

多条记录在 page 中的存储形式

如果 page 内的数据都是定长的，我们自然很好管理，可以直接通过以尾部追加（append）的形式一条一条地添加数据，但这样做很明显会面临一堆问题。

比如上图中的组织方式，如果都是定长（fixed length）的记录，那很简单，数据直接追加到 page 尾部，header 中也只需要记录该 page 内的 record 个数即可，这样的话如果删除一条数据腾出空间，下一次新数据进来时直接填充上一次删除腾出来的空间即可，因为长度都是一致的。但是现实状况总是很残酷，我们总会遇到变长（variable length）的记录，如上图右边所示，我们将第一条和第三条数据删除之后，剩下两块不连续的空间。此时，我们需要新增一条跟之前不同长度的数据，此时就完全不能利用之前删除数据腾出来的空间了。

所以如何更有效地组织 page 内数据的方式，我们使用一种称为 slotted page（分槽的页面组织形式），在 page 的 header 中，除了记录 record 个数外，还会记录各个 record 的位置和大小，如下图所示：

采用这种方式，所有的记录会从尾部开始进行连续排列，当有新的记录插入时，会在空闲空间的尾部为其分配空间，并在 header 中添加该记录的大小和位置信息。采用此种方式，各个记录可以随意在 page 中移动，只需更改 header 中的位置信息即可，这样的话也可以允许一条记录跨 page 进行存储，只需要将 header 的位置信息标记为 forward address，也就是更改位置引用即可。另外，在删除数据时，我们也可以选择是否对数据进行真正的删除，因为将位置信息标记为已删除也可以代表该条 record 已经删除。

log 在 page 中的存储形式

除了要进行多条记录的存储外，log 日志的存储也是很常见的情况，在记录日志的情况下，往往只记录对数据库的操作行为，比如插入、删除了哪条数据，对怎样的数据做了什么样的更新。MySQL 中的 binlog 就是一种类似的使用场景。

对于此类情况，page 也仅仅是以尾部追加的形式将操作行为追加到 page 的尾部，因为仅仅是 append，所以写入数据的速度非常快。但是在读取的时候，就需要从 page 中顺序读取所有行为进行 replay（重放）来还原出最终的数据内容。

因为读取操作需要在所有操作行为中进行 replay，所以若要加速数据读取速度，可以通过在一些位置增加索引，然后通过索引缩短 replay 的时间，也可以对所有的内容进行压缩，减少 replay 需要访问的数据个数。

Buffer Pool

因此磁盘访问的速度限制，因此为了尽量减少磁盘的 IO 次数，结合局部性的特质，在每次访问磁盘数据时尽可能地获取多的数据 page，这样最大化要访问的 page 已经被获取到的几率，避免多次访问磁盘来获取数据。

局部性：对一数据结构中的数据进行访问时，不同的操作之间具有很强的相关性，之前被访问过的元素很有可能在之后被再次访问，将被访问的下一个元素的位置也有可能就在之前被访问元素的位置附近。

但是因为内存大小的限制，不太可能每次获取磁盘数据时都能够一次性获取足够多的 page，因此使用 Buffer Pool（缓冲池）就是一个非常行之有效的方法。当需要访问磁盘中的 page 时，直接向 Buffer Pool 中发起请求，如果要访问的 page 已经存在于 Buffer Pool 中则直接返回，因为 Buffer Pool 是使用内存的，因此速度非常快。若 Buffer Pool 中没有需要的 page 数据，则首先会为要获取的 page 分配存储空间，可能是直接在剩余空闲空间中直接分配，也有可能是将已有的 page 剔除出 Buffer Pool，然后以 page 为单位，从磁盘中进行获取并读入 Buffer Pool，再返回给请求方。

数据库的 Buffer Pool 管理策略同操作系统的 Virtual Address 管理策略几乎一致，但在现实的数据库系统实现中，并不是直接使用操作系统提供的系统调用 mmap 来实现 Buffer Pool 的管理策略，因为数据库所面临的数据大小比机器的地址空间要大得多，另外数据库所需要使用的缓存替换策略往往同操作系统的需求不太一致。

对于数据库管理系统来说，当 Buffer Pool 中的缓存空间不足时，需要进行数据回写到磁盘中的操作，但此时可以根据实际情况做出操作选择。

1. 若 Buffer Pool 中要进行回写的区域并没有产生 dirty page，那么直接从 Buffer Pool 将此区域抹除即可，因为 Buffer Pool 中的原始数据就是从磁盘中获取的，没有 dirty page 意味着数据同磁盘中是一致的；
2. 若有 dirty page，则进行磁盘回写，腾出缓存空间供新的缓存数据使用。

而在操作系统中，当 Buffer 空间不足时，因为 Virtual Address 的存在，系统会不断地在磁盘和内存中进行 page 的换入唤出操作，这对于数据库系统是不可以接受的，因此在数据库中直接使用 mmap 并不是一个好方法。

提到缓存替换策略，有基于访问时间所做的 LRU （Least Recently Used），即在需要对 Buffer Page 中的 page 进行剔除淘汰时，最近访问最少的 page 会被写回磁盘。还有基于访问次数的 LFU（Least Recently Used），即访问次数最少的 page 会被写回磁盘。此外还有 FIFO 以及 Second Chance 一类的策略，这里就不再继续介绍。

InnoDB 引擎中使用的缓存替换策略是基于 LRU 进行更改的，因为对于 LRU 策略有时也会出现问题，比如某些数据查询操作需要访问到很多 page（比如全表扫描操作），Buffer Pool 中头部的数据就会被大量剔除，此时缓存命中率就会受到影响。InnoDB 引擎的方法是将最新访问的 page 放入到 Buffer Pool 的中间位置而不是直接放置于头部，等待一定时间之后才会将其移入到热端位置。

这篇文章我们主要介绍了数据在磁盘、内存中是如何进行存储的，首先数据都是以 page 的形式进行组织的，记录内有自己的存储形式，然后介绍了多个记录在 page 中是如何存储的，进一步简单介绍了 Buffer Pool 是如何工作的。

数据的组织形式往往在实际使用数据库时显得不是那么重要，但是了解它之后会有助于了解如何能够利用数据组织形式加速数据访问，缩小数据占用空间大小，并能够进一步有助于理解缓存是如何工作的。