1．索引

索引是计算机中最常见的提高检索效率的手段，在数据库系统和用户自定义存储结构中被广泛使用。就其本质而言，它是一种“空间换时间”的方法，可以提高检索速度、节约时间，但是索引本身要占用一定的存储空间。

2．倒排索引

随着信息爆炸以及海量数据的出现，信息检索系统，尤其是Web信息检索系统的准确高效检索遇到了很大的压力，因为Web信息检索不是简单地在一个文档中查找指定的词，而是需要利用指定的词找出所有包含该词语的文档。在一个文档中找指定的词，可以看成是一个子串匹配问题。由Knuth，Morris，Pratt共同提出的KMP算法，是一个非常优秀的子串匹配算法，它对于各种情况，都可以在线性时间内完成匹配查找。但是如果对海量文档中每一个文档运行一次KMP匹配算法，将是一个不可接受的时间开销。

如果在检索之前，已经有一个数据结构存储了包含每个检索词的对应文档集合，那么检索效率将会急剧提高。因此倒排索引应运而生。倒排索引是现代信息检索系统的核心部分，其组织方式和存储结构对信息检索系统的性能有很大的影响。

倒排索引主要由词典和倒排链两个部分组成。词典记录了需要被检索的所有词条项和对应倒排链指针。对于一个查询词条项，查找其是否出现在词典中，如果找到就可以直接获取到倒排链指针，也就是就直接快速获取到了文档集合。为了满足快速索引构建和词项查找需求，词典本身通常是利用Hash表或者二叉搜索树形结构实现；出现在词典中的每个词项都对应一个倒排链，最简单的倒排链存储了包含该此项的所有文档ID列表。

3．Hash

Hash被直接音译为“哈希”，它也叫散列。它的任务是通过散列算法把变长的输入转换成定长的输出，这个输出就是散列值。这种转换实质是一种压缩映射，因为：散列值的空间通常远小于输入的空间，但是不同的输入可能会散列成相同的输出，称之为碰撞。hash目前被广泛应用在文件校验、数字签名和鉴权协议等领域，md5和sha1是两个著名的hash计算方法，并且md5和sha1的采用了杂凑的方法进行哈希，基本上不可能找到碰撞。

4．二叉排序树

二叉排序树，又叫二叉查找树、二叉搜索树，是一个可以快速检索的数据结构。图1就是一个二叉排序树的例子，二叉排序树的定义如下：

二叉排序树可以是一棵空树，或者是具有下列性质的二叉树：

（1）如果左子树不空，则左子树上所有结点的键值均小于它的根结点的值；

（2）如果右子树不空，则右子树上所有结点的键值均大于或等于它的根结点的键值；

（3）左、右子树也分别为二叉排序树；

（4）整个树中没有键值相等的节点。

图1 一个二叉排序树的例子

因为二叉排序树以及每个子树都能保证根节点的键值大于左子树同时小于右子树，因此可以在检索时，每次排除一棵子树，检索效率高。检索算法如下：

（1）让p指向根节点

（2）若p的键值等于查找的内容，成功，结束查找。

（3）若p的键值大于查找的内容，p等于p的左儿子。

（4）若p的键值小于查找的内容，p等于p的右儿子。

（5）若p为空，结束，查找不成功。

（6）如p不为空，则转（2）。

5．平衡二叉搜索树

二叉排序树在结果添加、删除等一系列操作之后，很容易发生向一个方向偏沉，最极端的情况是每个节点都只有一个子树，此时相当于退化成了一个链表，增加了访问操作时间，图2就展示了一个极端的二叉排序树。而平衡二叉树具有良好的稳定性，可以有效保证检索效率。

图2 一个退化的二叉排序树

平衡二叉搜索树可以是一个空树，或者具有以下性质：

(1)它的左右两个子树的高度差的绝对值不超过1;

(2)并且左右两个子树都是一棵平衡二叉搜索树。

著名的平衡二叉搜索树有：AVL树、红黑树、Treap树和伸展树等。通常它们在插入和删除时都能保持自平衡，因此插入和删除的速度略低于二叉排序树，但是由于保持了平衡，因此具有极好的稳定性。

6.基于哈希表的倒排索引

