1. 索引章引论¶

许多大规模计算应用都围绕那些大到无法装入内存的数据集展开。 最典型的例子是带有多个查找键的大型记录数据库，它要求支持 插入、删除和查找记录的能力。 散列为这类情形提供了出色的性能，但仅限于所有查找都是"查找 键值为 \(K\) 的记录"这种形式的受限情形。 许多应用需要更一般的查找能力。 一个例子是范围查询（range query）：查找键落在某个区间内的所有记录。 其他查询可能要求按键值的顺序访问所有记录，或查找键值 最大的记录。 散列表的结构无法高效地支持这些查询中的任何一种。

本章介绍用于组织存储在磁盘上的大规模记录集合的文件结构。 这类文件结构支持高效的插入、删除和查找操作，适用于精确匹配查询（exact-match query）、范围查询（range query）以及最大/最小键值查找。

在讨论这些文件结构之前，我们必须熟悉一些基本的文件处理术语。一个 序列 文件按照记录添加到文件时的顺序存储记录。序列文件是未排序列表的磁盘等同物，因此不支持高效的搜索。自然解决方案是按查找键的顺序对记录进行排序。然而，典型的数据库，例如由企业维护的员工或客户记录集合，可能包含多个查找键。回答关于特定客户的问题可能需要对客户姓名进行搜索。企业通常希望按邮政编码顺序对记录进行排序和输出，以便进行批量邮件。政府文件可能需要能够按社会安全号码进行搜索。因此，可能没有一个“正确的”顺序来存储记录。

索引 是把键与相应数据记录的位置关联起来的 过程。 外排序 通常使用键 排序的概念：创建一个 索引文件，其记录由键/指针 对组成。 这里，每个键都与一个指向主数据库文件中完整记录的指针 相关联。 索引文件可以被排序或用树结构组织，从而在不物理重排记录的 前提下为记录强加一个逻辑顺序。 一个数据库可以有多个相关联的索引文件， 每个索引文件通过不同的键字段支持高效访问。

每个数据库记录通常都有一个唯一的标识符，称为 主键 。例如，一个人员记录集的 键 可能是该人的社会保障号码或身份证号码。不幸的是，身份证号码通常是一个不便于用于搜索的值，因为搜索者不太可能知道它。相反，搜索者可能知道所需的雇员姓名。或者，搜索者可能感兴趣的是找到所有薪资在某个特定范围内的雇员。如果这些是数据库的典型搜索请求，那么，姓名和薪资字段应该分别有索引。然而，姓名和薪资索引中的键值不太可能是唯一的。

一个键字段（如薪水），其特定键值可能在多条记录中重复出现，称为 次键 。大多数查找都是使用次键进行的。 次键索引 （或更简单地称为 次索引 ）将一个次键值与每条具有该次键值的记录的主键关联起来。此时，可以直接在整个数据库中查找具有该主键的记录，也可能存在一个 主键索引 （或 主索引 ），将每个主键值与指向磁盘上实际记录的指针关联起来。在后一种情况下，只有主索引提供磁盘上实际记录的位置，而各次索引则引用主索引。

索引是组织大型数据库的重要技术，人们已经开发了许多索引方法。 通过散列的直接访问在 Hashing 章讨论。 按键值排序的简单线性表也可以充当记录文件的索引。 用有序线性表索引磁盘文件将在下一节讨论。 遗憾的是，有序线性表的插入和删除操作表现不佳。

第三种索引方法是树索引。 树通常用来组织那些必须支持记录插入、删除和键 range query 的大型数据库。 ISAM 是解决"存储必须支持插入和删除记录 的大型数据库"这一问题的一次初步尝试。 它的缺陷恰好有助于说明树索引技术的价值。 模块 TreeIndexing 介绍与树索引相关的基本问题。 模块 2-3 树 介绍 2-3 树—— 一种平衡树结构，是 B 树 的简单形式。 B 树是大型磁盘数据库和文件系统实现中使用最广泛的索引方法。