Lucene系列七：番外篇-倒排数组合并

川长思鸟来 2022-04-10 07:39 264阅读 0赞

为何要把这一篇单独起草谈？主要是它很重要，当然了经常玩算法的基本上可以一扫而过。在上一节[Lucene搜索][Lucene]中要实现这样的需求sql（name='alan' and name='alice' limit 0,20 ）该如何处理？

我们知道单个词匹配可以得到这个term的倒排链（docId列表），在数据库中使用二级索引（可能需要建立两张索引表）也是可以满足。lucene的优势在哪呢（更少IO）？问题其实就变成了求**有序**List1<Integer>和List2<integer>**的并集**（整个搜索的时间复杂度取决于词，因为分词和倒排查询时间复杂度都是O(1)），解决方法有：

> **二重for循环法**
> 
> 时间复杂度O(n\*n)，每个搜索词命中的网页是很多的，O(n\*n)的复杂度是明显不能接受的

> **拉链法**，时间复杂度O(n)
> 
> 有序集合1\{1,3,5,7,8,9\}和有序集合2\{2,3,4,5,6,7\}，两个指针指向首元素，比较元素的大小（如果相同，放入结果集，随意移动一个指针，否则，移动值较小的一个指针，直到队尾），
> 
> 优势（集合中的元素最多被比较一次，时间复杂度为O(n)，多个有序集合可以同时进行，这适用于多个分词的item求url\_id交集），这个方法就像一条拉链的两边齿轮，一一比对就像拉链，故称为拉链法

> **水平分桶**，多线程并行
> 
> 有序集合1\{1,3,5,7,8,9, 10,30,50,70,80,90\}和有序集合2\{2,3,4,5,6,7, 20,30,40,50,60,70\}，先进行分桶拆分【桶1的范围为\[1, 9\]、桶2的范围为\[10, 100\]、桶3的范围为\[101, max\_int\]】，于是拆分成集合1【a=\{1,3,5,7,8,9\}、b=\{10,30,50,70,80,90\}、c=\{\}】和集合2【d=\{2,3,4,5,6,7\}、e=\{20,30,40,50,60,70\}、e=\{\}】，利用多线程对桶1（a和d）、桶2（b和e）、桶3（c和e）分别求交集，最后求并集。
> 
> 每个区间利用多线程并行求交集，各个线程结果集的并集，作为最终的结果集，能够大大的减少执行时间

> **bitmap**，大大提高运算并行度，时间复杂度O(n)
> 
> 假设set1\{1,3,5,7,8,9\}和set2\{2,3,4,5,6,7\}的所有元素都在桶值\[1, 16\]的范围之内，可以用16个bit来描述这两个集合，原集合中的元素x，在这个16bitmap中的第x个bit为1，此时两个bitmap求交集，只需要将两个bitmap进行“与”操作，结果集bitmap的3，5，7位是1，表明原集合的交集为\{3,5,7\}
> 
> 水平分桶（每个桶内的数据一定处于一个范围之内），使用bitmap来表示集合，能极大提高求交集的效率，但时间复杂度仍旧是O(n)，但bitmap需要大量连续空间，占用内存较大。
> 
> 从Lucene 5 开始采用了一种改进的位图方式，即roaring bitmaps（官网[http://roaringbitmap.org/][http_roaringbitmap.org]），它是一个压缩性能比bitmap更好的位图实现。

> **跳表**，时间复杂度为O(log(n))
> 
> 集合1\{1,2,3,4,20,21,22,23,50,60,70\}和集合2\{50,70\}求交集，如果用拉链法，会发现1,2,3,4,20,21,22,23都要被无效遍历一次，每个元素都要被比对，时间复杂度为O(n)，能不能每次比对“跳过一些元素”呢？集合1\{1,2,3,4,20,21,22,23,50,60,70\}建立跳表时，一级只有\{1,20,50\}三个元素，二级与普通链表相同，集合2\{50,70\}由于元素较少，只建立了一级普通链表。这样在进行拉链法时，复杂度由O(n)降至O(log(n))

总之，我们在实现一个需求的时候，总是要考虑时间复杂度和空间复杂度，当然有时候二者是冲突的，那我们就需要视情况而定。![85062127][]

[Lucene]: https://blog.csdn.net/alex_xfboy/article/details/83377210
[http_roaringbitmap.org]: http://roaringbitmap.org/
[85062127]: /images/20220402/ec625a45213a4fe09aba79d4e594acef.png