有朋友提示可以使用Roaring Bitmap，咱們今天就看看什么是Roaring Bitmap。

什么是 Bitmap？

Bitmap是用于存儲整數集的位數組。

它們的工作原理是當整數N位于集合中時設置第N位，如圖：

什么是 Bitmap？

通過這種方式存儲整數集，在進行數據操作時，可以使用CPU指令中的按位與和按位或指令來計算集合的交集和并集，CPU指令都是極快的。

集合交集和并集運行效率，對于許多搜索和數據庫應用程序至關重要。搜索和數據庫索引中存在各種操作，歸根結底就是擁有兩組整數，需要快速對它們進行交集或并集。

以反向搜索索引為例：

1. 您已索引了數十億個文檔。每個文檔都有一個整數 ID。
2. 索引將術語映射到它們出現的一組文檔。例如，術語pigeon出現在具有以下 ID 的文檔中：{2, 345, 2034, ...}。
3. 跨術語搜索的查詢使用集合運算。為了解決類似這樣的搜索查詢，carrier AND pigeon您需要包含pigeon的文檔集和包含carrier的文檔集的交集。
4. 按位運算可以快速執行這些集合運算。如果將文檔 ID 集合表示為Bitmap，則上述查詢就是按位與。

什么是Roaring Bitmap

在https://roaringbitmap.org/中的介紹簡潔明了：

Roaring bitmaps are compressed bitmaps. They can be hundreds of times faster.

Bitmap和Roaring Bitmap都為整數提供了一組數據結構，可以插入整數、檢查整數的存在以及獲取兩組整數的交集和并集。

Roaring Bitmap在補習生集合操作性能的前提下，比Bitmap具有更好的壓縮效果。

roaringbitmap.org網站列出了一系列OLAP數據庫和搜索系統，這些系統內部都使用了Roaring Bitmap。這些系統的詳細點是：

• 需要存儲大量整數
• 盡可能少的內存
• 執行快速設置
• ……

從側面反映了Roaring Bitmap的優勢。

Roaring Bitmap 解決了什么問題？

當集合稀疏時，Bitmap的壓縮效果較差。

假設您有一個空的Bitmap，向其中添加整數8,000,000。將發生以下情況：

首先需要分配1,000,000字節。

然后設置第8,000,000位。

Bitmap的問題

這有什么不好嗎？

很明顯，集合中只有1個整數，整數占用4個字節，但是Bitmap已經分配了1兆，整整多了6個數量級。

妥妥的空間黑洞。

Roaring Bitmap就是為了解決這個問題的。

Roaring Bitmap 的工作原理

Roaring Bitmap是一組無符號整數，由不相交子集的容器組成。

每個子集都有一個16位的索引，可以保存大小為2^16范圍內的值。

容器大小的選擇還確保在最壞情況下，容器仍然適合現代CPU的L1緩存。

下圖展示了Roaring Bitmap結構：

圖片

我們的整數的高16位是索引（或者叫做存儲桶或塊鍵）。每個數據塊代表間隔內值范圍的基數（0<= n < 2^16）。此外，如果值范圍內沒有數據，則不會創建塊。

下圖是具有不同數據的Roaring Bitmap的示例：

圖片

在第一個塊中，我們存儲了 2 的前 10 個倍數。此外，在第二個塊中，我們有從 65536 開始的 100 個連續整數。圖像中的最后一個塊有 131072 到 19660 之間的偶數。

Roaring Bitmap 的容器

Roaring Bitmap 中有三種主要類型的容器 - 數組容器（Array Container）、Bitmap容器（Bitmap Container）和運行容器（Run Container）。

根據分區集的特征，數組容器、Bitmap容器和運行容器是保存分區數據的容器的實現。

當我們將數據添加到Roaring Bitmap時，它會在內部根據值是否適合容器鍵所涵蓋的范圍來決定是否創建新容器或更改現有容器。

數組容器

數組容器不壓縮數據，只能保存少量數據，其占用的空間與保存的數據量成正比，每個數據占兩個字節。

數組容器直接采用數組來存儲低16位數據，沒有采用任何數據壓縮算法，適合存儲比較稀疏的數據，在Java中，使用short數組來存儲，并且占用的內存空間大小和數據量成線性關系。由于short為2字節，因此n個數據為2n字節。

數組容器的初始容量為4，最大數據量為4096，數組容量是動態變化的，但是當元素數超過4096時，Roaring Bitmap內部會將數組容器轉換為Bitmap容器。4096 * 2b = 8kb，Bitmap容器空間也是8kb。

數組容器采用二分查找定位有序數組中的元素，因此時間復雜度為O(logN)。

讓我們看一個在Roaring Bitmap中將數據插入數組容器的示例。

插入數字131090，高16位是 0000 0000 0000 0010，作為一級索引，低16位是 0000 0000 0001 0010，作為存儲數據，低16位轉換為十進制基數時，值為18。

現在，插入數據后，這是我們的Roaring Bitmap結構：

圖片

Bitmap容器

Bitmap容器采用BitMap的原理，就是一個沒有經過壓縮處理的普通BitMap，適合存儲比較稠密的數據，在Java中使用Long數組存儲低16位數據，每一個bit位表示一個數字。由于每個container需要存儲2^16 = 65536個數據，如果通過BitMap進行存儲的話，需要使用2^16個bit進行存儲，即8kb的數據空間。

Bitmap采用位運算，時間復雜度為O(1)。

為了觀察它的工作原理，我們將使用一個簡單的示例。我們將數字 32786 插入Roaring Bitmap中。高16位是 0000 0000 0000 0000 作為一級索引，低16位是1000 0000 0001 0010，對應的數據大于4096，需要使用Bitmap容器，對應的結果為：

圖片

運行容器

運行容器采用行程長度編碼（Run-Length Encoding，RLE）進行壓縮，適合存儲大量連續數據。Java中使用short數組進行存儲。

連續bit位程度越高的話越節省存儲空間，最佳場景下（65536個數據全為1）只需要存儲4字節。最差場景為所有數據都不連續，所有存儲數據位置為奇數或者偶數，這種場景需要存儲128kb。

運行容器采用二分查找算法定位元素，因此時間復雜度為O(logN)。

偶數索引處的值表示運行的開始，奇數索引處的值表示這些運行的長度。容器的基數是通過遍歷整個運行數組來計算的。

例如，下圖展示了一個包含連續整數序列的容器。然后，在 RLE 執行之后，容器只有四個值：

圖片

這些值表示為 11 后跟四個連續增加的值和 27 后跟兩個連續增加的值。

這種壓縮算法的工作原理取決于數據的緊湊程度或連續程度。如果我們有100個數，它們全都排成一行，它可以將它們從200字節壓縮到4字節，但如果它們全都位于不同位置，則編碼后會從200字節變為400字節。

文末總結

今天介紹了Roaring Bitmap，有用的知識又增加了。我們可以不用，但是不能知道。知道了，需要的時候就可以直接用了。

下次我們看下Java中如何使用Roaring Bitmap。