声明：
本博客是本人在学习《大话数据结构》后整理的笔记，旨在方便复习和回顾，并非用作商业用途。
本博客已标明出处，如有侵权请告知，马上删除。
略
只要你打开电脑，就会涉及到查找技术。如炒股软件中查股票信息、硬盘文件中找照片、在光盘中搜 DVD ，甚至玩游戏时在内存中查找攻击力、魅力值等数据修改用来作弊等，都要涉及到查找。当然，在互联网上査找信息就更加是家常便饭。所有这些需要被查的数据所在的集合，我们给它一个统称叫查找表。
査找表（Search Table） 是由同一类型的数据元素（或记录）构成的集合。例如图 8-2-1 就是一个查找表。
关键字（ Key ）是数据元素中某个数据项的值，又称为键值，用它可以标识一个数据元素。也可以标识一个记录的某个数据项（字段），我们称为关键码，如下图中（1）和（2）所示。
若此关键字可以唯一地标识一个记录，则称此关键字为主关键字（ Primary Key ）。 注意这也就意味着，对不同的记录，其主关键字均不相同。主关键字所在的数据项称为主关键码，如下图中（3）和（4）所示。
那么对于那些可以识别多个数据元素（或记录）的关键字，我们称为次关键字（ SecondaryKey ），如下图中（5）所示。次关键字也可以理解为是不以唯一标识一个数据元素（或记录）的关键字，它对应的数据项就是次关键码。
查找（ Searching ）就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。
若表中存在这样的一个记录，则称查找是成功的，此时查找的结果给出整个记录的信息，或指示该记录在查找表中的位置。比如上图所示，如果我们查找主关键码 “代码” 的主关键字为 “sh601398” 的记录时，就可以得到第 2 条唯一记录。如果我们查找次关键码 “涨跌额” 为 “-0.11” 的记录时，就可以得到两条记录。
若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可给出一个 “空” 记录或 “空” 指针。
查找表按照操作方式来分有两大种：静态查找表和动态查找表。
静态査找表（ Static Search Table ）：只作査找操作的查找表。它的主要操作有：
查询某个 “特定的” 数据元素是否在查找表中。检索某个 “特定的” 数据元素和各种属性。按照我们大多数人的理解，查找，当然是在已经有的数据中找到我们需要的。静态查找就是在干这样的事情，不过，现实中还有存在这样的应用：查找的目的不仅仅只是查找。
比如网络时代的新名词，如反应年轻人生活的 “蜗居” 、 “蚁族” 、 “孩奴” 、 “啃老” 等，以及 “X 客” 系列如博客、播客、闪客、黑客、威客等，如果需要将它们收录到汉语词典中，显然收录时就需要查找它们是否存在，以及找到如果不存在时应该收录的位置。再比如，如果你需要对某网站上亿的注册用户进行清理工作，注销一些非法用户，你就需查找到它们后进行删除，删除后其实整个查找表也会发生变化。对于这样的应用，我们就引入了动态査找表。
动态査找表（Dynamic Search Table ）：在査找过程中同时插入査找表中不存在的数据元素，或者从査找表中删除已经存在的某个数据元素。显然动态查找表的操作就是两个：
查找时插入数据元素。
查找时删除数据元素。
为了提高查找的效率，我们需要专门为查找操作设置数据结构，这种面向查找操作的数据结构称为查找结构。
从逻辑上来说，查找所基于的数据结构是集合，集合中的记录之间没有本质关系。可是要想获得较高的查找性能，我们就不能不改变数据元素之间的关系，在存储时可以将査找集合组织成表、树等结构。
例如，对于静态查找表来说，我们不妨应用线性表结构来组织数据，这样可以使用顺序査找算法，如果再对主关键字排序，则可以应用折半查找等技术进行高效的查找。
如果是需要动态查找，则会复杂一些，可以考虑二叉排序树的查找技术。
另外，还可以用散列表结构来解决一些查找问题，这些技术都将在后面的讲解中说明 。
试想一下，要在散落的一大堆书中找到你需要的那本有多么麻烦。碰到这种情况的人大都会考虑做一件事，那就是把这些书排列整齐，比如竖起来放置在书架上，这样根据书名，就很容易查找到需要的图书，如图 8-3-1 所示。
散落的图书可以理解为一个集合，而将它们排列整齐，就如同是将此集合构造成一个线性表。我们要针对这一线性表进行査找操作，因此它就是静态查找表。
此时图书尽管已经排列整齐，但还没有分类，因此我们要找书只能从头到尾或从尾到头一本一本查看，直到找到或全部查找完为止。这就是我们现在要讲的顺序查找。
顺序査找（ Sequential Search ）又叫线性査找，是最基本的査找技术，它的査找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所査的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。
顺序查找的算法实现如下：
/* 顺序查找，a 为数组，n 为要查找的数组个数，key 为要查找的关键字*/ int Sequential_Search(int *a, int n, int key) { int i; for (i = 1; i <= n; i++) { if (a[i] == key) { return i; } } return 0; }这段代码非常简单，就是在数组 a ( 注意元素值从下标 1 开始 ）中查看有没有关键字（ key ），当你需要查找复杂表结构的记录时，只需要把数组 a 与关键字 key 定义成你需要的表结构和数据类型即可。
到这里并非足够完美，因为每次循环时都需要对 i 是否越界，即是否小于等于 n 作判断。事实上，还可以有更好一点的办法，设置一个哨兵，可以解决不需要每次让 i 与 n 作比较。看下面的改进后的顺序查找算法代码。
/* 有哨兵顺序查找 */ int Sequential_Search2(int *a, int n, int key) { int i; a[0] = key; /* 设置 a[0] 为关键字值，我们称之为“哨兵” */ i = n; /* 循环从数组尾部开始 */ while (a[i] != key) { i--; } return i; /* 返回 0 则说明查找失败 */ }此时代码是从尾部开始查找，由于 a[0]=key ，也就是说，如果在 a[i] 中有 key 则返回i值，查找成功。否则一定在最终的 a[0] 处等于 key ，此时返回的是 0 ，即说明 a[1]〜a[n] 中没有关键字 key ，查找失败。
这种在查找方向的尽头放置 “哨兵” 免去了在查找过程中每一次比较后都要判断查找位置是否越界的小技巧，看似与原先差别不大，但在总数据较多时，效率提高很大，是非常好的编码技巧。当然， “哨兵” 也不—定就一定要在数组开始，也可以在末端。
对于这种顺序查找算法来说，查找成功最好的情况就是在第一个位置就找到了，算法时间复杂度为 O(1) ，最坏的情况是在最后一位置才找到，需要 n 次比较，时间复杂度为 O(n) ，当查找不成功时，需要 n+1 次比较，时间复杂度为 O(n) 。我们之前推导过，关键字在任何一位置的概率是相同的，所以平均查找次数为 (n+1)/2 ，所以最终时间复杂度还是 O(n) 。
很显然，顺序查找技术是有很大缺点的，n 很大时，查找效率极为低下，不过优点也是有的，这个算法非常简单，对静态查找表的记录没有任何要求，在一些小型数据的查找时，是可以适用的。
另外，也正由于査找概率的不同，我们完全可以将容易查找到的记录放在前面，而不常用的记录放置在后面，效率就可以有大幅提高。
我们如果仅仅是把书整理在书架上，要找到一本书还是比较困难的，也就是刚才讲的需要逐个顺序査找。但如果我们在整理书架时，将图书按照书名的拼音排序放置，那么要找到某一本书就相对容易了。说白了，就是对图书做了有序排列，一个线性表有序时，对于查找总是很有帮助的。
我们在树结构的二叉树定义时，曾经提到过一个小游戏，我在纸上已经写好了一个 100 以内的正整数数字请你猜，问几次可以猜出来，当时已经介绍了如何最快猜出这个数字。我们把这种每次取中间记录查找的方法叫做折半查找，如图 8-4-1 所示。
折半査找（ Binary Search ）技术，又称为二分査找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。折半査找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则査找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续査找；若给定值大于中间记录的关键字，则在中间记录的右半区继续査找。不断重复上述过程，直到査找成功，或所有査找区域无记录，査找失败为止。
假设我们现在有这样一个有序表数组 { 0， 1， 16， 24， 35， 47， 59， 62， 73， 88， 99 } ，除 0 下标外共 10 个数字。对它进行查找是否存在 62 这个数。我们来看折半查找的算法是如何工作的。
/* 折半查找 */ int Binary_Search(int *a, int n, int key) { int low, high, mid; low = 1; /* 定义最低下标为记录首位 */ high = n; /* 定义最高下标为记录末位 */ while (low <= high) { mid = (low + high) / 2; /* 折半 */ if (key<a[mid]) /* 若查找值比中值小 */ { high = mid - 1; /* 最高下标调整到中位下标小一位 */ } else if (key>a[mid]) /* 若查找值比中值大 */ { low = mid + 1; /* 最低下标调整到中位下标大一位 */ } else { return mid; /* 若相等则说明 mid 即为查找到的位置 */ } } return 0; }程序开始运行，参数 a={ 0， 1， 16， 24， 35， 47， 59， 62， 73， 88， 99 } ， n=10 ， key=62 ，第 3〜6 行，此时 low=1 ， high=10 ，如图 8-4-2 所示。
第 7〜22 行循环，进行查找。
第 9 行，mid 计算得 5 ，由于 a[5]=47<key ，所以执行了第 17 行， low=5+1=6 ，如图 8-4-3 所示。
再次循环，mid=(6+10)/2=8 ，此时 a[8]=73>key ，所以执行第 12 行， high=8-1=7 ，如图 8-4-4 所示。
再次循环，mid=(6+7)/2=6 ，此时 a[6]=59<key ，所以执行 17 行， low=6+1=7 ，如图 8-4-5 所示。
再次循环，mid=(7+7)/2=7 ，此时 a[7]=62=key ，査找成功，返回 7 。
该算法还是比较容易理解的，同时我们也能感觉到它的效率非常高。但到底高多少？关键在于此算法的时间复杂度分析。
首先，我们将这个数组的查找过程绘制成一棵二叉树，如图 8-4-6 所示，从图上就可以理解，如果查找的关键字不是中间记录 47 的话，折半查找等于是把静态有序查找表分成了两棵子树，即查找结果只需要找其中的一半数据记录即可，等于工作量少了一半，然后继续折半查找，效率当然是非常高了。
我们之前讲的二叉树的性质 4：" 具有 n 个结点的完全二叉树的深度为 [log2n]+1 "。在这里尽管折半查找判定二叉树并不是完全二叉树，但同样相同的推导可以得出，最坏情况是查找到关键字或查找失败的次数为 [log2n]+1。
有人还在问最好的情况？那还用说吗，当然是 1 次了。
因此最终我们折半算法的时间复杂度为 O(logn) ，它显然远远好于顺序查找的 O(n) 时间复杂度了。
不过由于折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，这样的算法已经比较好了。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。
现在我们的新问题是，为什么一定要折半，而不是折四分之一或者折更多呢？
打个比方，在英文词典里查 “apple”，你下意识里翻开词典是翻前面的书页还是后面的书页呢？如果再让你查 “zoo”，你又怎么查？很显然，这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻。
同样的，比如要在取值范围 0~10000 之间 100 个元素从小到大均匀分布的数组中查找 5，我们自然会考虑从数组下标较小的开始查找。
看来，我们的折半查找，还是有改进空间的。
折半查找代码的第 9 句，我们略微等式变换后得到：
也就是 mid 等于最低下标 low 加上最高下标 high 与 low 的差的一半。算法科学家们考虑的就是将这个 1/2 进行改进，改进为下面的计算方案：
将 1/2 改成了 有什么道理呢？假设 a[11]={ 0， 1， 16， 24， 35， 47， 59， 62， 73， 88， 99 }，low=1 , high = 10 ，则 a[low]=1 ， a[high]=99 ，如果我们要找的是 key=16 时，按原来折半的做法，我们需要四次（如图 8-4-6 所示）才可以得到结果，但如果用新办法， ，即 取整得到 mid=2 ，我们只需要二次就查找到结果了，显然大大提高了查找的效率。
换句话说，我们只需要在折半查找算法的代码中更改一下第 9 行代码如下：
mid=low+ ( high-low )*( key-a[low] )/( a[high]-a[low] ); /* 插值 */就得到了另一种有序表查找算法，插值查找法。插值査找（ Interpolation Search ）是根据要查找的关键字 key 与查找表中最大最小记录的关键字比较后的查找方法其核心就在于插值的计算公式 。
应该说，从时间复杂度来看，它也是 O(logn) 但对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好得多。反之，数组中如果分布类似 {0，1，2，2000，2001，……， 999998， 999999 } 这种极端不均匀的数据，用插值查找未必是很合适的选择。
还有没有其他办法？我们折半查找是从中间分，也就是说，每一次查找总是一分为二，无论数据偏大还是偏小，很多时候这都未必就是最合理的做法。除了插值查找，我们再介绍一种有序查找，斐波那契查找（Fibonacci Search），它是利用了黄金分割原理来实现的。
为了能够介绍清楚这个查找算法，我们先需要有一个斐波那契数列的数组，如图 8-4-8 所示。
下面我们根据代码来看程序是如何运行的。
/*斐波那契查找*/ int Fibonacci_Search(int *a, int n, int key) { int low, high, mid, i, k; low = 1; /* 定义最低下标为记录首位 */ high = n; /* 定义最高下标为记录末位 */ k = 0; while (n > F[k] - 1) /* 计算 n 位于斐波那契数列的位置 */ { k++; } for (i = n; i < F[k] - 1; i++) /* 将不满的数值补全 */ { a[i] = a[n]; } while (low <= high) { mid = low + F[k - 1] - 1; /* 计算当前分隔的下标 */ if (key<a[mid]) /* 若查找记录小于当前分隔记录 */ { high = mid - 1; /* 最高下标调整到分隔下标 mid-1 处 */ k = k - 1; /* 斐波那契数列下标减一位 */ } else if (key>a[mid]) /* 若査找记录大于当前分隔记录 */ { low = mid + 1; /* 最低下标调整到分隔下标 mid+1 处 */ k = k - 2; /* 斐波那契数列下标减两位 */ } else { if (mid <= n) { return mid; /* 若相等则说明 mid 即为查找到的位置 */ } else { return n; /* 若 mid>n 说明是补全数值，返回n */ } } } return 0; }程序开始运行，参数 a={ 0， 1， 16， 24， 35， 47， 59， 62， 73， 88， 99 } ， n=10 ，要查找的关键字 key=59 。注意此时我们已经有了事先计算好的全局变量数组 F 的具体数据，它是斐波那契数列，F={ 0， 1， 1， 2， 3， 5， 8， 13， 21， …… }。
第 7〜11 行是计算当前的 n 处于斐波那契数列的位置。现在 n=10 ，F[6]<n<F[7] ，所以计算得出 k=7 。
第 12〜15 行，由于 k=7 ，计算时是以 F[7]=13 为基础，而 a 中最大的仅是 a[10] ，后面的 a[11] ， a[12] 均未赋值，这不能构成有序数列，因此将它们都赋值为最大的数组值，所以此时 a[11]=a[12]=a[10]=99 （此段代码作用后面还有解释）。
第 16〜40 行査找正式开始。
第 18 行，mid=1+ F[7-1]-1=8 ，也就是说，我们第一个要对比的数值是从下标为 8 开始的。
由于此时 key=59 而 a[8]=73 ，因此执行第 21〜22 行，得到 high=7 ， k=6 。
再次循环， mid=1 + F[6-1]-1=5 。此时 a[5]=47<key ，因此执行第 26〜27 行，得到 low=6 , k=6-2=4 。注意此时 k 下调 2 个单位。
再次循环， mid=6 + F[4-1]-1=7 。此时 a[7]=62>key ,因此执行第 21〜22 行，得到 high=6 , k=4-1=3 。
再次循环， mid=6 + F[3-1]-1=6 。此时 a[6]=59=key ,因此执行第 31〜34 行，得到返回值为 6 。程序运行结束。
如果 key=99 ，此时查找循环第一次时， mid=8 与上例是相同的，第二次循环时， mid=11 ，如果 a[11] 没有值就会使得与 key 的比较失败，为了避免这样的情况出现， 第 12〜15 行的代码就起到这样的作用。
斐波那契查找算法的核心在于：
当 key=a[mid] 时，査找就成功；当 key<a[mid] 时，新范围是第 low 个到第 mid-1 个，此时范围个数为 F[k-1]-1 个；当 key>a[mid] 时，新范围是第 m+1 个到第 high 个，此时范围个数为 F[k-2]-1 个。也就是说，如果要查找的记录在右侧，则左侧的数据都不用再判断了，不断反复进行下去，对处于当中的大部分数据，其工作效率要高一些。所以尽管斐波那契查找的时间复杂也为 O(logn)，但就平均性能来说，斐波那契查找要优于折半查找。可惜如果是最坏情况，比如这里 key=1 ，那么始终都处于左侧长半区在查找，则查找效率要低于折半查找。
应该说，三种有序表的查找本质上是分隔点的选择不同，各有优劣，实际开发时可根据数据的特点综合考虑再做出选择。
我们前面讲的几种比较髙效的查找方法都是基于有序的基础之上的，但事实上，很多数据集可能增长非常快，例如，某些微博网站或大型论坛的帖子和回复总数每天都是成百万上千万条，如图 8-5-1 所示，或者一些服务器的日志信息记录也可能是海量数据，要保证记录全部是按照当中的某个关键字有序，其时间代价是非常高昂的，所以这种数据通常都是按先后顺序存储。
那么对于这样的查找表，我们如何能够快速查找到需要的数据呢？办法就是——索引。
数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构。索引就是把一个关键字与它对应的记录相关联的过程，一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。索引技术是组织大型数据库以及磁盘文件的一种重要技术。
索引按照结构可以分为线性索引、树形索引和多级索引。我们这里就只介绍线性索引技术。所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。我们重点介绍三种线性索引：稠密索引、分块索引和倒排索引。
我母亲年纪大了，记忆力不好，经常在家里找不到东西，于是她想了一个办法。她用一个小本子记录了家里所有小东西放置的位置，比如户口本放在右手床头柜下面抽屉中，针线放在电视柜中间的抽屉中，钞票放在衣柜……总之，她老人家把这些小物品的放置位置都记录在了小本子上，并且每隔一段时间还按照本子整理一遍家中的物品，用完都放回原处，这样她就几乎再没有找不到东西。
记得有一次我申请职称时，单位一定要我的大学毕业证，我在家里找了很长时间未果，急得要死。和老妈一说，她的神奇小本子马上发挥作用，一下子就找到了，原来被她整理后放到了衣橱里的抽屉里。
从这件事情就可以看出，家中的物品尽管是无序的，但是如果有一个小本子记录，寻找起来也是非常容易的，而这小本子就是索引。
稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项，如图 8-5-2 所示。
刚才的小例子和稠密索引还是略有不同，家里的东西毕竟少，小本子再多也就几十页，全部翻看完就几分钟时间，而稠密索引要应对的可能是成千上万的数据，因此对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列。
索引项有序也就意味着，我们要查找关键字时，可以用到折半、插值、斐波那契等有序查找算法，大大提高了效率。比如上图中，我要查找关键字是 18 的记录， 如果直接从右侧的数据表中查找，那只能顺序查找，需要查找 6 次才可以查到结果。 而如果是从左侧的索引表中査找，只需两次折半查找就可以得到 18 对应的指针，最终查找到结果。
这显然是稠密索引优点。但是如果数据集非常大，比如上亿，那也就意味着索引也得同样的数据集长度规模，对于内存有限的计算机来说，可能就需要反复去访问磁盘，查找性能反而大大下降了。
回想一下图书馆是如何藏书的。显然它不会是顺序摆放后，给我们一个稠密索引表去查，然后再找到书给你。图书馆的图书分类摆放是一门非常完整的科学体系，而它最重要的一个特点就是分块。
稠密索引因为索引项与数据集的记录个数相同，所以空间代价很大。为了减少索引项的个数，我们可以对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项，从而减少索引项的个数。
分块有序，是把数据集的记录分成了若干块，并且这些块需要满足两个条件：
块内无序，即每一块内的记录不要求有序。当然，你如果能够让块内有序对查找来说更理想，不过这就要付出大量时间和空间的代价，因此通常我们不要求块内有序。块间有序，例如，要求第二块所有记录的关键字均要大于第一块中所有记录的关键字，第三块的所有记录的关键字均要大于第二块的所有记录关键字…… 因为只有块间有序，才有可能在查找时带来效率。对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引。
如图 8-5-4 所示，我们定义的分块索引的索引项结构分三个数据项：
最大关键码，它存储每一块中的最大关键字，这样的好处就是可以使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大；存储了块中的记录个数，以便于循环时使用；用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历。在分块索引表中查找，就是分两步进行：
在分块索引表中查找要查关键字所在的块。由于分块索引表是块间有序的， 因此很容易利用折半、插值等算法得到结果。例如，在上图的数据集中查找 62 ，我们可以很快可以从左上角的索引表中由 57<62<96 得到 62 在第三个块中。
根据块首指针找到相应的块，并在块中顺序查找关键码。因为块中可以是无序的，因此只能顺序查找。
我们再来分析一下分块索引的平均查找长度。设 n 个记录的数据集被平均分成 m 块，每个块中有 t 条记录，显然 n=m x t ，或者说 m = n/t 。再假设 Lb 为查找索引表的平均查找长度，因最好与最差的等概率原则，所以 Lb 的平均长度为 (m+1)/2 。Lw 为块中查找记录的平均查找长度，同理可知它的平均查找长度为 (t+1)/2 。
这样分块索引查找的平均查找长度为：
注意上面这个式子的推导是为了让整个分块索引查找长度依赖 n 和 t 两个变量。 从这里了我们也就得到，平均长度不仅仅取决于数据集的总记录数 n ，还和每一个块的记录个数 t 相关。最佳的情况就是分的块数 m 与块中的记录数 t 相同，此时意味着 n= m x t = t^2，即
可见，分块索引的效率比之顺序查找的 O(n) 是高了不少，不过显然它与折半查找的 O(logn) 相比还有不小的差距。因此在确定所在块的过程中，由于块间有序，所以可以应用折半、插值等手段来提高效率。
总的来说，分块索引在兼顾了对细分块不需要有序的情况下，大大增加了整体查找的速度，所以普遍被用于数据库表查找等技术的应用当中。
不知道大家有没有对搜索引擎好奇过，无论你查找什么样的信息，它都可以在极短的时间内给你一些结果，如图 8-5-5 所示。是什么算法技术达到这样的高效查找呢？
在这里介绍最简单的，也算是最基础的搜索技术——倒排索引。
我们来看样例，现在有两篇极短的英文“文章” ——其实只能算是句子，我们暂认为它是文章，编号分别是1 和 2 。
Books and friends should be few but good （ 读书如交友，应求少而精 ）
A good book is a good friend （ 好书如挚友 ）
假设我们忽略掉如 “books” 、 “friends” 中的复数 “s” 以及如 “A” 这样的大小写差异。我们可以整理出这样一张单词表，如表 8-5-1 所示，并将单词做了排序，也就是表格显示了每个不同的单词分别出现在哪篇文章中，比如 “good” 它在两篇文章中都有出现，而 “is” 只是在文章 2 中才有。
有了这样一张单词表，我们要搜索文章，就非常方便了。如果你在搜索框中填写 “book” 关键字。系统就先在这张单词表中有序査找 “book” ，找到后将它对应的文章编号 1 和 2 的文章地址（通常在搜索引擎中就是网页的标题和链接）返回，并告诉你，查找到两条记录，用时 0.0001 秒。由于单词表是有序的，查找效率很高，返回的又只是文章的编号，所以整体速度都非常快。
如果没有这张单词表，为了能证实所有的文章中有还是没有关键字 “book” ，则需要对每一篇文章每一个单词顺序查找。在文章数是海量的情况下，这样的做法只存在理论上可行性，现实中是没有人愿意使用的。
在这里这张单词表就是索引表，索引项的通用结构是：
次关键码，例如上面的 “英文单词” ；记录号表，例如上面的 “文章编号” 。其中记录号表存储具有相同次关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字)。这样的索引方法就是倒排索引（ inverted index ）。倒排索引源于实际应用中需要根据属性（或字段、次关键码）的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引。
倒排索引的优点显然就是查找记录非常快，基本等于生成索引表后，查找时都不用去读取记录，就可以得到结果。但它的缺点是这个记录号不定长，比如上例有 7 个单词的文章编号只有一个，而 “book” 、 “friend” 、 “good” 有两个文章编号，若是对多篇文章所有单词建立倒排索引，那每个单词都将对应相当多的文章编号，维护比较困难，插入和删除操作都需要作相应的处理。
