背景

最近在閱讀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);