Bitmap与RoaringBitmap原理详解

一、Bitmap基础原理

Bitmap（位图）是一种高效的数据结构，用于表示一组数字的存在性。其核心思想是：

• 使用一个bit位来标记某个元素对应的存在性（Value）
• 元素的数值（Key）直接对应bit数组中的索引位置

基本操作示例：

• 存储数字2：将bit数组下标为2的位置置为1
• 查询数字2：检查bit数组下标为2的位置是否为1

空间特性：

• Bitmap的空间占用仅与存储的最大数值有关
• 存储数值范围0-N需要N+1个bit位

问题：
当存储稀疏数据时（如仅存储1和1,000,000两个数值），传统Bitmap会浪费大量空间（需要1,000,000 bit）。

二、RoaringBitmap（RBM）原理

RoaringBitmap是一种高效压缩位图，由S. Chambi等人在2016年提出，主要解决传统Bitmap的空间浪费问题。

2.1 核心设计思想

1. 32位整数分割：

   • 将32位整型(int)分为高16位和低16位（两个short）
   • 高16位：使用16位整型有序数组存储
   • 低16位：根据数据特征选择三种不同的container存储

2. 分层存储结构：

   RoaringBitmap
   ├── 高16位分区1 → Container1
   ├── 高16位分区2 → Container2
   └── ...
   

2.2 三种Container类型

1. Array Container

适用场景：存储少量数据（≤4096个元素）

实现特点：

• 底层数据结构：short类型的有序数组
• 始终保持有序，支持二分查找
• 不存储重复数值
• 动态扩容，最大容量4096

空间占用：

• 每个元素占用2字节（short）
• N个元素占用约2N字节
• 最大占用：4096×2=8KB

2. Bitmap Container

适用场景：存储大量数据（>4096个元素）

实现特点：

• 底层数据结构：long[1024]数组
• 每个long表示64位，共1024×64=65536位
• 可表示0-65535的所有数值

空间占用：

• 固定占用8KB（1024×8字节）
• 与存储元素数量无关（存储1个或65536个都占8KB）

3. Run Container

适用场景：存储连续数值序列

实现原理：

• 基于行程长度压缩算法(Run Length Encoding)
• 对连续数字存储起始值和长度
  • 示例1：[11] → [11,0]
  • 示例2：[11,12,13,14,15] → [11,4]
  • 示例3：[11,12,13,14,15,21,22] → [11,4,21,1]

空间特性：

• 最好情况：仅2个short（4字节）
• 最坏情况：65536个short（128KB）

2.3 动态转换机制

RBM会根据数据特征自动调整Container类型：

1. Array → Bitmap：

   • 当ArrayContainer元素超过4096时自动转换
   • 转换后固定占用8KB

2. Bitmap → Array：

   • 当BitmapContainer元素减少到≤4096时自动转换
   • 转换后空间占用与元素数量成正比

2.4 存储示例

以数字131122为例：

1. 转换为十六进制：0x00020032
2. 分割：
   • 高16位：0x0002 → 确定分区
   • 低16位：0x0032（十进制50）
3. 存储：
   • 查找高16位对应的分区
   • 将低16位存入该分区的Container中
   • 由于50 < 4096，使用ArrayContainer存储

三、64位扩展：Roaring64NavigableMap

对于long类型(64位)数据：

1. 分割方式：

   • 高32位：作为索引key
   • 低32位：存储在对应的RoaringBitmap中

2. 内部结构：

   • 使用TreeMap结构
   • 按signed/unsigned排序高32位
   • key：高32位
   • value：对应的RoaringBitmap

四、空间占用对比

4.1 连续数据测试

4.2 稀疏数据测试

存储两个极端值（1和9,999,999）：

五、代码实现示例（Java）

// 连续数据测试
public void testContinuousData() {
    // 10w数据
    RoaringBitmap rb1 = new RoaringBitmap();
    byte[] bits1 = new byte[100000];
    for (int i = 0; i < 100000; i++) {
        rb1.add(i);
        bits1[i] = (byte) i;
    }
    System.out.println("10w数据 RBM大小:" + rb1.getSizeInBytes());
    System.out.println("10w数据 Bitmap大小:" + bits1.length);
    
    // 稀疏数据测试
    RoaringBitmap rb2 = new RoaringBitmap();
    byte[] bits2 = new byte[10000000];
    for (int i = 0; i < 10000000; i++) {
        if (i == 1 || i == 9999999) {
            rb2.add(i);
            bits2[i] = (byte) i;
        }
    }
    System.out.println("稀疏数据 RBM大小:" + rb2.getSizeInBytes());
    System.out.println("稀疏数据 Bitmap大小:" + bits2.length);
}

六、应用场景

1. 人群本地化存储：

   • 存储用户ID的偏移量
   • 高效处理大规模用户群组

2. 大数据分析：

   • 快速集合运算（并集、交集）
   • 用户画像标签计算

3. 数据库索引：

   • 高效压缩倒排索引
   • 加速多条件查询

七、性能优化建议

1. 数据预处理：

   • 对输入数据进行排序，提高连续性
   • 利用Run Container的压缩优势

2. 监控Container类型：

   • 避免频繁的Array/Bitmap转换
   • 对特定场景可手动控制Container类型

3. 批量操作：

   • 优先使用批量添加/删除API
   • 减少多次单独操作的开销