背景

在关系型数据库中，索引是检索数据的最有效率方式，但是在海量的数据中，需要实时检索数据的时候，关系型数据库的索引方式在性能方面并不能满足我们的检索要求。打个比方：搜索引擎面对的是海量数据，像Google，百度这样大型的商业搜索引擎索引都是亿级甚至百亿级的网页数量 ，面对如此海量数据 ,使得数据库系统很难有效的管理。于是在很多搜索引擎中出现了一种相对于我们传统的正序索引相反的一种索引：倒排索引或反序索引，官方的名称是：inverted index 。

倒排索引

1）基本概念

概括《这就是搜索引擎-核心技术详解》总结出来就是：索引表包括了每条记录的属性值和属性值记录的地址，检索的时候，通过属性值来确定该条记录的位置，而不是像传统索引那样通过属性来确定属性值，通俗的说就是不在是通过key寻找value，而是通过value寻找key。也许这么阐述还是有点抽象，那么我们先了解倒排索引有关的几个概念，然后一点点深入。

文档

一般搜索引擎的处理对象是互联网网页，而文档这个概念更要宽泛一些，代表以文本形式存在的存储对象。相比于网页来说，涵盖更多形式，比如Word、PDF、html、XML等不同格式的文件都可以称为文档，再比如一封邮件、一条短信、一条微博也可以称为文档。

文档集合

顾名思义，一组或多个文档构成的集合，比如海量的互联网网页或者大量的电子邮件，都是文档集合的具体例子。

文档编号

在搜索引擎内部，会为文档集合內每个文档赋予一个唯一的内部编号，以此编号作为这个文档的唯一标识，这样方便内部处理。

单词编号（重点）

与文档编号类似，搜索引擎内部以唯一的编号来表征某个单词，单词编号可以作为某个单词的唯一表征。

倒排索引（重点）

倒排索引是实现单词——文档矩阵（文档矩阵如下图1，为了方便看，就不直接采用书上的截图，而是采用网友们的图）的一种具体存储形式。通过倒排索引，可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成：单词词典和倒排文件。

单词词典（重点）

搜索引擎通常的索引单位是单词，单词词典是由文档集合中出现过的所有单词构成的字符串集合，单词词典內每条索引项记载单词本身的一些信息及指向倒排列表的指针。所以在用户进行查询的时候，搜索引擎根据用户的查询词，去单词词典里查询，就能够获得相应的倒排列表，并以此作为后续排序的基础。

对于一个规模很大的文档集合来说，可能包含几十万甚至上百万不同的单词，能否快速定位某个单词，这直接影响搜索时的相应速度，常用的数据结构包括哈希加链表结构和树形词典结构。

倒排列表

倒排列表记载了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息，每条记录称为一个倒排项（Posting）。根据倒排列表，即可获知哪些文档包含某个单词。

倒排文件

所有单词的倒排列表往往顺序地存储在磁盘的某个文件里，这个文件即被称为倒排文件，倒排文件是存储倒排索引的物理文件。

单词-文档矩阵：（单词即一段文档或者句子中的某个单词，英文以空格分割，文档即一段句子或者一段文章）

图1

稍微简述一下，上述图中的意思，我们首先把文档看作一段英文句子，也就是说句子1，2，3，4，5在横列中，然后每段句子构成的单词在列中，如果单词在某个句子出现过，就在该句子与单词构成的矩阵交集处打勾，这样就构成了我们单词文档矩阵。

将上面的索引的元素组成后，大致关系图如下图2所示（由于书上的图依旧不清晰，所以还是采用网上其他同学的图）：

图2

上面的图也稍微解释一下：

单词的集合组成了词典，每个单词与文档的组合组成了倒排索引，倒排索引的结汇组成了倒排列表，倒排列表组成了倒排文件。

倒排索引实例

这里我们就引用书中的例子：

图1

图1中有5个句子，然后我们把每句话的词汇和句子构成单词-文档矩阵，第一列给每个单词一个编号，即我们前面说的单词编号，便于检索时候使用，第二列是单词，第三列是每一个单词在哪里句子里面出现的。然后这种索引列表过于简单，我们可以继续在图2中我们在倒排列表中加入每一个单词在每一个句子里面出现的频率

图2

图3

如图3所示，我们看到倒排列表中，增加了每一个词汇在句子出现的编号以及出现的频率，当然这样还是很简单，并不达到我们的预期索引系统，于是我们可以在增加单词频率的基础上加入文档频率，即代表有多少个文档包含了这类单词。

图4

如图4所示：我们以“拉斯”为例子，其单词编号为8，文档频率为2，代理整个文档中有两个文档包含这个单词，对应倒排列表是：{(3;1,<4>),(5;1,<4>)},其含义就是“拉斯”在文档3和文档5各出现一次，位置在第四个词的位置。上述的例子即是一个完整的倒排索引系统，在实际应用中无非采取哪种数据的方式而已。

索引的存储结构

单词词典是倒排索引中非常重要的组成部分，它用来维护文档集合中出现过的所有单词的相关信息，同时用来记载某个单词对应的倒排列表在倒排文件中的位置信息。在支持搜索时，根据用户的查询词，去单词词典里查询，就能够获得相应的倒排列表，并以此作为后续排序的基础。

1）Hash的存储方式

在建立索引的过程中，词典结构也会相应地被构建出来。比如在解析一个新文档的时候，对于某个在文档中出现的单词T，首先利用哈希函数获得其哈希值，之后根据哈希值对应的哈希表项读取其中保存的指针，就找到了对应的冲突链表。如果冲突链表里已经存在这个单词，说明单词在之前解析的文档里已经出现过。如果在冲突链表里没有发现这个单词，说明该单词是首次碰到，则将其加入冲突链表里。这样的存储方式很类似于Java中HashMap解决hash冲突的方式。

2）树形结构

B树（或者B+树的）存储方式，这点很类似于Mysql的Inoodb的存储引擎中采用B+树的方式来存储索引，由于采用了B树的结构，即索引存储在是一个平衡树，避免了查询极端的情况，由于有序，所以能根据字典项需要的大小顺序来构建索引，这样在检索中可以快速通过字典项比较大小，最终确定叶子结点中词汇的存储地址信息。（由于B树的构建复杂，这里就不过多的讲解，向深入了解，可以翻翻上学那会儿的《数据结构》那本书喔）

总结

上面大致粗略的讲解了一下倒排索引的概念，其实在实际中，倒排索引还会进行索引压缩，排序的加工，也正因为这些加工，让其成为目前许多搜索引擎采用的索引方式。由于博主也是最近才介入搜索相关的工作，对于搜索引擎的话，还在初探阶段，如有更好的见解，欢迎一起来学习。