召回系统介绍
一、以Lucene为例介绍召回系统
1、倒排检索
Lucene的倒排索引由 Term Index -> TermDictionary -> Posting List 三层组成，倒排检索实际上就是通过分词Term查询到倒排拉链，然后对所有拉链进行合并。
Term-> Posting List，可以直接通过B+树来完成（对Term创建索引，叶子结点存储拉链的磁盘位置+长度），但是数据量较大时Term索引无法完整放在内存里，因此Lucene加了一个TermIndex，FST有限状态机转换器（类似Trie树），为了进一步压缩空间，Trie树里不存储所有Term，只包含Term的一些前缀，Term的后缀存放在磁盘上，通过TermIndex快速定位到后缀block在磁盘上的位置，遍历找到匹配的Term，进而得到PostingList在磁盘上的位置。
TermIndex相当于对term进行了前缀压缩，公共前缀只存储一份，而使用map存储term -> List映射，相当于每个term都要存储一份，内存无法放下全部term。
相比于倒排检索，Mysql 只有 term dictionary 这一层，是以 b-tree 排序的方式存储在磁盘上的，检索一个 term 需要若干次的 random access 的磁盘操作，速度非常慢。
对于联合查询（拉链合并），Lucene提供了两种方法：
- 使用跳表结构，合并时同时遍历两条拉链，互相skip，时间复杂度O(m+n);
- 使用位图结构，对两条拉链分别计算位图，然后对位图进行AND，OR操作；
如果查询的Term在内存中有bitset的缓存，就用bitset合并，否则使用跳表。
因为bitset要表示Doc全集所以一条拉链的bitset是比较稀疏的，因此使用Roaring Bitmap压缩存储。
为了防止一条拉链的跳表全加载进来内存放不开，会将DocId差值编码，使用最大值所占空间存储每个值，然后每128个DocId压缩成一个PackBlock作为跳表的一个节点（使用packblock首元素表示节点值），合并时公共的PackBlock先从磁盘上读取并解压缩，再计算公共DocId。
ElasticSearch官网上有这两种方式的性能对比：因为 PackBlock 编码非常高效，对于简单的相等条件的过滤缓存成纯内存的 bitset 还不如需要访问磁盘的 skip list 的方式要快。
2、正排检索
需要对某个正排属性进行聚合，或者希望返回结果按照某个正排属性进行排序。先检索出所有DocId在分别读取正排信息进行排序效率较低，还非常占内存，Lucene使用了DocValue，一个基于docid的列式存储。当我们拿到一系列的docid后，进行排序就可以使用这个列式存储，结合一个堆排序进行。