背景

最近在阅读Starrocks源码的时候，遇到ColumnRefSet的RoaringBitmap使用，所以借此来讨论一下RoaringBitmap这个数据结构,这种思想是很值得借鉴的。
对于的实现可以参考一下

<dependency><groupId>org.roaringbitmap</groupId><artifactId>RoaringBitmap</artifactId><version>1.3.0</version>
</dependency>

的实现

杂谈

RoaringBitmap是高效压缩位图，简称RBM，我们可以通过Github RoaringBitmap了解它的全貌。

实现思路

• 将 32bit int（无符号的）类型数据 划分为 2^16 个桶，即2^16=65536个桶，每个桶内用container来存放一个数值的低16位
• 在存储和查询数值时，将数值划分为高16位和低16位，取高 16 位值找到对应的桶，然后在将低 16 位值存放在相应的 Container 中（存储时如果找不到就会新建一个）

举个例子：
以十进制数字131122为例，现在我们要将该数字放入到RBM中。第一步，先将该数字转换为16进制，131122对应的十六进制为0x00020032；其中，高十六位对应0x0002，首先我们找到0x0002所在的桶，再将131122的低16位存入到对应的container中，131122的低16位转换为10进制就是50，没有超过ArrayContainer的容量4096，所以将低16位直接放入到对应的ArrayContainer中。

如果要插入的数字低16位超过了4096，RBM会将ArrayContainer转换为BitMapContainer。

具体的操作

摘抄自Github官网，如下

import org.roaringbitmap.RoaringBitmap;public class Basic {public static void main(String[] args) {RoaringBitmap rr = RoaringBitmap.bitmapOf(1,2,3,1000);RoaringBitmap rr2 = new RoaringBitmap();rr2.add(4000L,4255L);rr.select(3); // would return the third value or 1000rr.rank(2); // would return the rank of 2, which is index 1rr.contains(1000); // will return truerr.contains(7); // will return falseRoaringBitmap rror = RoaringBitmap.or(rr, rr2);// new bitmaprr.or(rr2); //in-place computationboolean equals = rror.equals(rr);// trueif(!equals) throw new RuntimeException("bug");// number of values stored?long cardinality = rr.getLongCardinality();System.out.println(cardinality);// a "forEach" is faster than this loop, but a loop is possible:for(int i : rr) {System.out.println(i);}}
}

container的类型

小桶的实现目前有三种:ArrayContainer,BitmapContainer,RunContainer。默认采用 ArrayContainer 。

• ArrayContainer
  这个是 RoaringBitmap 默认小桶的实现，在初始化的时候，会初始化长度为4的ArrayContainer，
  其内部实现是用 Char数组实现的

  public ArrayContainer(int capacity) {this.cardinality = 0;this.content = new char[capacity];
  }
  

  其中每个Char占用两个字节。
  从Add方法来看：

  @Override
  public Container add(final char x) {if (cardinality == 0 || (cardinality > 0&& (x) > (content[cardinality - 1]))) {if (cardinality >= DEFAULT_MAX_SIZE) {return toBitmapContainer().add(x);}if (cardinality >= this.content.length) {increaseCapacity();}content[cardinality++] = x;} else {int loc = Util.unsignedBinarySearch(content, 0, cardinality, x);if (loc < 0) {// Transform the ArrayContainer to a BitmapContainer// when cardinality = DEFAULT_MAX_SIZE // DEFAULT_MAX_SIZE值为4096if (cardinality >= DEFAULT_MAX_SIZE) {return toBitmapContainer().add(x);}if (cardinality >= this.content.length) {increaseCapacity();}// insertion : shift the elements > x by one position to// the right// and put x in it's appropriate placeSystem.arraycopy(content, -loc - 1, content, -loc, cardinality + loc + 1);content[-loc - 1] = x;++cardinality;}}return this;
  }
  

  • ArrayContainer内部的数据是排序的
  • 容量超过4096(这个是代码写死的)后，会转换为BitmapContainer
  • ArrayContainer占用的内存空间为 4096*2B ,即 8KB

• BitmapContainer
  这个就是一个位图,这里的位图的长度为 2^16 ，也就是占用 2^16 bit，所有占用存储为8KB

• RunContainer
  这是一种利用步长来压缩空间的方法，
  比如连续的整数序列 11, 12, 13, 14, 15, 27, 28, 29 会被 压缩为两个二元组 11, 4, 27, 2 表示：11后面紧跟着4个连续递增的值，27后面跟着2个连续递增的值，那么原先16个字节的空间，现在只需要8个字节，这种用的比较少

可以看到 ArrayContainer 占用的内存的最大空间为 8KB，和BitMapContainer占用的空间内存一样，但是ArrayContainer存储的数据最大为4096，超过这个以后，内存空间的占用就会超过8KB，所以从内存占用考虑的话，ArrayContainer适合存储稀疏数据，适合存储稠密数据，这样策略下，能够最大程度的避免内存浪费

查询的性能

和BitMap相比

• Roaringbitmap本质上是将大块分为了各个小块，并且只有小块有数据的时候才会存在，所以Roaringbitmap在前16位的时候，就可以将部分数据过滤掉，而不像 BitMap一样，所有的位都需要进行计算

其他

除了 32位的RoaringBitmap外，还有64位的Roaring64Bitmap,如下：

    import org.roaringbitmap.longlong.*;// first Roaring64NavigableMapLongBitmapDataProvider r = Roaring64NavigableMap.bitmapOf(1,2,100,1000);r.addLong(1234);System.out.println(r.contains(1)); // trueSystem.out.println(r.contains(3)); // falseLongIterator i = r.getLongIterator();while(i.hasNext()) System.out.println(i.next());// second Roaring64Bitmapbitmap1 = new Roaring64Bitmap();bitmap2 = new Roaring64Bitmap();int k = 1 << 16;long i = Long.MAX_VALUE / 2;long base = i;for (; i < base + 10000; ++i) {bitmap1.add(i * k);bitmap2.add(i * k);}b1.and(bitmap2);