2. 线性索引¶
2.1. 线性索引¶
线性索引 是一种 索引文件 ，组织为 键值对 的序列，其中 键 按排序顺序排列，并且指针要么 (1) 指向磁盘上完整记录的位置，(2) 指向主索引中 主键 的位置，要么 (3) 实际上就是键的值。根据其大小，线性索引可以存储在内存或磁盘中。线性索引提供了许多优势。它方便访问变长数据库记录，因为索引文件中的每个条目都包含一个定长的键字段和一个指向（变长）记录起始位置的定长指针，如下面幻灯片所示。线性索引还允许高效搜索和随机访问数据库记录，因为它适用于 binary search 。
如果数据库包含的记录足够多，线性索引可能大到无法存入 主存。 这使得对索引做二分查找的代价更高，因为查找过程通常需要多次 磁盘访问。 一种解决方案是在内存中存放一个二级线性索引，指出索引文件中的 哪个磁盘块存储着想要的键。 例如，磁盘上的线性索引可能由一系列 1024 字节的磁盘块组成。 如果线性索引中的每个键/指针对需要 8~字节 （4 字节键和 4 字节指针），那么每个磁盘块存储 128 个键/指针对。 存放在内存中的二级索引就是一张简单的表，记录线性索引文件中 每个磁盘块第一个位置上的键值。 下一张幻灯片展示了这种布局。 若线性索引需要 1024 个磁盘块（1MB），二级索引只包含 1024 个表项，每个磁盘块对应一个。
要找出某个查找键值位于哪个磁盘块， 先在 1024 个表项的表中找到小于等于该查找键的最大值。 这会把查找引向索引文件中正确的磁盘块，随后该块被读入内存。 此时，在该块内做二分查找即可得到指向数据库中实际记录的指针。 由于二级索引存放在内存中，用这种方法访问一条记录需要两次磁盘 读取：一次读索引文件，一次从数据库文件读实际记录。
一个简单的二级线性索引。 线性索引存储在磁盘上。 较小的二级索引存放在内存中。 二级索引的每个表项存储索引文件中相应磁盘块的第一个键值。 本例中，线性索引的第一个磁盘块存储 1 到 2001 的键， 第二个磁盘块存储 2003 到 5688 的键。 因此，二级索引的第一个表项是键值 1 （线性索引第一块中的第一个键），第二个表项是键值 2003。
每当向数据库插入或从数据库删除一条记录时， 所有关联的次索引都必须更新。 线性索引的更新代价很高，因为数组的全部内容都可能要移动。 另一个问题是，具有相同次键的多条记录会在索引中各自重复 该键值。 当次键字段有大量重复值时——比如它的取值范围有限（例如 一个表示工作类别、只有少数几个可选类别的字段）——这种重复 可能浪费相当多的空间。
对简单有序数组的一种改进是使用二维数组，其中每一行对应一个 次键值。 一行中存放的是记录具有该次键值的主键。 12.2.1 图展示了这种方法。 这样就没有次键值的重复， 可能节省相当可观的空间。 插入和删除的代价也降低了，因为只需调整表的一行。 注意，当加入一个新的次键值时，要向数组添加一个新行。 这可能要移动许多记录，但适合使用这种布局的应用中这种情况很少 发生。
这种方法的一个缺点是数组必须是固定大小的， 这就限制了能与特定次键相关联的主键的数量上限。 而且，那些记录数少于数组长度的次键会浪费所在行的剩余 部分。 更好的做法是用一个一维数组存放次键值， 每个次键关联一个链表。 这在索引存于内存时效果很好，但存于磁盘时就不太好了， 因为某个键的链表可能分散在多个磁盘块上。
考虑一个大型的员工记录数据库。 如果主键是员工的 ID 号，次键是员工的姓名， 那么姓名索引中的每条记录把一个姓名与一个或多个 ID 号关联 起来。 ID 号索引再把这些 ID 号与指向磁盘上完整记录的唯一指针关联 起来。 这种组织方式中的次键索引也称为 倒排表 或 倒排文件。 说它"倒排"，是因为查找从次键出发，经主键， 最终到达实际的数据记录。 说它是"表"，是因为每个次键值（在概念上）都关联着一个 主键的列表。 12.2.2 图展示了这种布局。 这里，姓作为次键。 主键是一个四字符的唯一标识符。
12.2.3 图给出了一种存储倒排表的更好方法。 如前所述，这是一个次键值数组。 每个次键关联一个指向主键数组的指针。 主键数组采用链表实现。 这种方法把所有次键列表的存储合并到一个数组中， 大概可以节省空间。 该数组中的每条记录由一个主键值和一个指向表中下一个元素 的指针组成。 在这种数组中插入和删除次键都很容易， 这使它成为基于磁盘的倒排文件的良好实现。
