数据结构之查找（四）——线性索引查找

索引就是把一个关键字与它对应的记录相关联的过程。

索引按照结构可以分为线性索引，树形索引和多级索引。我们这里就只介绍线性索引技术。

所谓线性索引就是将索引项集合组织为线性结构，也成为索引表。分为：稠密索引，分块索引和倒排索引。

稠密索引

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

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

分块索引

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

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

我们定义的索引的索引项结构分三个数据项：

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

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

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

在分块索引表中查找，就是分俩部进行；

1.在分块索引表中查找关键字所在的块。

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

倒排索引

我们都知道搜索引擎搜索一个词是非常快的，但你有没有想过为什么搜索引擎能够以这么快的速度从数以亿计的网页中找到你想要的内容？一个很重要的原因是，现代的搜索引擎基本上都使用了倒序索引技术。

如果不使用倒序索引技术，在每次进行检索时，搜索引擎必须遍历每一个网页，查找网页中是否包含你指定的关键词。这个工作量是十分巨大的，主要原因有二：

• 互联网的网页基数非常大；
• 在每一个网页中检索是否含有指定的关键词不是一件简单的事情，它需要遍历网页的每个字符。

为了更好的建立被搜索的关键字和含有这些关键字的页面之间的映射关系，倒序索引产生了。简单的说，倒序索引的倒序，指的是这个索引是从关键词中查找对应的源的，而不是从源中检索对应的关键词。

举例如下：为了检索关键词 A，首先从倒序索引的索引表中，找到关键词 A，然后查找 A 所在的页。由于倒序索引表排序后，在其中查找一个关键词可以使用二分查找，特别是在采用分布式数据、服务器集群、多线程技术等条件下，效率极高，所以，查找含有某个关键词的页变得非常简单。

假设数据库中含有1000000条记录，其中有 10 条记录符合搜寻条件，如果使用倒序索引，可以很快找到这些关键词，并且定位到含有这些关键词的十条记录；否则，需要遍历1000000条记录，效率的差异可想而知。

所以，倒序索引相当于一本出处大字典，查阅其中的每个词汇，都可以告诉你它的所有出处。

如：1.Books and friends should be few but good.

2.A good book is  a good friend.

(忽略如“books","friends"中的复数"s"以及如"A"这样的大小写差异。我们整理出如下的单词表：