Roaring Bitmap更好的位图压缩算法
1. 概述
Bitsets（也称为Bitmaps）通常用作快速数据结构。不幸的是，他们可能会占用太多内存。为了降低内存的使用，我们经常会使用压缩的位图。
Roaring Bitmaps 是一种压缩的位图，要优于常规的压缩位图，例如 WAH，EWAH 或者 Concise。在某些情况下，可以比它们快几百倍，并且通常提供更好的压缩。
Roaring Bitmaps 已经被很多重要系统使用：
几乎所有流行的编程语言（Java，C，C ++，Go，C＃，Rust，Python ……）都提供了 Roaring Bitmaps。
2. 主要思想
我们以存放 Integer 值的 Bitmap 来举例，RBM 把一个 32 位的 Integer 划分为高 16 位和低 16 位，通过高 16 位找到该数据存储在哪个桶中（高 16 位可以划分 2^16 个桶），把剩余的低 16 位放入该桶对应的 Container 中。
每个桶都有对应的 Container，不同的 Container 存储方式不同。依据不同的场景，主要有 2 种不同的 Container，分别是 Array Container 和 Bitmap Container。Array Container 存放稀疏的数据，Bitmap Container 存放稠密的数据。若一个 Container 里面的元素数量小于 4096，使用 Array Container 来存储。当 Array Container 超过最大容量 4096 时，会转换为 Bitmap Container。
3. Array Container
Array Container 是 Roaring Bitmap 初始化默认的 Container。Array Container 适合存放稀疏的数据，其内部数据结构是一个有序的 Short 数组。数组初始容量为 4，数组最大容量为 4096，所以 Array Container 是动态变化的，当容量不够时，需要扩容，并且当超过最大容量 4096 时，就会转换为 Bitmap Container。由于数组是有序的，存储和查询时都可以通过二分查找快速定位其在数组中的位置。
后面会讲解为什么超过最大容量 4096 时变更 Container 类型。
下面我们具体看一下数据如何被存储的，例如，0x00020032（十进制131122）放入一个 RBM 的过程如下图所示：
0x00020032 的前 16 位是 0002，找到对应的桶 0x0002。在桶对应的 Container 中存储低 16 位，因为 Container 元素个数不足 4096，因此是一个 Array Container。低 16 位为 0032（十进制为50）, 在 Array Container 中二分查找找到相应的位置插入即可（如上图50的位置）。
相较于原始的 Bitmap 需要占用 16K (131122/8/1024) 内存来存储这个数，而这种存储实际只占用了4B（桶中占 2 B，Container中占 2 B，不考虑数组的初始容量）。
4. Bitmap Container
第二种 Container 是 Bitmap Container。它的数据结构是一个 Long 数组，数组容量恒定为 1024，和上文的 Array Container 不同，Array Container 是一个动态扩容的数组。Bitmap Container 不用像 Array Container 那样需要二分查找定位位置，而是可以直接通过下标直接寻址。
由于每个 Bitmap Container 需要处理低 16 位数据，也就是需要使用 Bitmap 来存储需要 8192 B（2^16/8）, 而一个 Long 值占 8 个 B，所以数组大小为 1024。因此一个 Bitmap Container 固定占用内存 8 KB。
下面我们具体看一下数据如何被存储的，例如，0xFFFF3ACB（十进制4294916811）放入一个 RBM 的过程如下图所示：
0xFFFF3ACB 的前 16 位是 FFFF，找到对应的桶 0xFFFF。在桶对应的 Container 中存储低 16 位，因为 Container 中元素个数已经超过 4096，因此是一个 Bitmap Container。低 16 位为 3ACB（十进制为15051）, 因此在 Bitmap Container 中通过下标直接寻址找到相应的位置，将其置为 1 即可（如上图15051的位置）。
可以看到元素个数达到 4096 之前，Array Container 占用的空间比 Bitmap Container 的少，当 Array Container 中元素到 4096 个时，正好等于 Bitmap Container 所占用的 8 KB。当元素个数超过了 4096 时，Array Container 所占用的空间还是继续线性增长，而 Bitmap Container 的内存空间并不会增长，始终还是占用 8 KB，与数据量无关。所以当 Array Container 超过最大容量 4096 会转换为 Bitmap Container。