稀疏位图算法RoaringBitmap 稀疏图是指零元素非常少的矩阵

复杂的问题应拆解为可求解的子问题(按问题的不同规模)，这样最终问题得到解决。不同数据量最优解不同

稀疏位图存储占用空间大，需采用稀疏位图压缩算法，减少内存占用并提高效率。

比较有代表性的有WAH、EWAH、Concise，以及RoaringBitmap。

前三种算法都是基于行程长度编码（Run-length encoding, RLE）做压缩的，而RoaringBitmap算是它们的改进版。

位图常用运算：交，并，补，存储要考虑高效运算

RoaringBitmap的核心思想是，对于32位(这里指的是bit)的位图， 将32位无符号整数按照高16位分桶，即最多可能有2^16=65536个桶，称为container。存储数据时，按照数据的高16位找到container（找不到就会新建一个），再将低16位放入container中。也就是说，一个RoaringBitmap就是很多container的集合。

RoaringBitmap有三种策略实现container：

1.ArrayContainer

当桶内数据的基数小于等于4096时，会采用它来存储，其本质上是一个unsigned short类型的有序数组。

数组初始长度为4，随着数据的增多会自动扩容（但最大长度就是4096）。另外还维护有一个计数器，用来实时记录基数。

2.BitmapContainer

当桶内数据的基数大于4096时，会采用位图来存储。BitmapContainer用长度固定为1024的unsigned long型数组表示，亦即位图的大小固定为216位（8KB）。它同样有一个计数器。

3.RunContainer

RunContainer存储使用行程长度编码（RLE）压缩后的数据，是一个可变长度的unsigned short数组。举个例子，连续的整数序列11, 12, 13, 14, 15, 12800, 12801, 12802 会被RLE压缩为两个二元组11, 4, 12800, 2，表示11后面紧跟着4个连续递增的值，27后面跟着2个连续递增的值。

RunContainer的压缩效果与数据分布连续性有关。考虑极端情况：如果所有数据都是连续的，那么最终只需要4字节；如果所有数据都不连续（比如全是奇数或全是偶数），那么不仅不会压缩，还会膨胀成原来的两倍大。RoaringBitmap引入RunContainer是作为ArrayContainer和BitmapContainer的折衷方案。

ClickHouse的存储方法：

使用RoaringBitmap数据结构存储位图对象，当基数小于或等于32时，使用Set保存。当基数大于32时，使用RoaringBitmap保存。这也是为什么低基数集的存储更快的原因。

孜孜不倦，每日一学