线性索引查找

有此数据集可能增长非常快，例如，某些微博网站或大型论坛的帖子和回复总数每天都是成百万上千万条，或者一些服务器的日志信息记录也可能是海量数据，要保证记录全部是按照当中的某个关键字有序，其时间代价是非常高昂的，所以这种数据都是按先后顺序存储的。

对于这样的查找表，我们如何能够快速 查找到需要的数据呢？办法就是----索引

索引是 了加快查找速度而设计的一种数据结构。

索引就是把一个关键字与它对应的记录相关联的过程，一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。

 

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

 

稠密索引

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

 

 

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

索引项有序也就意味着，我们要查找关键字时，可以用到折半、插值、斐波那契等有序查找算法，大大提高效率。

比如查找上表中的18。如果不用索引表，需要6次。而用左侧的索引表，折半两次就可以找到18对应的指针。

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

分块索引

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

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

l  块内无序，即每一块内的记录不要求有序。当然，你如果能够让块内有序对查找来说更理想，不过这就要付出大量时间和空间代价，因此通常我们不要求块内有序

l  块间有序，例如要求第二块所有记录的关键字均要大于第一块中所有记录的关键字，第三块的所有记录的关键字均要大于第二块的所有记录关键字….因为只有块间有序，才有可能在查找时带来效率。

对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分场索引。我们定义的分块索引项结构分三个数据项：

 

 

n  最大关键码：它存储每一块中的最大关键字，这样的好处就是可以使得在它之后的下一块中最小关键字也能比这一块最大的关键字要大

n  存储了块中的记录个数，以便于循环时使用

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

 

分块索引是分两步进行：

1.    在分块索引表中查找要查关键字所在的块。由于分块索引表是块间有序的，因此很容易利用折半、插值等算法得到结果。

2.    根据块首指针找到相应的块，并在块中顺序查找关键码。因为块中可以是无序的，因此只能顺序查获。

 

倒排索引

搜索引擎，无论你查找什么 样的信息，它都可以在极短的时间内给你一些结果，是什么算法技术达到这样的高效查找呢？

这里介绍一种最基础的搜索技术----倒排索引。

我们来看一个例子：

如下假设有两篇文章：

1.    Books   and  friends   should   be  few   but   good .

2.    A   good book   is   a good  friend.

假设我们忽略掉如“books”，“friends”中的复数”s”以及如“A”这样的大小写差异。我们可以整理出这样一张单词表，如下图，并将单词做了排序，也就是表格显示了每个不同的单词分别出现在哪篇文章中，比如“good”它在两篇文章中都有出现，而is只有在文章2中才有。

 

 

在这里这张单词表就是索引表，索引项的通用结构是：

1.     次关键码

2.    记录号表

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