线性索引（稠密索引、稀疏索引即分块索引、多重表、倒排表）

索引是把一个数据文件的关键码和它对应的数据记录相关联的过程。

每一个关联构成一个索引项，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。

所有索引项的集合构成该文件的索引表。保存在磁盘上的索引表又称索引文件。

索引技术是组织大型数据库以及磁盘文件的一种重要技术。

索引按照结构可以分为线性索引，树形索引和多级索引。

所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。

重点了解三种线性索引：稠密索引，分块索引，多重表和倒排索引。

一、稠密索引

稠密索引是指在线性索引的过程中将数据集中的每个记录对应一个索引项。索引项按关键码有序，索引表是有序表。当索引文件可以在内存中容纳时，将索引文件驻留内存，可用高效查找方法如二分查找实现索引表上的查找，在找到索引项后，可根据其中存放的指向记录的位置信息，可快速找到要找的记录。但若主文件记录数较大，由于是稠密索引，故索引表也会很大，甚至无法存储在内存中，可能就需要反复去访问磁盘，查找性能大大下降。

稠密索引不适合在主文件中进行插入或删除一条记录的运算，因为一旦在文件中插入或删除一条记录，就必然要引起记录的移动。为了使稠密索引文件按关键码有序而且是顺序存储的，索引就必须更新。

二、分块索引（稀疏索引）

注意理解：稠密索引是因为索引项和数据集的记录个数相同，所以空间代价很大。

  如何减少索引项的个数呢？

  我们可以对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项（类似于图书馆的分块）。

  分块有序是把数据集的记录分成了若干块，并且这些块需要满足两个条件：

（1）块内无序

  每一块内的记录不要求有序

（2）块间有序

  比如要求第二块记录的关键字均要大于第一块中所有记录的关键字，第三块要大于第二块。

  只有块间有序才有可能在查找时带来效率。

  对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引。

  分块索引的索引项结构分为三个数据项：

a: 最大关键码--存储每一块中的最大关键字。

b: 块长--存储每一块中记录的个数以便于循环时使用。

c: 块首地址--用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历。

在分块索引表中查找，可以分为两步：

a: 在分块索引表中查找要查的关键字所在块。

由于分块索引表是块间有序的，因此很容易利用折半插值等算法得到结果。

b:根据块首指针找到相应的块，并在块中顺序查找关键码。

因为块中可以是无序的，因此只能顺序查找。

三、多重表

若不仅要按主关键码进行查找，还要按次关键码按给定码值或给定取值范围进行查找，则需在建立主索引的同时，也建立次关键码索引。

例：

四、倒排表

倒排表中索引项结构：

关键码值或取值范围

记录号表

索引项包括次关键码的值和具有该值的各记录的地址，或包括次关键码的一个取值范围和取值在该范围内的所有记录的地址。

优点：

（1）既适合主关键码查找，也适合次关键码的查找

（2）查找速度较快

（3）没有要求对主文件中次关键码相同的记录建立链接，因而不需要对主文件进行修改，故其使用和维护简单方便

缺点：

（1）由于记录号表是不定长的，故处理起来不太方便

（2）由于倒排表的记录号表中记录号要求有序，这对在主文件中进行插入和删除记录操作带来相应处理上的工作量