一个良好的哈希函数不仅应该计算简单，而且应该使得哈希地址尽可能均匀地连续分布，此外需要降低碰撞发生的可能性。因为计算简单可以降低计算复杂度，均匀连续分布将大大有利于将哈希表加载到内存，较低的碰撞同样可以提高效率。

常见的哈希函数构造方法有：直接定址法、除留余数法、数字分析法、平方取中法、移位法等。BKDRHash算法是一个经典的字符串哈希算法，为了充分离散数据，它没有直接把字符串中的字符累加，而是把字符串中每个字符乘以一个种子之后累加，最后为了控制哈希表的空间，把累加结果进行一次求余，该算法简单明了，容易实现。

如果哈希表本身无碰撞，那么可以使用如图3的存储结构来存储倒排索引，但是由于待哈希的字符串的数量很大，为了避免碰撞而设计的散列函数可能会很复杂，而且可能图3左侧的列表也会因为包含了大量的空位而变得巨大。因此在图3的基础上稍作变换，可以得到加入碰撞处理的哈希表，该表的结构参见图4，其中右侧的数据结构比3中多了一个指针。

图3 一种无碰撞的倒排索引哈希表结构

图4 一种处理碰撞的倒排索引哈希表结构

7.AVL树的基本操作

AVL树是最早被发明的平衡二叉搜索树，它得名于发明者 G.M. Adelson-Velsky 和 E.M. Landis。AVL树通常在每个节点中存储它的平衡因子，所谓平衡因子就是一个节点的左子树的高度减去右子树的高度，按照平衡二叉搜索树的定义，平衡因子应该的取值是-1、0和1，但如果经过插入和删除操作后，该值可能变为2或者-2，此时就说明该子树已经不平衡，此时需要通过称为“旋转”的操作来平衡这个树。

旋转

所谓旋转就是找到不平衡的最小子树的根节点X，然后将X用其子树的一个根节点Y替换，图5就显示了两个右旋的例子。

图5 两个通过旋转后重新平衡的例子

假设由于在AVL树上因为插入结点而失去平衡的最小子树根结点为X（即X是离插入点最近，且平衡因子绝对值超过1的祖先结点），则失去平衡后通过旋转重新平衡的规律可归纳为下列四种情况：

单向右旋平衡处理LL：由于在X的左子树根结点的左子树上插入结点，X的平衡因子由1增至2，致使以X为根的子树失去平衡，则需进行一次右旋转操作；

单向左旋平衡处理RR：由于在X的右子树根结点的右子树上插入结点，X的平衡因子由-1变为-2，致使以X为根的子树失去平衡，则需进行一次左旋转操作；

双向旋转（先左后右）平衡处理LR：由于在X的左子树根结点的右子树上插入结点，X的平衡因子由1增至2，致使以X为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。

双向旋转（先右后左）平衡处理RL：由于在X的右子树根结点的左子树上插入结点，X的平衡因子由-1变为-2，致使以X为根的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。

插入

可以首先检索到需要插入的位置，然后进行插入，如果插入后树失去了平衡，重新平衡该树。

删除

如果要删除的节点是叶子那么直接删除，否则可以把待删除节点旋转成一个叶子节点，接着直接剪除这个叶子节点来完成。如果删除后不平衡，重新平衡该树。

检索

因为二叉平衡树的每个节点的左右子树大致相等，因此其检索本质上是把传统的二分检索从线性表拓展到了树形结构上。

3.基于AVL树的倒排索引

基于AVL树的倒排索引在存储空间的需求上是低于哈希表的，首先，不像哈希表通常必须占用连续内存，AVL树的每个节点可以是动态从堆中申请内存；第二，不存在哈希表中的空位问题，此外也无需考虑与处理哈希的碰撞问题。图6就是一个基于AVL树倒排索引的结构，其中每个节点有四个指针，分别指向父节点、左儿子、右儿子和文档编号链表，但是为了描述简单，每个节点的单词、平衡因子等信息未在图中展示。

图6 一个基于AVL树的倒排索引结构

从图6可以看出，该结构中的每个节点的指针使用略复杂。该索引生成的步骤为：依次读取文档，首先把每个文档中的单词去除重复，从而得到唯一单词清单，然后依次用单词清单中的单词到AVL树检索是否存在此单词的节点，如果不存在就增加节点，并根据情况调整树的平衡，如果已经存在则更新该节点的文档编号列表。这样最终就可以得到一个基于AVL树的倒排索引。

参考文献