RoaringBitmap 的實現(xiàn)原理
RoaringBitmap 的核心思想是將整數(shù)集合劃分為 塊（chunk），并根據(jù)每塊的稀疏程度選擇不同的存儲格式。
- 分塊（Chunking）
整個整數(shù)集合按固定大小（通常是
2
16
2
16
即 65536）劃分為多個塊譬嚣。
每個塊存儲一個 16 位的整數(shù)范圍（即 0 到 65535）正勒。
塊的索引由整數(shù)的高位決定腺兴，例如：
整數(shù) 123456 屬于第 1 塊（索引為
123456
÷
65536
=
1
123456÷65536=1）。
低位部分
123456
m
o
d
?
?
65536
=
57920
123456mod65536=57920 存儲在塊內(nèi)牌废。 - 三種存儲方式
根據(jù)每個塊中整數(shù)的密度咽白，RoaringBitmap 動態(tài)選擇以下三種存儲方式：
Array Container：
用于存儲稀疏數(shù)據(jù)。
將塊內(nèi)的整數(shù)用一個有序數(shù)組存儲鸟缕。
適用于塊內(nèi)整數(shù)少于 4096 個的情況晶框。
Bitmap Container：
用于存儲較密集數(shù)據(jù)。
用一個固定大小的位圖（bitmap）存儲塊內(nèi)的整數(shù)懂从。
適用于塊內(nèi)整數(shù)超過 4096 個的情況授段。
Run-length Encoding Container：
用于存儲連續(xù)整數(shù)范圍。
用一個運行長度編碼（RLE）的方式壓縮存儲番甩。
RoaringBitmap 的操作效率
- 查詢
確定整數(shù)在哪個塊侵贵，然后快速查找塊內(nèi)存儲結(jié)構(gòu)。
時間復(fù)雜度接近
O(1)缘薛。 - 集合操作
RoaringBitmap 針對分塊的設(shè)計使得集合操作（如并集窍育、交集）可以逐塊并行處理。
復(fù)雜度通常是線性
O(n)（與塊的數(shù)量相關(guān)）宴胧，性能遠超傳統(tǒng)位圖漱抓。 - 遍歷
遍歷所有整數(shù)時，只需按塊逐一訪問數(shù)據(jù)牺汤，避免無效空間的開銷辽旋。
RoaringBitmap 的優(yōu)勢
節(jié)省空間：
在稀疏場景下比普通位圖節(jié)省大量內(nèi)存。
在密集場景下依然接近普通位圖的性能檐迟。
高性能：
對整數(shù)集合的操作非巢古撸快（如并集、交集追迟、差集等）溶其。
跨平臺支持：
RoaringBitmap 有多種語言實現(xiàn)，包括 C++敦间、Java瓶逃、Python束铭、Rust 等。
靈活性強：
動態(tài)選擇存儲格式厢绝，適應(yīng)不同密度的整數(shù)集合契沫。
RoaringBitmap 的應(yīng)用場景
大規(guī)模稀疏數(shù)據(jù)的索引：
用于倒排索引，存儲文檔中包含特定關(guān)鍵詞的 ID 集合昔汉。
高效范圍查詢：
快速確定某個范圍內(nèi)的整數(shù)分布懈万，適用于基因組學(xué)或圖分析中的范圍檢索。
實時分析：
實時統(tǒng)計和集合操作靶病，如用戶行為日志的快速處理会通。
壓縮存儲：
高效壓縮和存儲整數(shù)集合，特別是稀疏集合娄周。
use roaring::RoaringBitmap;
fn main() {
let mut rb = RoaringBitmap::new();
// 插入整數(shù)
rb.insert(1);
rb.insert(100);
rb.insert(1000);
// 查詢整數(shù)是否存在
assert!(rb.contains(100));
assert!(!rb.contains(50));
// 集合操作
let mut rb2 = RoaringBitmap::new();
rb2.insert(100);
rb2.insert(500);
let union = &rb | &rb2; // 并集
let intersection = &rb & &rb2; // 交集
println!("Union: {:?}", union);
println!("Intersection: {:?}", intersection);
}
