Optimizing Druid with Roaring bitmaps

这篇主要是说,如何利用compressed bitmap来提升查询性能

虽然之前有很多bitmap的压缩方案,但是,新提出的Roaring bitmap会更加高效

参考,Better bitmap performance with Roaring bitmaps

BitMap,为了有效和compact的表示integer

只能表示integer,因为下标只能是integer

为何是compact?

int是32bit,而32bit的bitmap是可以表示32个int的

很简单,bitmap有个问题,如果需要表示的integer很稀疏的时候,会有很多空间浪费

比如,我只需要表示7和37,那我需要一个64bit的bitmap,把第7,37bit设置为1

这样就没有compact,和直接用integer空间占用是一样的

所以自然的想法就是要根据integer的稀疏程度来选择是否使用bitmap

并且这个全局太粗了,所以要分段,不同的分段用不同的策略,

这个就是Roaring Bitmap的思路,

对于integer,32bit,分为high-16,和low-16

high-16用于分段,形成2的16次方的bucket

low-16如何存储,就取决于bucket中要存储的数据数量,

如果大于4096,就用bitmap,称为bitmapContainer

小于4096,就直接存value,称为arrayContainer

为何是4096,因为直接存储4096个16bit的value的空间,等同于一个2的16次方的bitmap的大小?所以小于4096,不然直接存value

当然这里根据low-16的情况,可以用其他的各种container来进行更为有效的compact

感觉论文剩下的部分比较水

原文地址:https://www.cnblogs.com/fxjwind/p/12787264.html