你好，我是陈东。欢迎来到检索专栏的第二次加餐时间。
在上一篇加餐中，我们讲了工业界中，倒排索引是怎么利用基础的数据结构来加速“求交集”过程的。现在，相信你已经对跳表、哈希表和位图的实际使用，有了更深刻的理解和认识了。然而，在日常的检索中，我们往往会面临更复杂的联合查询需求。这个时候，又该如何加速呢？
我们先来看一个例子：在一个系统的倒排索引中，有4个不同的key，分别记录着“北京”“上海”“安卓”“学生”，这些标签分别对应着4种人群列表。如果想分析用户的特点，我们需要根据不同的标签来选择不同的人群。这个时候，我们可能会有以下的联合查询方式：
- 在“北京”或在“上海”，并且使用“安卓”的用户集合。抽象成联合查询表达式就是，（“北京”∪“上海”）∩“安卓”；
- 在“北京”使用“安卓”，并且是“学生”的用户集合。抽象成联合查询表达式就是，“北京”∩“安卓”∩“学生”。
这只是2个比较有代表性的联合查询方式，实际上，联合查询的组合表达可以更长、更复杂。对于联合查询，在工业界中有许多加速检索的研究和方法，比如，调整次序法、快速多路归并法、预先组合法和缓存法。今天，我们就来聊一聊这四种加速方法。
方法一：调整次序法
首先，我们来看调整次序法。那什么是调整次序法呢？接下来，我们就以三个集合的联合查询为例，来一起分析一下。这里我再多说一句，虽然这次讲的是三个集合，但是对于多个集合，我们也是采用同样的处理方法。
假设，这里有A、B、C三个集合，集合中的元素个数分别为2、20、40，而且A包含在B内，B包含在C内。这里我先补充一点，如果两个集合分别有m个元素和n个元素，那使用普通的遍历归并合并它们的时间代价为O(m+n)。接着，如果我们要对A、B、C求交集，这个时候，会有几种不同的求交集次序，比如，A∩（B∩C）、（A∩B）∩C等。那我们该如何选择求交集的次序呢？下面，我们就以这两种求交集次序为例来分析一下，不同的求交集次序对检索效率的影响。
当求交集次序是A∩（B∩C）时，我们要先对B和C求交集，时间代价就是20+40 = 60，得到的结果集是B，然后B再和A求交集，时间代价是2 + 20 = 22。因此，最终一共的时间代价就是60 + 22 = 82。
那当求交集次序是（A∩B）∩C时，我们要先对A和B求交集，时间代价是2 + 20 = 22，得到的结果集是A，然后A再和C求交集，时间代价是2 + 40 = 42。因此，最终的时间代价就是22 + 42 = 64。这比之前的代价要小得多。
除了对A、B、C这三个集合同时取交集以外，还有一种常见的联合查询方式，就是对其中两个集合取并集之后，再和第三个集合取交集，比如A ∩（B∪C），你可以看我开头举的第一个例子。在这种情况下，如果我们不做任何优化，查询代价是怎么样的呢？让我们一起来看一下。
首先是执行B∪C的操作，时间代价是20 + 40 = 60，结果是C。然后再和A求交集，时间代价是2+40 = 42。一共是102。
这样的时间代价非常大，那针对这个查询过程我们还可以怎么优化呢？这种情况下，我们可以尝试使用数学公式，对先求并集再求交集的次序进行改造，我们先来复习一个集合分配律公式：
A∩（B∪C）=（A∩B）∪（A∩C）
然后，我们就可以把先求并集再求交集的操作，转为先求交集再求并集的操作了。那这个时候，查询的时间代价是多少呢？我们一起来看一下。
首先，我们要执行A∩B操作，时间代价是2+20 = 22，结果是A。然后，我们执行A∩C操作，时间代价是2+40=42，结果也是A。最后，我们对两个A求并集，时间代价是2+2=4。因此，最终总的时间代价是22 + 42 + 4 = 68。这比没有优化前的102要低得多。
这里有一点需要特别注意，如果求并集的元素很多，比如说（B∪C∪D∪E∪F），那我们用分配律改写的时候，A就需要分别和B到F求5次交集，再将5个结果求并集。这样一来，操作的次数会多很多，性能就有可能下降。因此，我们需要先检查B到F每个集合的大小，比如说，如果集合中元素个数都明显大于A，我们预测它们分别和A求交集能有提速的效果，那我们就可以使用集合分配律公式来加速检索。
不知道你有没有注意到，在一开始讲这两个例子的时候，我们假设了A、Ｂ、Ｃ有相互包含的关系，这是为了方便你更好地理解调整操作次序带来的效率差异。那在真实情况中，集合中的关系不会这么理想，但是我们分析得到的结论，依然是有效的。
方法二：快速多路归并法
但是，调整次序法有一个前提，就是集合的大小要有一定的差异，这样的调整效果才会更明显。那如果我们要对多个posting list求交集，但是它们的长度差异并不大，这又该如何优化呢？这个时候，我们可以使用跳表法来优化。
在对多个posting list求交集的过程中，我们可以利用跳表的性质，快速跳过多个元素，加快多路归并的效率。这种方法，我叫它"快速多路归并法"。在一些搜索引擎和广告引擎中，包括在Elastic Search这类框架里，就都使用了这样的技术。那具体是怎么做的呢？我们一起来看一下。
其实，快速多路归并法的思路和实现都非常简单，就是将n个链表的当前元素看作一个有序循环数组list[n]。并且，对有序循环数组从小到大依次处理，当有序循环数组中的最小值等于最大值，也就是所有元素都相等时，就说明我们找到了公共元素。
这么说可能比较抽象，下面，我们就以4个链表A、B、C、D求交集为例，来讲一讲具体的实现步骤。
第1步，将4个链表的当前第一个元素取出，让它们按照由小到大的顺序进行排序。然后，将链表也按照由小到大有序排列；
第2步，用一个变量max记录当前4个链表头中最大的一个元素的值；
第3步，从第一个链表开始，判断当前位置的值是否和max相等。如果等于max，则说明此时所有链表的当前元素都相等，该元素为公共元素，那我们就将该元素取出，然后回到第一步；如果当前位置的值小于max，则用跳表法快速调整到该链表中第一个大于等于max的元素位置；如果新位置元素的值大于max，则更新max的值。
第4步，对下一个链表重复第3步，就这样依次处理每个链表（处理完第四个链表后循环回到第一个链表，用循环数组实现），直到链表全部遍历完。
为了帮助你加深理解，我在下面的过程图中加了一个具体的例子，你可以对照前面的文字描述一起消化吸收。
上图的例子中，我们通过以上4个步骤，找到了公共元素6。接下来，你可以试着继续用这个方法，去找下一个公共元素11。这里，我就不再继续举例了。
方法三：预先组合法
接下来，我们来说一说第三种方法，预先组合法。其实预先组合法的核心原理，和我们熟悉的一个系统实现理念一样，就是能提前计算好的，就不要临时计算。换一句话说，对于常见的联合查询，我们可以提前将结果算好，并将该联合查询定义一个key。那具体该怎么操作呢？
假设，key1、key2和key3分别的查询结果是A、B、C三个集合。如果我们经常会计算A∩B∩C，那我们就可以将key1+key2+key3这个查询定义为一个新的组合key，然后对应的posting list就是提前计算好的结果。之后，当我们要计算A∩B∩C时，直接去查询这个组合key，取出对应的posting list就可以了。
方法四：缓存法加速联合查询
预先组合的方法非常实用，但是在搜索引擎以及一些具有热搜功能的平台中，经常会出现一些最新的查询组合。这些查询组合请求量也很大，但是由于之前没有出现过，因此我们无法使用预先组合的方案来优化。这个时候，我们会使用缓存技术来优化。
那什么是缓存技术呢？缓存技术就是指将之前的联合查询结果保存下来。这样再出现同样的查询时，我们就不需要重复计算了，而是直接取出之前缓存的结果即可。这里，我们可以借助预先组合法的优化思路，为每一个联合查询定义一个新的key，将结果作为这个key的posting list保存下来。
但是，我们还要考虑一个问题：内存空间是有限的，不可能无限缓存所有出现过的查询组合。因此，对于缓存，我们需要进行内容替换管理。一种常用的缓存管理技术是LRU（Least Recently Used），也叫作最近最少使用替换机制。所谓最近最少使用替换机制，就是如果一个对象长期未被访问，那当缓存满时，它将会被替换。
对于最近最少使用替换机制，一个合适的实现方案是使用双向链表：当一个元素被访问时，将它提到链表头。这个简单的机制能起到的效果是：如果一个元素经常被访问，它就会经常被往前提；如果一个元素长时间未被访问，它渐渐就会被排到链表尾。这样一来，当缓存满时，我们直接删除链表尾的元素即可。
不过，我们希望能快速查询缓存，那链表的访问速度就不满足我们的需求了。因此，我们可以使用O(1)查询代价的哈希表来优化。我们向链表中插入元素时，同时向哈希表中插入该元素的key，然后这个key对应的value则是链表中这个节点的地址。这样，我们在查询这个key的时候，就可以通过查询哈希表，快速找到链表中的对应节点了。因此，使用“双向链表+哈希表”是一种常见的实现LRU机制的方案。
通过使用LRU缓存机制，我们就可以将临时的查询组合缓存起来，快速查询出结果，而不需要重复计算了。一旦这个查询组合不是热点了，那它就会被LRU机制替换出缓存区，让位给新的热点查询组合。
缓存法在许多高并发的查询场景中，会起到相当大的作用。比如说在搜索引擎中，对于一些特定时段的热门查询，缓存命中率能达到60%以上甚至更高，会大大加速系统的检索效率。
重点回顾
好了，今天的内容就讲到这里。今天我们学习了联合查询的4种优化方法，我们一起来回顾一下。
第1种方法是调整次序法，它是通过从小到大求交集，以及使用集合分配律改写查询，使得检索效率得到提升。
第2种方法是快速多路归并法，它是利用跳表快速跳过多个元素的能力，结合优化的多路归并方案，提升多个posting list归并性能的。
第3种方法是预先组合法，也就是将热门的查询组合提前处理好，作为一个单独的key，保存提前计算好的posting list。
第4种则是使用缓存法，将临时的热点查询组合进行结果缓存处理，避免重复查询每次都要重复计算。
你会看到，这4种方法分别从数学、算法、线下工程和线上工程，这四种不同的方向对联合查询进行了优化。同时使用它们，能让我们从多个维度对联合查询进行加速。
通过上一篇加餐，我相信你也体会到了，如果我们能合理组合和灵活应用简单的数据结构和算法，就能构建出复杂的架构，让它们在工业界的大规模系统中发挥重要的作用。那通过这一篇加餐，你还可以体会到，基础知识的全面性能帮助你从不同的维度去思考，教你用更多的手段去优化系统。
因此，在学习的金字塔中，扎实和稳健的基础知识永远是最重要。多花点时间，打好基础，我相信你一定会有巨大的收获！
课堂讨论
最后，我们还是来看一道讨论题。
对于今天介绍的四种方案，你觉得哪一种给你的印象最深刻？你会尝试在怎么样的场景中使用它？为什么？
欢迎在留言区畅所欲言，说出你的思考过程和答案。如果有收获，也欢迎把这篇文章分享给你的朋友。
精选留言
2020-04-06 17:12:18
或许我哪里思考的不全面，需要向您请教~~~
2020-04-06 10:09:06
2. 快速多路归并法： 多路归并可谓是数据库解决数据排序，尤其是不能内排的条件下的一大基础利器，当然像大数据组件里的mr，spark等等，做shuffle时，同样要考虑多个排序数组如何归并的问题。
3.预先组合： 最熟悉的代表就是kylin了， 经典的cube预计算理论，
4. 缓存法：这个就太多了，核心还是局部性原理，所以必须清楚自己的业务场景是否是有那种比较热点的查询，如果每种查询概率都一样，那缓存法也是浪费，所以mysql在某个版本之后把sql到结果的缓存给关闭了。
2020-06-20 20:30:13
后两种方法：预先组合、缓存法实际上就跟我们设计系统时redis作为缓存一个道理，防止打穿来提高效率。
但是后两种方法在用的时候应该还要注意实时更新问题，比如搜索引擎中，更新了数据，如果使用缓存那么只能召回已经“计算”好的数据，即使是热点。就搜索引擎的应用，缓存的key应该还要保存一个时间进行重召回替换，比如1分钟这样。一般搜索引擎应该使用双buffer机制来更新。
2020-04-18 20:57:33
老师的图解非常重要，让难以理解的算法变的简单明了。
阅读本专栏全程“轻松愉快”，原来是因为能读懂。很多令人望而生畏的算法，都让图解化解了！
专栏可以有一个别名：检索算法图解。让更多基础不好，又想学习的同学轻松学习。
另外分享一个LRU算法的练习，更好的理解实现原理：https://leetcode-cn.com/problems/lru-cache/
2020-04-06 18:38:51
1.调整次序法
调整次序法是有前提的，就是集合大小要有诧异且调整后优于调整前，所以依赖预判机制
2.快速多路归并法
多路归并法充分利用跳表加快速度，老师说在 ES 中采用了这个方法，在下面我要看看加深理解
3.预先组合法
预先组合法适合用在数据报表分析的场景上，比如我们部门的报表系统就原始数据存放在 hive 上，然后通过 druid 和 kylin 对一些常用的组合做提前预聚合，这样可以加快查询速度。但我们在使用的时候，druid 和 kylin 对组合数和对应的数据也会有限制的，不能滥用，毕竟会浪费内存
4.缓存加速联合查询
缓存和预先组合法挺像，都是提前把数据准备好。但是它俩又有不同，预先组合的数据一般是稳定的，而缓存的数据是热点数据，如果非热点数据放到缓存中，会白白浪费内存，所以存储空间是需要考虑的。再者就是缓存命中率的问题，可以引入 LRU 缓存替换机制，把常用的缓存放到前面能够快速访问。通过双向链表 + 哈希表实现
2020-04-13 16:00:26
LinkedHashMap 的 accessOrder = true ，它表示遍历的时候按 访问的顺序输出。
我现在 linkedHashMap map; // accessOrder = true
map put(1，1); // a
map put(2，2); // b
map put(3，3); // c
A处： 此时若遍历，打印的顺序是 1 2 3
map. get(2); // d
B处：此时若遍历，打印的顺序是 1 3 2
我知道accessOrder = true时，每访问过一个元素，都要改变它的位置链到双链表的末尾去。
我的问题是：
既然accessOrder = true
那它的遍历打印，不应该是最后（最后是时间上的顺序，那也就是最近）访问过的元素先被打印出来吗？
即B处的遍历打印应该是 2 3 1 才对啊 ？
还是应该理解成：
在B处：1的唯一一次访问是在注释为a的地方访问的； 3的唯一一次访问是在注释为c的地方访问的；2的第一次访问是 在注释为 b的地方访问的，最后一次访问是在注释为 d的地方访问的，访问被更新，因此加到末尾； 由此推出 ==>
1的访问时间最早 1先输出
3的访问时间早于最后一次2的访问时间， 所以接着3输出
2的访问时间由于是最后一次访问更新了访问时间，所以放到链表末尾，表示最后一个访问的。
因此，遍历输出应该是==> 1, 3, 2 而不是 2 开头。
即，访问时间遍历（accessOrder = true）的意思是，最早访问过的先被遍历，最晚访问过的元素，最后被遍历，是这个意思吗？ 我没评论之前还没想明白，评论完了，好像终于想清楚了。还是想找老师确认一下。
恳请老师回答，谢谢老师！
2023-05-22 10:21:05
假设一个容量为3的缓存cache = []，此时添加缓存A，cache = [A]；添加缓存B，cache = [B, A]；添加缓存C，cache = [C, B, A];
访问缓存A后，cache变为[A, C, B]；若此时再要加入缓存D，则因为缓存容量只有3，因此需要淘汰掉最久没被使用的缓存B才可以，因此cache变为
[D, A, C]；从中可以发现缓存的实现有最本质的三个特点，一是各个缓存之间是有顺序的，比如D在A之前，A在C之前（A相比C在最近的时间内被使用过）；
二是要能快速的判断出一个缓存是否在缓存中，比如A是否在cache中；三是从缓存中删除一个元素的操作也要是便捷的（O(1)），所以结合这三点来看，
单单的数组与Dict都是无法满足最优条件的。拿数组来说，其能够满足顺序这个特性，但判断一个缓存元素是否在其中，需要遍历整个数组，
且当删除一个缓存元素时，还伴有数组内元素移动的操作，因此整个的性能开销很大；再来看Dict，Dict能够满足O(1)的缓存元素的快速判断，
且删除元素的操作也为O(1)，但Dict中的元素没有顺序，比如因为缓存容量满了需要淘汰最久没有被使用的元素（按顺序来看，处于最末尾的元素），
此时在Dict中是没有办法识别处于末尾的元素的。所以最好的方式是对基本的数据结构进行组合使用，依然是三个特点：有序，O(1)查找，O(1)删除；
Dict + 数组：数组用于实际存储缓存元素，Dict用于快速判断缓存是否存在，但是数组的淘汰删除策略不是最优的，因此不能满足条件；
Dict + 双向链表：双向链表用于实际存储缓存元素，Dict依然是用于快速判断缓存元素是否存在，双向链表本身有序，且删除一个特定节点操作的时间
复杂度是O(1)，因此LRUCache最终的实现方式是采用Dict + 双向链表
字典dict+双向链表实现
1. dict存储真正的被封装成双向链表节点的key、value对，即key -> Node(key, value)
2. 双向链表和上述使用到的数组一样，用于记录元素的位置
2023-04-07 20:56:11
2020-12-25 22:55:13