查找算法之线性索引查找法

数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构，索引就是把一个关键字与它对应的记录相关联的过程，一个索引由若干个索引项构成，每个索引项至少包含关键字和其对应的记录在存储器中的位置等信息。索引技术是组织大型数据库以及磁盘文件的一种重要技术。

索引按照结构可以分为线性索引、树形索引和多级索引。这里只介绍线性索引技术。所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。这里介绍三种线性索引：稠密索引、分块索引、倒排索引。

稠密索引

稠密索引是指在线性索引中，将数据集中的每一个记录对应一个索引项。

对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列

索引项也有序也就意味着，我们要查找关键字时，可以用到折半，插值，斐波那契等有序查找算法，大大提高了效率。比如上图，我要查找关键字是18的记录，如果直接从右侧的数据表中查找，那只能顺序查找，需要查找6次才可以查到结果。而如果是从左侧的索引表中查找，只需两侧折半查找就可以得到18对应的指针，最终查找到结果。

这显然是稠密索引优点，到时如果数据集非常大，比如上亿，那也就意味着索引也得同样的数据集长度规模，对于内存有限的计算机来说 ，可能就需要反复去访问磁盘，查找性能反而大大下降了。

分块索引

稠密索引因为索引项与数据集的记录个数相同，所以空间代价很大，为了减少索引项的个数，我们可以对数据集进行分块，使其分块有序，然后再对每一块建立索引项，从而减少索引项的个数。

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

• 块内无序，即每一块内的记录不要求有序，当然，如果块内记录有序更理想，不过块内有序需要大量时间和空间的代价，通常要求快内无序。
• 块间有序,例如，要求第二块所有记录的关键字均要大于第一块中所有记录的关键字，第三块的所有记录的关键字均要大于第二块的所有记录关键字……因为只有块间有序，才有可能在查找时带来效率。

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

如图所示，定义的分块索引的索引项结构分三个数据项：

• 最大关键码，它存储每一块中的最大关键字，这样的好处就是可以使得在它之后的下一块中的最小关键字也能比这一块的最大关键字要大;
• 存储了块中的记录个数，以便于循环时使用;
• 用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历。

在分块索引表中查找，就是分两步进行：

1. 在分块索引表中查找关键字所在的块。由于分块索引表是快间有序的，因此很容易利用折半，插值等算法得到结果。
2. 根据块首指针找到相应的块，并在块中顺序查找关键码。因为块中可以是无序的，因此只能顺序查找。

分块索引的时间复杂度：
设n个记录的数据集被平分成m块，每块中有t条记录，显然n=m×t,或者说m=n/t。再假设L_b为查找索引表的平均查找长度，因最好与最差的等概率原则，所以L_b的平均长度为(m+1)/2。L_w为块中查找记录的平均查找长度，同理可知它的平均查找长度为(t+1)/2。这样分块索引查找的平均查找长度为:

注意上面这个式子的推导是为了让整个分块索引查找长度依赖n和t两个变量。从这里我们得到，平均长度不仅仅取决于数据集的总记录数n，还和每一个块的记录数t有关，最佳的情况就是分的块数m和块中的记录数t相同，此时意味着n=m×t=t²,即ASL_w=(1/2)*((n/t)+t)+1=√n+1

可见，分块索引的效率比之顺序查找的O(n)是高了不少。不过显然它与折半查找的O(logn)相比还是有不小的差距，因此在确定所在块的过程中，由于块间有序，所以可以应用折半，插值等手段来提高效率。

总的来说，分块索引在兼顾了对细分块不需要有序的情况下，大大增加了整体查找的速度，所以普遍被用于数据表查找等技术的应用中。

倒排索引

在我们使用百度或者谷歌搜索的时候，当我们输入某个信息，搜索引擎都会在短时间内给我们一些结果，如图，它是用到什么算法技术实现的高效查找呢？

这里简单介绍，也算是最基础的搜索技术——倒排索引。
当然，搜索引擎所使用到的算法绝对比这复杂的多。
例如我们看如下两句话：

1. Books and friends should be few but good
2. A good book is a good friend

如图所示，我们将单词做了排序，也就是表格显示了每个不同的单词分别出现在哪篇文章中。

有了这张表，我们在查每个单词时都能很快的查找到这个单词在哪篇文章。
在这里这张单词表就是索引表，索引项的通用结构是：

• 次关键码，例如上表中的“英文单词”
• 记录号表，例如上表中的“文章编号”

其中记录号表存储具有相同次关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字）。这样的索引方法就是倒排索引。