什么是Roaring Bitmap？你知道了嗎？
有朋友提示可以使用Roaring Bitmap，咱們今天就看看什么是Roaring Bitmap。
什么是 Bitmap？
Bitmap是用于存儲整數(shù)集的位數(shù)組。
它們的工作原理是當整數(shù)N位于集合中時設(shè)置第N位，如圖：
什么是 Bitmap？
通過這種方式存儲整數(shù)集，在進行數(shù)據(jù)操作時，可以使用CPU指令中的按位與和按位或指令來計算集合的交集和并集，CPU指令都是極快的。
集合交集和并集運行效率，對于許多搜索和數(shù)據(jù)庫應(yīng)用程序至關(guān)重要。搜索和數(shù)據(jù)庫索引中存在各種操作，歸根結(jié)底就是擁有兩組整數(shù)，需要快速對它們進行交集或并集。
以反向搜索索引為例：
- 您已索引了數(shù)十億個文檔。每個文檔都有一個整數(shù) ID。
- 索引將術(shù)語映射到它們出現(xiàn)的一組文檔。例如，術(shù)語pigeon出現(xiàn)在具有以下 ID 的文檔中：{2, 345, 2034, ...}。
- 跨術(shù)語搜索的查詢使用集合運算。為了解決類似這樣的搜索查詢，carrier AND pigeon您需要包含pigeon的文檔集和包含carrier的文檔集的交集。
- 按位運算可以快速執(zhí)行這些集合運算。如果將文檔 ID 集合表示為Bitmap，則上述查詢就是按位與。
什么是Roaring Bitmap
在https://roaringbitmap.org/中的介紹簡潔明了：
Roaring bitmaps are compressed bitmaps. They can be hundreds of times faster.
Bitmap和Roaring Bitmap都為整數(shù)提供了一組數(shù)據(jù)結(jié)構(gòu)，可以插入整數(shù)、檢查整數(shù)的存在以及獲取兩組整數(shù)的交集和并集。
Roaring Bitmap在補習(xí)生集合操作性能的前提下，比Bitmap具有更好的壓縮效果。
roaringbitmap.org網(wǎng)站列出了一系列OLAP數(shù)據(jù)庫和搜索系統(tǒng)，這些系統(tǒng)內(nèi)部都使用了Roaring Bitmap。這些系統(tǒng)的詳細點是：
- 需要存儲大量整數(shù)
- 盡可能少的內(nèi)存
- 執(zhí)行快速設(shè)置
- ……
從側(cè)面反映了Roaring Bitmap的優(yōu)勢。
Roaring Bitmap 解決了什么問題？
當集合稀疏時，Bitmap的壓縮效果較差。
假設(shè)您有一個空的Bitmap，向其中添加整數(shù)8,000,000。將發(fā)生以下情況：
首先需要分配1,000,000字節(jié)。
然后設(shè)置第8,000,000位。
Bitmap的問題
這有什么不好嗎？
很明顯，集合中只有1個整數(shù)，整數(shù)占用4個字節(jié)，但是Bitmap已經(jīng)分配了1兆，整整多了6個數(shù)量級。
妥妥的空間黑洞。
Roaring Bitmap就是為了解決這個問題的。
Roaring Bitmap 的工作原理
Roaring Bitmap是一組無符號整數(shù)，由不相交子集的容器組成。
每個子集都有一個16位的索引，可以保存大小為2^16范圍內(nèi)的值。
容器大小的選擇還確保在最壞情況下，容器仍然適合現(xiàn)代CPU的L1緩存。
下圖展示了Roaring Bitmap結(jié)構(gòu)：
圖片
我們的整數(shù)的高16位是索引（或者叫做存儲桶或塊鍵）。每個數(shù)據(jù)塊代表間隔內(nèi)值范圍的基數(shù)（0<= n < 2^16）。此外，如果值范圍內(nèi)沒有數(shù)據(jù)，則不會創(chuàng)建塊。
下圖是具有不同數(shù)據(jù)的Roaring Bitmap的示例：
圖片
在第一個塊中，我們存儲了 2 的前 10 個倍數(shù)。此外，在第二個塊中，我們有從 65536 開始的 100 個連續(xù)整數(shù)。圖像中的最后一個塊有 131072 到 19660 之間的偶數(shù)。
Roaring Bitmap 的容器
Roaring Bitmap 中有三種主要類型的容器 - 數(shù)組容器（Array Container）、Bitmap容器（Bitmap Container）和運行容器（Run Container）。
根據(jù)分區(qū)集的特征，數(shù)組容器、Bitmap容器和運行容器是保存分區(qū)數(shù)據(jù)的容器的實現(xiàn)。
當我們將數(shù)據(jù)添加到Roaring Bitmap時，它會在內(nèi)部根據(jù)值是否適合容器鍵所涵蓋的范圍來決定是否創(chuàng)建新容器或更改現(xiàn)有容器。
數(shù)組容器
數(shù)組容器不壓縮數(shù)據(jù)，只能保存少量數(shù)據(jù)，其占用的空間與保存的數(shù)據(jù)量成正比，每個數(shù)據(jù)占兩個字節(jié)。
數(shù)組容器直接采用數(shù)組來存儲低16位數(shù)據(jù)，沒有采用任何數(shù)據(jù)壓縮算法，適合存儲比較稀疏的數(shù)據(jù)，在Java中，使用short數(shù)組來存儲，并且占用的內(nèi)存空間大小和數(shù)據(jù)量成線性關(guān)系。由于short為2字節(jié)，因此n個數(shù)據(jù)為2n字節(jié)。
數(shù)組容器的初始容量為4，最大數(shù)據(jù)量為4096，數(shù)組容量是動態(tài)變化的，但是當元素數(shù)超過4096時，Roaring Bitmap內(nèi)部會將數(shù)組容器轉(zhuǎn)換為Bitmap容器。4096 * 2b = 8kb，Bitmap容器空間也是8kb。
數(shù)組容器采用二分查找定位有序數(shù)組中的元素，因此時間復(fù)雜度為O(logN)。
讓我們看一個在Roaring Bitmap中將數(shù)據(jù)插入數(shù)組容器的示例。
插入數(shù)字131090，高16位是 0000 0000 0000 0010，作為一級索引，低16位是 0000 0000 0001 0010，作為存儲數(shù)據(jù)，低16位轉(zhuǎn)換為十進制基數(shù)時，值為18。
現(xiàn)在，插入數(shù)據(jù)后，這是我們的Roaring Bitmap結(jié)構(gòu)：
圖片
Bitmap容器
Bitmap容器采用BitMap的原理，就是一個沒有經(jīng)過壓縮處理的普通BitMap，適合存儲比較稠密的數(shù)據(jù)，在Java中使用Long數(shù)組存儲低16位數(shù)據(jù)，每一個bit位表示一個數(shù)字。由于每個container需要存儲2^16 = 65536個數(shù)據(jù)，如果通過BitMap進行存儲的話，需要使用2^16個bit進行存儲，即8kb的數(shù)據(jù)空間。
Bitmap采用位運算，時間復(fù)雜度為O(1)。
為了觀察它的工作原理，我們將使用一個簡單的示例。我們將數(shù)字 32786 插入Roaring Bitmap中。高16位是 0000 0000 0000 0000 作為一級索引，低16位是1000 0000 0001 0010，對應(yīng)的數(shù)據(jù)大于4096，需要使用Bitmap容器，對應(yīng)的結(jié)果為：
圖片
運行容器
運行容器采用行程長度編碼（Run-Length Encoding，RLE）進行壓縮，適合存儲大量連續(xù)數(shù)據(jù)。Java中使用short數(shù)組進行存儲。
連續(xù)bit位程度越高的話越節(jié)省存儲空間，最佳場景下（65536個數(shù)據(jù)全為1）只需要存儲4字節(jié)。最差場景為所有數(shù)據(jù)都不連續(xù)，所有存儲數(shù)據(jù)位置為奇數(shù)或者偶數(shù)，這種場景需要存儲128kb。
運行容器采用二分查找算法定位元素，因此時間復(fù)雜度為O(logN)。
偶數(shù)索引處的值表示運行的開始，奇數(shù)索引處的值表示這些運行的長度。容器的基數(shù)是通過遍歷整個運行數(shù)組來計算的。
例如，下圖展示了一個包含連續(xù)整數(shù)序列的容器。然后，在 RLE 執(zhí)行之后，容器只有四個值：
圖片
這些值表示為 11 后跟四個連續(xù)增加的值和 27 后跟兩個連續(xù)增加的值。
這種壓縮算法的工作原理取決于數(shù)據(jù)的緊湊程度或連續(xù)程度。如果我們有100個數(shù)，它們?nèi)寂懦梢恍?，它可以將它們?00字節(jié)壓縮到4字節(jié)，但如果它們?nèi)嘉挥诓煌恢?，則編碼后會從200字節(jié)變?yōu)?00字節(jié)。
文末總結(jié)
今天介紹了Roaring Bitmap，有用的知識又增加了。我們可以不用，但是不能知道。知道了，需要的時候就可以直接用了。
下次我們看下Java中如何使用Roaring Bitmap。
