RoaringDocIdSet的设计灵感来源于RoaringBitmap,Lucene根据自身需求有着自己的的实现方法,来实现对文档号的处理(存储,读取)。
位集合(bitsets)通常也被成为位图(bitMaps),它是一种常用的快速数据结构(fast data structures),但由于它对内存的开销较大,所以我们通常会使用经过压缩处理的bitMaps,而这便是RoaringBitmap。
本篇文章不会对RoaringBitmap展开介绍,因为Lucene有着自己的实现方法,感兴趣的同学可以看这两个链接:http://roaringbitmap.org、https://github.com/RoaringBitmap/RoaringBitmap。
图1:
点击查看大图
图2:
RoaringDocIdSet只允许处理按照文档号从小到大递增的文档号集合,每当处理一个新的文档号,称之为docId,会判断与上一个处理的文档号lastDocId的大小,如果小于等于lastDocId,说明文档号集合不满足要求,抛出如下的异常:
xxxxxxxxxx
if (docId <= lastDocId) {
throw new IllegalArgumentException("Doc ids must be added in-order, got " + docId + " which is <= lastDocID=" + lastDocId);
}
图3:
我们从最小的文档号开始,逐个处理文档号集合中的文档号,当处理完所有的文档号,那么就完成了图1所示的流程。
图4:
block是什么:
规则是什么:
xxxxxxxxxx
docId >>> 16
图5:
图6:
我们以图5中的文档号集合为例,当处理到文档号65536时,该文档号会被划分到第二个block中,那么此时我们就需要处理第一个block,此时第一个block成为图4中的lastBlock,同时第二个block成为currentBlock。
图7:
上文中我们说到使用block来存储文档号,并且一个block中最多存储65536个文档号,但是并没有给出block的数据结构,原因是block的数据结构取决于block中包含的文档号数量。
block一共有两种数据结构:
short类型数组向FixedBitSet的转化(重要):
图8:
根据block中包含的文档号的数量来判断稠密度:
不同稠密度的文档号集合如何存储:
例如我们以下的文档号集合:
图9:
图10描述了将图9中的文档号划分到不同的block,其中第一个block中包含了0~65533共65534个文档号:
图10:
图11描述了进行了稠密度计算后,将处理后的block添加到block数组中,第一个block包含了65534个文档号,故认为是稠密的,由于一个block最多只能存储65536个,那么计算出那些未存储的文档号,即65534跟65535两个文档号,然后存储它们两个,而第二个block跟第三个block都只包含了2个文档号,所以认为是稀疏的,直接存储即可:
图11:
RoaringDocIdSet提供了两种方法来读取文档号:
xxxxxxxxxx
docId >>> 16
个人觉得直接看源码应该比看我写的文章能更快的了解RoaringDocIdSet😁,所以点击这个链接看下吧:https://github.com/LuXugang/Lucene-7.5.0/blob/master/solr-7.5.0/lucene/core/src/java/org/apache/lucene/util/RoaringDocIdSet.java。
点击下载附件