下载掌阅APP，畅读海量书库
立即打开
数据库系统的主要目标是存储数据，并可以快速地访问它们。但是，数据是如何组织的？为什么我们需要一个数据库系统而不仅仅是一堆文件？文件又是如何组织以提高效率的？
数据库系统确实使用文件来存储数据，但它不是依赖于目录和文件的文件系统层次结构来定位记录，而是使用特定于实现的格式来组织文件。使用特定文件组织形式而不是普通文件的主要原因是：
文件以最小化单个存储数据记录开销的方式进行存储。
用尽可能少的步骤来定位记录。
记录更新可以以某种方式执行，以使磁盘更改的次数最小化。
数据库系统存储数据记录，每个记录都由表中的多个字段组成，其中每个表通常以一个单独文件来表示。我们可以使用搜索键来查找表中的每个记录。为了定位记录，数据库系统使用索引——一种辅助数据结构，让我们能够有效地定位数据记录，而无须在每次访问时都扫描整个表。索引由能够标识记录的字段子集构建而成。
数据库系统通常将数据文件和索引文件分开：数据文件存储数据记录，而索引文件存储元数据并使用它来定位数据文件中的记录。索引文件的大小通常比数据文件小。文件被划分成页（page），每个页通常具有单个或多个磁盘块的大小。页可以被组织成记录的序列或分槽页（slotted page）（参见3.5节）。
新增记录（插入）和对现有记录的更新使用键/值对来表示。大多数现代存储系统不显式地删除页上的数据。相反，它们使用删除标记（deletion marker，也称为墓碑（tombstone）），其中包含此删除动作的元数据，如键和时间戳。在垃圾收集过程中，这些被更新或被删除标记遮盖（shadowed）过的记录所占用的空间会被数据库回收。该过程会读取页，然后将活动（即未被遮盖）的记录写入新位置，并丢弃被遮盖的记录。
数据文件（有时称为主文件（primary file））通常可以用索引组织表（Index-Organized Table，IOT）、堆组织表（heap-organized table，即堆文件）或哈希组织表（hash-organized table，即哈希文件）来实现。
在堆文件中的记录不需要遵循任何特定的顺序，并且大多数情况下它们都是按写顺序放置的。这样，在追加新的页时，数据库便不需要额外的工作或文件重组。堆文件需要额外的索引结构来指向存储数据记录的位置，以使其能够被检索到。
在哈希文件中，记录存储在桶中，并且键的哈希值确定记录属于哪个桶。存储在桶中的记录可以按追加顺序存储，也可以按键排序存储以提高查找速度。
索引组织表将数据记录存储在索引自身。由于记录是按键的顺序存储的，所以索引组织表中的范围扫描可以通过顺序扫描其内容来实现。
将数据记录存储在索引中使我们能够将磁盘查找的次数至少减少一次，因为在遍历索引并找到搜索到的键之后，我们不必寻址另外的文件来查找相关联的数据记录。
当记录存储在单独的文件中时，索引文件保存着数据条目（data entry），该条目唯一地标识了数据记录，并包含足够的信息使得数据库可以在数据文件中找到它们。例如，我们可以存储文件偏移量（有时称为行定位符）、数据文件中数据记录的位置或哈希文件中的桶ID。在索引组织表中，数据条目包含实际的数据记录。
索引是一种为了高效检索数据而对磁盘上的数据记录进行组织的结构。索引文件被组织成专门的结构，将键映射到数据文件里的记录。这些记录由对应的键（在堆文件的情况下）或主键（在索引组织表的情况下）所标识。
主（数据）文件上的索引称为主索引。但是，在大多数情况下，我们还可以假设主索引是在主键或作为主键的一组键之上构建的。所有其他索引都称为二级索引（secondary index）。
二级索引可以直接指向数据记录，也可以简单地存储它的主键。指向数据记录的指针可以保存堆文件或索引组织表中的偏移量。多个二级索引可以指向同一记录，从而允许单个数据记录能够由不同的字段来标识并且可以被不同的索引来定位。虽然主索引文件中每个搜索键都有一个唯一的条目，但对于每个搜索键，二级索引可能会针对每个搜索键保存多个条目[MOLINA08]。
如果数据记录的顺序遵循搜索键顺序，则这种索引称为聚簇索引（clustered/clustering index）。聚簇索引中的数据记录通常与索引存储于同一文件，有时也存放在单独的聚簇文件中，而这些文件均保留了键的顺序。如果数据存储在单独的文件中，且其顺序不遵循键顺序，则索引称为非聚簇索引（nonclustered/unclustered index）。
图1-5展示了这两种方法的区别。
·a）一个索引组织表，其数据记录直接储存在索引文件内部。
·b）索引文件仅保存偏移量，而用另外的文件保存数据记录。
图1-5：将数据记录存储在索引文件中与将偏移量存储在数据文件中（白色的是索引段；灰色的是保存数据记录的段）
索引组织表以索引的顺序保存数据，因此按定义一定是聚簇的。主索引通常是聚簇的，而根据定义，二级索引一定不是聚簇的，因为它们是用于加速主键以外的键的访问的。聚簇索引既可以是索引组织的，也可以具有单独的索引和数据文件。
许多数据库系统都有一个固有的、显式的主键，即唯一标识数据库记录的一组列。在未指定主键的情况下，存储引擎可以创建一个隐式主键（例如，MySQL InnoDB引擎会自动添加新的自增列并填充该列的值）。
该术语可以用于不同类型的数据库系统中：关系型数据库系统（如MySQL和PostgreSQL）、基于Dynamo的NoSQL存储（如Apache Cassandra和Riak），以及文档型存储（如MongoDB）。有时候它可能以专属于某个项目的特定名词的形式出现，但大多数情况下我们都可以将那些特定名词与这些术语进行清晰的映射。
在数据库社区中，对于是直接通过文件偏移量引用数据记录还是通过主键索引引用数据记录存在不同的意见。
这两种方法各有利弊，因此我们最好针对一个完整实现进行具体的讨论。通过直接引用数据，我们可以减少查找磁盘的次数，但在维护过程中，每当更新或重新定位记录时，我们都必须承担更新指针所带来的成本。通过主索引间接引用数据可以降低指针更新的成本，但在读取路径上成本更高。
如果工作负载主要由读操作组成，那么更新几个索引可能没有什么问题，但是对于具有多个索引、以写为主的工作负载，这种方法便不能很好地工作了。为了减少指针更新的成本，一些数据库的具体实现是使用主键进行间接操作，而不是直接使用数据偏移量。例如，MySQL InnoDB使用主索引并执行两次查找：一次在二级索引中，一次在主索引中[TARIQ11]。这样并不直接使用二级索引查询得到的偏移量，因此增加了一次主索引的查询开销。
图1-6展示了这两种方法的不同之处。
·a）两个索引从二级索引文件直接指向数据条目。
·b）二级索引通过主索引间接地定位数据条目。
图1-6：直接引用数据元组（a）与使用主索引作为间接引用（b）
我们还可以使用混合方法将数据文件偏移量和主键存储在一起。首先，你要检查数据偏移量是否仍然有效，如果它已经发生变化了，则需要额外对主键索引进行遍历，在找到新的偏移量后更新索引文件。