RoaringBitMap是一種壓縮算法。
聊roaringBitMap之前，需要了解其産生背景。先看下es裡面反向索引的結構，網上有很多圖，拿一個來舉例子。反向索引存儲的是“詞項-文檔ID數組”的對應關系。對于上億數量級的文檔，單個詞項可能會出現上億數量級别的文檔ID數組。簡單的存儲這個數組肯定不合适，是以，高效壓縮、解壓這個數組，是ES搜尋引擎解決的第一個關鍵問題。
筆者在前面介紹過第一種壓縮算法，FOR（Frame Of Reference）算法。
FOR用的是減法
通過記錄初始數值及後續數值間的內插補點，來記錄整體數組資料。整數的數值越小，所需要的存儲二進制位數越少，因而占用比特越少。有序數值之間的內插補點是小于數值本身的，因而FOR算法能比較好的節省存儲空間。
FOR算法在資料比較稠密的時候，節省空間的效果比較好，比如[111,112,113,114,115,116,117,119],壓縮後是[111,1,1,1,1,1,1,2],得到的是比較小的數值。在資料相對稀疏的情況下，數值之間的內插補點仍然是一個比較大的數值，效果就不那麼好了。舉例來說，我有一個數組[100W,200W,300W,500W],用FOR壓縮得到壓縮結果[100W,100W,100W,200W]，得到的依舊是一個百萬級别的數組。這個時候我們引入一種新的算法，也就是RBM算法。
FOR算法使用的是減法的思想，就是前一個數和後一個數做減法。RBM用的是什麼呢？
RBM用的是除法
但是RBM不是直接的相除，它是怎麼操作的呢？
核心思想就在上面的圖中，接下來我們逐漸解讀。
先看下圖幾個數字第一行的二進制表達：
可以看到，這幾個數字，高位16位，也就是靠左的16位是相差不大的；低位16位差異比較大。低位16位表達的範圍是多大呢？也就是2的0次方-1到2的16次方-1，0-65535。那麼我們把高位和低位單獨去存，相同的高位的存一起，等于是把公共的部分共用，這樣就初步節省了空間。這一步也是等效的做了除法，等于原資料/65536。
因而得到圖中第二行。将原資料拆分為高位16位和低位16位，小于65535的，高位都是0。然後将高位低位分别轉為二進制。
1000的高位16位都是0，轉化為十進制表達就是0；低位00000011-11101000轉化為十進制任然是1000；62101是同樣的道理；
對于十進制數131385，高位00000000-00000010轉換為十進制就是2，低位00000001-00111001轉換為十進制就是313。
進而得到下面的表格：
那麼高16位，得到三個數 0,2,3；低16位則各不相同。再把高16位相同的聚成一個數組，我們可以得到一個k-v鍵值對結構，其中值是一個數組，如下表所示。
此時我們已經完成了一輪壓縮，可以看到值數組已經會占用不少空間。接下來探讨值數組的存儲，在ES裡面，有3種container來存儲這個值數組。
ArrayContainer
每個數值16bit，需要2Byte。在數量為N的情況下，存儲空間是線性增長的,N*2byte。
BitmapContainer
怎麼存呢？了解bitmap的可以跳着了，不了解的慢慢看。
上表二進制數為01011000，在正常思維裡面，表達的十進制數為：2的3次方+2的4次方+2的6次方=8+16+64=88，也就是值為1的2的坐标次方之和。
那麼換種思路，01011000，還可以表達數組[3,4,6],不懂位圖的人看到這個就該懂了，就是說坐标為實際需要存儲的值。這個值存在，二進制表達為1；這個值不存在，二進制表達為0；這就是位圖bitmap。
16位數字位圖的大小也是固定的，65536位，需要空間為65536/8=8KB，看起來不小，但是這個空間是固定的。我們很容易得出，ArrayContainer和BitMapContainer在值數組大小為4096的時候，占用空間相等，值數組大小>4096，bitmapContainer占用空間将明顯小于ArrayContainer。
RunContainer
主要用于表達連貫的值數組或大部分連貫，其存儲思路為[begin,end]，也就是說[1,67]，表示[1,2,3,4...65,66,67],用首尾表達連貫的數值。不完全連貫的可以拆分為多段的數組。
以上就是值數組的三個容器，ArrayContainer、BitmapContainer、RunContainer，實際使用的時候需要根據數組的特性以及數量選擇合适的容器。
綜上，RoaringBitmap的思路為：對原數組内數字做除法，已商為key，對餘數進行聚合形成數組K-VArray，最後對數組選擇合适的存儲方式進行存儲。