1.引言
我们前面提到的几种高效查找方法都是基于有序的基础上的，但是实际上，很多数据集可能增长非常快。例如空间动态信息等，对于这样的查找表，我们若是保证记录全部按照当中某个关键字有序，其维护的时间代价非常高， 所以这种数据通常是按照先后顺序存储。
对于这样的查找表，我们如何快速的查找到所需要的数据？ ---------- 通过索引
数据结构的最终目的就是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构。
索引就是把一个关键字与他对应的记录相关联的过程，一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。
索引技术是组织大型数据库以及磁盘文件的一种重要技术。
索引按照结构可以分为线性索引，树形索引和多级索引。
所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。
我们重点介绍三种线性索引索引方式：稠密索引，分块索引 和 倒排索引
2. 稠密索引
稠密索引文件的每个记录都有一个索引项，记录在数据区存放是任意的，但索引是按序的，这种索引称为稠密索引。
稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项。
由上图可以知道：对于稠密索引这个索引表而言，索引项一定是按照关键码有序的排列。
2.1 例子：
2.2 小结：
3. 分块索引
3.1 注意理解：
稠密索引是因为索引项和数据集的记录个数相同，所以空间代价很大。
如何减少索引项的个数呢？
我们可以对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项（类似于图书馆的分块）。
3.2 前提：
分块有序是把数据集的记录分成了若干块，并且这些块需要满足两个条件：
（1）块内无序
每一块内的记录不要求有序
（2）块间有序
比如要求第二块所以记录的关键字均要大于第一块中所有记录的关键字，第三块要大于第二块。
只有块间有序才有可能在查找时带来效率。
对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引。
3.3 结构：
分块索引的索引项结构分为三个数据项：
最大关键码--存储每一块中的最大关键字。
存储每一块中记录的个数以便于循环时使用。
用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历。
3.4 查找：
在分块索引表中查找，可以分为两步：
a: 在分块索引表中查找要查的关键字所在块。
由于分块索引表是块间有序的，因此很容易利用折半插值等算法得到结果。
b:根据块首指针找到相应的块，并在块中顺序查找关键码。
因为块中可以是无序的，因此只能顺序查找。
4. 倒排索引
4.1 简介
倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件，简称倒排文件(inverted file)。
倒排文件（倒排索引），索引对象是文档或者文档集合中的单词等，用来存储这些单词在一个文档或者一组文档中的存储位置，是对文档或者文档集合的一种最常用的索引机制。
搜索引擎的关键步骤就是建立倒排索引，倒排索引一般表示为一个关键词，然后是它的频度（出现的次数），位置（出现在哪一篇文章或网页中，及有关的日期，作者等信息），它相当于为互联网上几千亿页网页做了一个索引，好比一本书的目录、标签一般。读者想看哪一个主题相关的章节，直接根据目录即可找到相关的页面。不必再从书的第一页到最后一页，一页一页的查找。
4.2 例子
网友评论