RoaringBitmap 的实现原理
RoaringBitmap 的核心思想是将整数集合划分为 块（chunk），并根据每块的稀疏程度选择不同的存储格式。

1. 分块（Chunking）
   整个整数集合按固定大小（通常是
   2
   16
   2
   16
   即 65536）划分为多个块。
   每个块存储一个 16 位的整数范围（即 0 到 65535）。
   块的索引由整数的高位决定，例如：
   整数 123456 属于第 1 块（索引为
   123456
   ÷
   65536
   =
   1
   123456÷65536=1）。
   低位部分
   123456
   m
   o
   d
    
    
   65536
   =
   57920
   123456mod65536=57920 存储在块内。
2. 三种存储方式
   根据每个块中整数的密度，RoaringBitmap 动态选择以下三种存储方式：

Array Container：

用于存储稀疏数据。
将块内的整数用一个有序数组存储。
适用于块内整数少于 4096 个的情况。
Bitmap Container：

用于存储较密集数据。
用一个固定大小的位图（bitmap）存储块内的整数。
适用于块内整数超过 4096 个的情况。
Run-length Encoding Container：

用于存储连续整数范围。
用一个运行长度编码（RLE）的方式压缩存储。
RoaringBitmap 的操作效率

1. 查询
   确定整数在哪个块，然后快速查找块内存储结构。
   时间复杂度接近
   O(1)。
2. 集合操作
   RoaringBitmap 针对分块的设计使得集合操作（如并集、交集）可以逐块并行处理。
   复杂度通常是线性
   O(n)（与块的数量相关），性能远超传统位图。
3. 遍历
   遍历所有整数时，只需按块逐一访问数据，避免无效空间的开销。
   RoaringBitmap 的优势
   节省空间：

在稀疏场景下比普通位图节省大量内存。
在密集场景下依然接近普通位图的性能。
高性能：

对整数集合的操作非常快（如并集、交集、差集等）。
跨平台支持：

RoaringBitmap 有多种语言实现，包括 C++、Java、Python、Rust 等。
灵活性强：

动态选择存储格式，适应不同密度的整数集合。
RoaringBitmap 的应用场景
大规模稀疏数据的索引：

用于倒排索引，存储文档中包含特定关键词的 ID 集合。
高效范围查询：

快速确定某个范围内的整数分布，适用于基因组学或图分析中的范围检索。
实时分析：

实时统计和集合操作，如用户行为日志的快速处理。
压缩存储：

高效压缩和存储整数集合，特别是稀疏集合。

use roaring::RoaringBitmap;

fn main() {
    let mut rb = RoaringBitmap::new();
    
    // 插入整数
    rb.insert(1);
    rb.insert(100);
    rb.insert(1000);
    
    // 查询整数是否存在
    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);
}