05 倒排索引：如何从海量数据中查询同时带有“极”和“客”的唐诗？
你好，我是陈东。
试想这样一个场景：假设你已经熟读唐诗300首了。这个时候，如果我给你一首诗的题目，你可以马上背出这首诗的内容吗？相信你一定可以的。但是如果我问你，有哪些诗中同时包含了“极”字和“客”字？你就不见得能立刻回答出来了。你需要在头脑中一首诗一首诗地回忆，并判断每一首诗的内容是否同时包含了“极”字和“客”字。很显然，第二个问题的难度比第一个问题大得多。
那从程序设计的角度来看，这两个问题对应的检索过程又有什么不同呢？今天，我们就一起来聊一聊，两个非常常见又非常重要的检索技术：正排索引和倒排索引。
什么是倒排索引？
我们先来看比较简单的那个问题：给出一首诗的题目，马上背出内容。这其实就是一个典型的键值查询场景。针对这个场景，我们可以给每首诗一个唯一的编号作为ID，然后使用哈希表将诗的ID作为键（Key），把诗的内容作为键对应的值（Value）。这样，我们就能在O(1)的时间代价内，完成对指定key的检索。这样一个以对象的唯一ID为key的哈希索引结构，叫作正排索引（Forward Index）。
哈希表存储所有诗
一般来说，我们会遍历哈希表，遍历的时间代价是O(n)。在遍历过程中，对于遇到的每一个元素也就是每一首诗，我们需要遍历这首诗中的每一个字符，才能判断是否包含“极”字和“客”字。假设每首诗的平均长度是k，那遍历一首诗的时间代价就是O(k)。从这个分析中我们可以发现，这个检索过程全部都是遍历，因此时间代价非常高。对此，有什么优化方法吗？
我们先来分析一下这两个场景。我们会发现，“根据题目查找内容”和“根据关键字查找题目”，这两个问题其实是完全相反的。既然完全相反，那我们能否“反着”建立一个哈希表来帮助我们查找呢？也就是说，如果我们以关键字作为key建立哈希表，是不是问题就解决了呢？接下来，我们就试着操作一下。
我们将每个关键字当作key，将包含了这个关键字的诗的列表当作存储的内容。这样，我们就建立了一个哈希表，根据关键字来查询这个哈希表，在O(1)的时间内，我们就能得到包含该关键字的文档列表。这种根据具体内容或属性反过来索引文档标题的结构，我们就叫它倒排索引（Inverted Index）。在倒排索引中，key的集合叫作字典（Dictionary），一个key后面对应的记录集合叫作记录列表（Posting List）。
倒排索引
如何创建倒排索索引？
前面我们介绍了倒排索引的概念，那创建一个倒排索引的过程究竟是怎样的呢？我把这个过程总结成了以下步骤。
- 给每个文档编号，作为其唯一的标识，并且排好序，然后开始遍历文档（为什么要先排序，然后再遍历文档呢？你可以先想一下，后面我们会解释）。
- 解析当前文档中的每个关键字，生成<关键字，文档ID，关键字位置>这样的数据对。为什么要记录关键字位置这个信息呢？因为在许多检索场景中，都需要显示关键字前后的内容，比如，在组合查询时，我们要判断多个关键字之间是否足够近。所以我们需要记录位置信息，以方便提取相应关键字的位置。
- 将关键字作为key插入哈希表。如果哈希表中已经有这个key了，我们就在对应的posting list后面追加节点，记录该文档ID（关键字的位置信息如果需要，也可以一并记录在节点中）；如果哈希表中还没有这个key，我们就直接插入该key，并创建posting list和对应节点。
- 重复第2步和第3步，处理完所有文档，完成倒排索引的创建。
将一个文档解析并加入倒排索引
如何查询同时含有“极”字和“客”字两个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移动到链表尾为止。
为了帮助你理解，我把一个链表归并的完整例子画在了一张图中，你可以结合这张图进一步理解上面的3个步骤。
链表归并提取公共元素例子
那对于两个key的联合查询来说，除了有“同时存在”这样的场景以外，其实还有很多联合查询的实际例子。比如说，我们可以查询包含“极”或“客”字的诗，也可以查询包含“极”且不包含“客”的诗。这些场景分别对应着集合合并中的交集、并集和差集问题。它们的具体实现方法和“同时存在”的实现方法差不多，也是通过遍历链表对比的方式来完成的。如果感兴趣的话，你可以自己来实现看看，这里我就不再多做阐述了。
此外，在实际应用中，我们可能还需要对多个key进行联合查询。比如说，要查询同时包含“极”“客”“时”“间”四个字的诗。这个时候，我们利用多路归并的方法，同时遍历这四个关键词对应的posting list即可。实现过程如下图所示。
多路归并
重点回顾
好了，今天的内容就先讲到这里。你会发现，倒排索引的核心其实并不复杂，它的具体实现其实是哈希表，只是它不是将文档ID或者题目作为key，而是反过来，通过将内容或者属性作为key来存储对应的文档列表，使得我们能在O(1)的时间代价内完成查询。
尽管原理并不复杂，但是倒排索引是许多检索引擎的核心。比如说，数据库的全文索引功能、搜索引擎的索引、广告引擎和推荐引擎，都使用了倒排索引技术来实现检索功能。因此，这一讲的内容我也希望你能好好理解消化，打好扎实的基础。
课堂讨论
今天的内容实践性比较强，你可以结合下面这道课堂讨论题，动手试一试，加深理解。
对于一个检索系统而言，除了根据关键字查询文档，还可能有其他的查询需求。比如说，我们希望查询李白都写了哪些诗。也就是说，如何在“根据内容查询”的基础上，同时支持“根据作者查询”，我们该怎么做呢？
欢迎在留言区畅所欲言，说出你的思考过程和最终答案。如果有收获，也欢迎把这篇文章分享给你的朋友。
- 无形 👍（37） 💬（4）
根据作者查询可以给每首诗打一个作者的标签，再把标签作为关键字，标签对应的文档集合即为这位诗人写的诗的集合，如这种格式 key=array "作者_李白"=["将进酒"，"凤求凰"，"静夜思"] 这里加的前缀"作者_"可以避免有的诗里面有"李白"这两个字，造成检索结果不准确，实际中key可能把key映射成ID，集合里保存的也是诗的ID，这是一种主动打标签的方式，如果还需要按照朝代查询，再打朝代的标签 对于检索效率的问题，当数据量很大的时候，显然不可能用链表，查询效率太低了，位图相比查询效率就非常高了，每个byte就能表示一个诗的ID，1表示有，0表示没有，因此非常省内存，而且位运算取交集、差集效率非常高，不过普通位图有一个缺点，如果数据稀疏的话比较浪费空间，因此有人研究出了压缩位图，压缩位图的主要思想是把一个int划分为高16位低16位，高16位对应int存储的容器，把低6位放到对应的容器中，容器有三种，有序集合、位图、还有一种忘了名字，会随着数据量的变化选择合适的容器来存储数据，比较节省内存，倒排索引+压缩位图是一个非常强的组合，搜索性能非常高，合适的场景下甚至可以替换ES，提升几十倍搜索性能。快手、华为千亿级用户标签检索系统中也有类似的应用
2020-04-01 - 明翼 👍（10） 💬（3）
老师对于邮件中敏感词检测适不适合用倒排索引那，用的话可能每个邮件都只要检测一次，不用直接搜索可能又找不到近义词
2020-04-01 - 阿斯蒂芬 👍（9） 💬（2）
想起了之前看《改变未来的九大算法》（书名比较夸张，但书是好书啊各位），开篇讲到了搜索引擎的「把戏」，就是从单词分词构建单词到网页的链接集合，来实现最「粗糙」的互联网检索冲浪。随后再考虑同时检索到多个满足条件的结果时，如何确定哪一个才更接近我们所需要的。于是在单纯记录单词出现的网页的基础上，加上了单词在这个网页的位置，理论上可以简单认为位置越近，就越符合我们检索条件的输入。 以上两个知识点其实跟老师讲的倒排索引思路类似。思考题的李白，其实也算是一种：假设作者和内容都命中，我们如何能区分哪个才是更接近我们想要的答案。解决这类问题的思路也是相似的，像单词增多一个在网页出现的位置记录一样，也可以考虑让“李白”多增加一个信息，来让计算机知道它是「出现在什么位置」的，当然这里的位置可能就变成了：内容、作者这样的标签或者类型。 人类想借助计算机快算处理结构化数据的特点，将人类知识从小条目到全文的检索关系结构化存储到计算机，实现了「正向索引」，但是贪婪的人类并不满足，调皮大脑还有一个特性就是，全文记不住，全文的这一小段那一小段倒是可能记得溜，所以人类又聪明地让计算机以类似的存储结构但是不同的关系方向来实现全文内容到全文方向的查找，于是出来了「倒排索引」。这个角度来看，说检索技术真是是被人类特征的需求来驱动进展的不为过。
2020-04-17 - yang 👍（9） 💬（1）
加餐是6号出的，倒排是1号出的，所以我先把1号的补完哈～ 你可以再思考一些细节:如果有一些诗的内容里也有“李白”这个关键词，比如杜甫的诗。 那么作者“李白”对应的posting list，和内容中的“李白”对应的posting list是否会冲突？可以怎么处理？ key_李白 = posting list; 内容中的关键字作为倒排索引 author_李白 = posting list; 作者的名字作为倒排索引 为避免 关键字 或 名字 或 朝代 相同时，查询出错，通过给索引加 前缀 或 后缀的形式 来区分内容相同类型不同的索引。 老师说的给posting list分域有点想不明白？ 看到老师提到进阶会有：压缩位图、磁盘存储、分布式存储。期待老师的进阶篇文章！ ps: 终于补到6号的了，马上可以去享受加餐课了！ (✪▽✪)
2020-04-10 - fengyi 👍（8） 💬（1）
有个问题想请教。如果要搜寻‘极客’这个单词的话。有方法可以重复利用‘极’和‘客’的索引吗。还是要对‘极客’单独作索引
2020-04-12 - 大头爸爸 👍（7） 💬（1）
是不是倒排索引主要应用在搜索引擎这一块？跟数据库SQL/NOSQL关系不大？ 另外，还有一个概念是列式存储，那个是不是主要用在NOSQL，跟搜索引擎关系不大?
2020-06-14 - Bachue Zhou 👍（5） 💬（1）
“那么问题来了，我们该如何在 A 和 B 这两个链表中查找出公共元素呢？如果 A 和 B 都是无序链表，那我们只能将 A 链表和 B 链表中的每个元素分别比对一次，这个时间代价是 O(m*n)。”不需要这么麻烦，对A建立Hash表，对B搜索Hash表即可，时间代价是O（m+n）
2020-12-18 - 李恒达 👍（5） 💬（1）
老师，我有个疑问，为了实现根据关键词获取数据的功能，是不是需要在正常的表存储的基础上，再额外维护这样一个倒排索引？那这种在关键词不明确的情况下是不是就不会有这个东西了？
2020-04-01 - 范闲 👍（4） 💬（5）
拉链的是倒排索引在数据量不大的情况下应该很好？如果数量上去了，要改成跳表了吧？如果跳表也支撑不下去了呢？
2020-04-01 - 时隐时现 👍（3） 💬（1）
每个留言问的到位，作者回复的也耐心，支持
2020-05-05 - 奕 👍（3） 💬（1）
倒排索引的核心就是关键词的提取，也就是如何合理的对内容进行分词
2020-04-01 - 与你一起学算法 👍（3） 💬（1）
老师在文章中提到了在构建倒排索引过程中要记录位置信息，我想可不可以同时检索 李 字和 白 字，然后判断二者的位置是否相邻？希望老师解答。
2020-04-01 - 峰 👍（3） 💬（4）
感觉老师这个问题有点水到渠成的感觉，既然讲了倒排，一个很明显的答案就是把作者也当检索内容一样处理构建索引，对这种类似kv m 查的问题，这应该是最优的一个手段，具体的方案应该考虑如何压缩表示的问题，不明显的答案想不到哈哈哈。 既然提到索引给大家分享一个观点，索引是什么，从机器学习的角度上看，它其实是检索信息(比如这边的关键字，作者等等)到数据本身位置信息的一个映射关系，pos ＝f(x)。这就转变成一个机器学习怎么输入x 预测pos 的问题了！(观点来自jeaf dean组的一篇论文) 最后老师的口音真牛逼！！！哈哈哈😂
2020-04-01 - 西西弗与卡夫卡 👍（3） 💬（1）
在关键字为key所在文档为posting list的基础上，再加以作者名为key，posting list为作者诗集的索引
2020-04-01 - Chaos 👍（2） 💬（1）
在A和B两个链表中查找公共元素，也可以看作判断A中的元素在B中是否存在。那么是不是可以使用上一讲中讲到的布隆过滤器，这样就不需要链表是有序的了。
2020-04-02