Lucene对Posting List压缩算法的解读之Roaring bitmaps

前文：关于Lucene采用的FST算法的解读、Lucene对Posting List压缩算法的解读之FOR

了解Roaring bitmaps，应该先了解bitmap，了解bitmap，可以看看桶排序算法，有相通之处。

举例，我们有8个doc ID，1,2,3,4,5,6,7,8。如果按照正常的int存储，就是4*8=32字节。

如图，有1个字节8位数字0。

第一位代表doc ID 1,0代表没有doc ID1，1代表有doc ID1。以此类推。

如果doc ID1~8都有，则这个8位数字全部为1，也就是1个字节就存储了原来32个字节的信息。

这是理想情况，假设我们只有两个doc ID：1和1024——数字很稀疏，如果按照正常int存储，也就是4*2=8字节，如果按照位图，我们就需要一个1024位=128字节的空间去存储，这就很不好了，本来用位图来压缩空间的，这么搞反而增加了空间。

为了解决这个问题，Lucene引入了Roaring bitmaps。

简单的说，就是将posting list里面的doc ID进行分块。

ID在0~65535之内，就放在第0块；ID在65536~131071之内，就放在第1块。以此类推。

举例：

拿到这些数字的高16位，右移16位，所代表的数字就是其应该所在block的位置。

65535在第0块，65536在第1块，131072在第2块。

而这些数字的低16位，则代表在block之内的位置。

注意，在block内，如果要存储的值超过了4096个，我们认为这是一个密集块，使用位图进行存储。否则，我们认为这是一个稀疏块，直接用short数组进行存储。

为什么是4096？

4096个short数值（16位），就是4096*16=65536位=8192字节。

很容易得出结论，当个数大于4096时，所需空间就大于8192字节，线性增加。

而如果使用位图，还记得之前我们说过的，每个block最多放65536个数，那么最多也就需要65536位来表示数值的有无。空间恒定为8192字节。

综上所述，我们可以解读下图：

以131385为例

第一步：131385/65536=2——CPU会优化为右移16位。

第二步：131385%65536=313。

第三步：将313存入第2个block中。

注意，本例中每个block存入的数值少于4096，所以就直接用short[]存了。

我们可以算一下原数据是6个int数值，6*4=24字节。

压缩后，6个short数值，6*2=12字节。