试想这样一个场景：假设你已经熟读唐诗 300 首了。这个时候，如果我给你一首诗的题目，你可以马上背出这首诗的内容吗？相信你一定可以的。但是如果我问你，有哪些诗中同时包含了「极」字和「客」字？你就不见得能立刻回答出来了。你需要在头脑中一首诗一首诗地回忆，并判断每一首诗的内容是否同时包含了极字和客字。很显然，第二个问题的难度比第一个问题大得多。
那从程序设计的角度来看，这两个问题对应的检索过程又有什么不同呢？今天，我们就一起来聊一聊，两个非常常见又非常重要的检索技术：正排索引和倒排索引。
什么是倒排索引？
我们先来看比较简单的那个问题：给出一首诗的题目，马上背出内容。这其实就是一个典型的 键值查询场景。针对这个场景，我们可以给每首诗一个唯一的编号作为 ID，然后使用哈希表将诗的 ID 作为键（Key），把诗的内容作为键对应的值（Value）。这样，我们就能在 O(1) 的时间代价内，完成对指定 key 的检索。这样一个以对象的唯一 ID 为 key 的哈希索引结构，叫作 正排索引（Forward Index）。
键值(文档唯一标识)字符数组(内容)word20doc1word2word3word1word2word33word5doc2word4word8word57docnword3word7
image.png
哈希表存储所有诗
一般来说，我们会遍历哈希表，遍历的时间代价是 O(n)。在遍历过程中，对于遇到的每一个元素也就是每一首诗，我们需要遍历这首诗中的每一个字符，才能判断是否包含极字和客字。假设每首诗的平均长度是 k，那遍历一首诗的时间代价就是 O(k)。从这个分析中我们可以发现，这个检索过程全部都是遍历，因此时间代价非常高。对此，有什么优化方法吗？
我们先来分析一下这两个场景。我们会发现，「根据题目查找内容」和「根据关键字查找题目」，这两个问题其实是完全相反的。既然完全相反，那我们能否「反着」建立一个哈希表来帮助我们查找呢？也就是说，如果我们以关键字作为 key 建立哈希表，是不是问题就解决了呢？接下来，我们就试着操作一下。
我们将每个关键字当作 key，将包含了这个关键字的诗的列表当作存储的内容。这样，我们就建立了一个哈希表，根据关键字来查询这个哈希表，在 O(1) 的时间内，我们就能得到包含该关键字的文档列表。这种根据具体内容或属性反过来索引文档标题的结构，我们就叫它 倒排索引（Inverted Index）。在倒排索引中，key 的集合叫作 字典（Dictionary），一个 key 后面对应的记录集合叫作 记录列表（Posting List）。
文档列表key(关键字唯一标识)doc19doc2doc1word1doc20doc19doc34word2doc1doc20doc53wordn
image.png
倒排索引
如何创建倒排索索引？
前面我们介绍了倒排索引的概念，那创建一个倒排索引的过程究竟是怎样的呢？我把这个过程总结成了以下步骤。
1
给每个文档编号，作为其唯一的标识，并且排好序，然后开始遍历文档（为什么要先排序，然后再遍历文档呢？你可以先想一下，后面我们会解释）。
2
解析当前文档中的每个关键字，生成 < 关键字，文档 ID，关键字位置 > 这样的数据对。为什么要记录关键字位置这个信息呢？因为在许多检索场景中，都需要显示关键字前后的内容，比如，在组合查询时，我们要判断多个关键字之间是否足够近。所以我们需要记录位置信息，以方便提取相应关键字的位置。
3
将关键字作为 key 插入哈希表。如果哈希表中已经有这个 key 了，我们就在对应的 posting list 后面追加节点，记录该文档 ID（关键字的位置信息如果需要，也可以一并记录在节点中）；如果哈希表中还没有这个 key，我们就直接插入该 key，并创建 posting list 和对应节点。
4
重复第 2 步和第 3 步，处理完所有文档，完成倒排索引的创建。
如果该key已经存在,直接在postinglist尾部插入节点word1doc2doc1位置关键字文档IDword插入哈希表分析文档word2Word1[1,3]Doc2worddoc2word2[2]Word2Doc2doc2如果该key在倒排表中不存在,插入该key,并创建postingist
image.png
将一个文档解析并加入倒排索引
如何查询同时含有「极」字和「客」字两个 key 的文档？
如果只是查询包含「极」或者「客」这样单个字的文档，我们直接以查询的字作为 key 去倒排索引表中检索，得到的 posting list 就是结果了。但是，如果我们的目的是要查询同时包含极和客这两个字的文档，那我们该如何操作呢？
我们可以先分别用两个 key 去倒排索引中检索，这样会得到两个不同的 posting list：A 和 B。A 中的文档都包含了极字，B 中文档都包含了客字。那么，如果一个文档既出现在 A 中，又出现在 B 中，它是不是就同时包含了这两个字呢？按照这个思路，我们 只需查找出 A 和 B 的公共元素 即可。
那么问题来了，我们该如何在 A 和 B 这两个链表中查找出公共元素呢？如果 A 和 B 都是无序链表，那我们只能将 A 链表和 B 链表中的每个元素分别比对一次，这个时间代价是 O(m*n)。但是，如果两个链表都是有序的，我们就可以用 归并排序 的方法来遍历 A 和 B 两个链表，时间代价会降低为 O(m + n)，其中 m 是链表 A 的长度，n 是链表 B 的长度。
我把链表归并的过程总结成了 3 个步骤，你可以结合我在图片中给出的例子来理解。
第 1 步，使用指针 p1 和 p2 分别指向有序链表 A 和 B 的第一个元素。
第 2 步，对比 p1 和 p2 指向的节点是否相同，这时会出现 3 种情况：
■
两者的 id 相同，说明该节点为公共元素，直接将该节点加入归并结果。然后，p1 和 p2 要同时后移，指向下一个元素；
■
p1 元素的 id 小于 p2 元素的 id，p1 后移，指向 A 链表中下一个元素；
■
p1 元素的 id 大于 p2 元素的 id，p2 后移，指向 B 链表中下一个元素。
第 3 步，重复第 2 步，直到 p1 或 p2 移动到链表尾为止。
p1链表Adoc5doc6worddoc3doc2docp2p1小于p2,p1要后移一位)Step1链表Bdoc5docdoc4word2p1链表Adoc6doc3doc5docdoc2wOrd52Step2p1-p2,找到公共元素doc2,p1和p2都要后移一位链表Bword2doc2doc5doc4p1链表Adoc6doc5doc3docworddocp2P1小于p2,p1要后移一位Step3:链表Bword2doc4doc2docp1链表Adoc5doc6doc3docdocwordp2p1大于p2,p2要后移一位Step4:链表Bdoc4doc5doc2word2p链表Adoc6doc2doc3doc5doc1worD1Step5:链表Bdoc2doc5word2doc4pl-p2,找到公共元素doC5,p1和2都要后移一位,p2已到链表尾,算法结束
image.png
链表归并提取公共元素例子
那对于 两个 key 的联合查询来说，除了有「同时存在」这样的场景以外，其实还有很多联合查询的实际例子。比如说，我们可以查询包含「极」或「客」字的诗，也可以查询包含「极」且不包含「客」的诗。这些场景分别对应着集合合并中的 交集、并集和差集 问题。它们的具体实现方法和「同时存在」的实现方法差不多，也是通过遍历链表对比的方式来完成的。如果感兴趣的话，你可以自己来实现看看，这里我就不再多做阐述了。
此外，在实际应用中，我们可能还需要对 多个 key 进行联合查询。比如说，要查询同时包含「极」「客」「时」「间」四个字的诗。这个时候，我们利用多路归并的方法，同时遍历这四个关键词对应的 posting list 即可。实现过程如下图所示。
doc6doc2doc5doc3链表Adoc1word链表Bdoc2doc4worddoc5多路归并p3p1-p2-p3-p4即为公共元素doc7doc2doc1doc5doc4链表CwOrdp4doc8doc2链表Ddocword
image.png
多路归并
重点回顾
好了，今天的内容就先讲到这里。你会发现，倒排索引的核心其实并不复杂，它的具体实现其实是哈希表，只是它不是将文档 ID 或者题目作为 key，而是反过来，通过将内容或者属性作为 key 来存储对应的文档列表，使得我们能在 O(1) 的时间代价内完成查询。
尽管原理并不复杂，但是倒排索引是许多检索引擎的核心。比如说，数据库的全文索引功能、搜索引擎的索引、广告引擎和推荐引擎，都使用了倒排索引技术来实现检索功能。因此，这一讲的内容我也希望你能好好理解消化，打好扎实的基础。
课堂讨论
今天的内容实践性比较强，你可以结合下面这道课堂讨论题，动手试一试，加深理解。
对于一个检索系统而言，除了根据关键字查询文档，还可能有其他的查询需求。比如说，我们希望查询李白都写了哪些诗。也就是说，如何在「根据内容查询」的基础上，同时支持「根据作者查询」，我们该怎么做呢？
将作者作为新的索引创建，作者作为 key，文档作为 value
拓展阅读
问：中敏感词检测适合用倒排索引吗？每个邮件都只要检测一次，不用直接搜索可能又找不到近义词
答：邮件只需要检测一次，因此对邮件做倒排索引并不适用。而且倒排索引也解决不了近义词问题。
邮件敏感词检测一般是这样的思路：
1
准备一个敏感词字典。
2
遍历邮件，提取关键词，去敏感词字典中查找，找到了就说明邮件有敏感词。
这里的核心问题是 如何提取关键词 和 如何在敏感词字典中查询。
一种方式是用哈希表存敏感词字典，然后用分词工具从邮件中提取关键字，然后去字典中查。
另一种方式是 trie 树来实现敏感词字典，然后逐字扫描邮件，用当前字符在 trie 树中查找。
不过，这两种方式都无法解决近义词，或者各种刻意替换字符的场景。要想解决这种问题，要么提供近义词字典，要么得使用大量数据进行训练和学习，用机器学习进行打分，将可疑的高分词找出来。
其实这种近义词处理方案，和搜索引擎解决近义词和查询纠错的过程很像。我在搜索引擎那篇里面会介绍。
问：文章中提到了在构建倒排索引过程中要记录位置信息，我想可不可以同时检索 「李」字和 「白」 字，然后判断二者的位置是否相邻？
答：这关注到了「李白」的分词问题了！对于如何确定一个词，常见的做法是使用分词技术，将「李白」作为一个整体处理。这样检索性能也最好。而这个方案，是在 分词技术无效的情况下，搜索引擎会采用的方案，它会根据位置信息进行短语查询，查出来的「李」和「白」是有序相邻的，优先级最高，位置越远的，优先级越低。通过描述，你也能体会到这样的效率的确没有直接处理一个整体高。因此，分词也是很重要的技术。
问：倒排索引数据量大的话，内存放不下怎么办?
回：有三个思路：
1
通过压缩，全塞进内存；
2
放磁盘上，用 b+ 树或分层跳表处理；
3
分布式，分片后全放内存
