Roaring Bitmap 详解

最后修改:2024年1月8日

by baeldung

1. 概述

本教程将深入探讨 Roaring Bitmap 数据结构。我们将通过集合的基本操作示例来演示 Roaring Bitmap 的使用，并对比 Java 中 RoaringBitmap 与 BitSet 的性能表现。

2. Roaring Bitmap 简介

Roaring Bitmap 因其高性能和高压缩比，在数据分析、搜索引擎和大数据项目中广泛应用。其核心思想源于位图索引（bitmap indexes），这是一种高效表示数字数组的数据结构。可以将其视为压缩版的 Java *BitSet*。

Roaring Bitmap 的核心优势在于：既能高效压缩大整数集合，又能快速访问单个元素。其内部通过多种容器类型实现这一目标。

3. Roaring Bitmap 工作原理

Roaring Bitmap 是由多个不相交子集容器组成的无符号整数集合。每个子集通过 16 位键索引，可存储 2^16 范围内的值。这种设计允许将 32 位无符号整数存储为 Java short 类型，因为最坏情况下仅需 16 位即可表示单个 32 位值。容器大小的选择确保了即使最坏情况下，容器仍能适配现代 CPU 的 L1 缓存。

下图展示了 Roaring Bitmap 的结构：

RoaringBitMap 结构示意图

整数的 16 个最高有效位作为桶（bucket）或块（chunk）键。每个数据块表示区间 (0 ≤ n < 2^16) 的值范围基础。若值范围内无数据，则不会创建对应块。

下图是包含不同数据的 Roaring Bitmap 示例：

含数据的 RoaringBitmap 结构

  • 第一块存储前 10 个 2 的倍数
  • 第二块存储从 65536 开始的 100 个连续整数
  • 第三块存储 131072 到 19660 之间的偶数

4. Roaring Bitmap 的容器类型

Roaring Bitmap 主要包含三种容器：数组容器、位图容器和行程容器。根据分区集合的特性，系统自动选择最优容器类型存储分区数据。

当向 Roaring Bitmap 添加数据时，内部会根据值是否在容器键覆盖范围内，决定创建新容器或修改现有容器。

4.1. 数组容器

数组容器不压缩数据，仅存储少量元素。其空间占用与数据量成正比：每个元素占 2 字节。

数组容器使用 short 数据类型，整数按升序存储。

初始容量为 4，最大元素数为 4096。数组容量动态变化，但当元素数超过 4096 时，Roaring Bitmap 会自动将其转换为位图容器。

以插入数字 131090 为例：

  • 16 个最高有效位：0000 0000 0000 0010（作为键）
  • 16 个最低有效位：0000 0000 0001 0010（十进制值 18）

插入后的结构如下：

RoaringBitmap 中的数组容器

插入后，该键对应的数组容器基数为 5。

4.2. 位图容器

位图容器是位图的经典实现。

Roaring Bitmap 使用 long 数组存储位图数据。与动态扩展的数组容器不同，其数组容量恒定为 1024。位图容器无需查找位置，直接通过索引访问。

以插入数字 32786 为例：

  • 16 个最高有效位：0000 0000 0000 0000
  • 剩余位：1000 0000 0001 0010（十进制值 32786）

该值表示位图容器中需设置的位索引。插入后的结构如下：

RoaringBitmap 中的位图容器

4.3. 行程容器

当位图区域存在大量连续值时，行程长度编码（RLE）是最佳容器选择。它使用 short 数组存储数据。

  • 偶数索引值表示行程起点
  • 奇数索引值表示行程长度
  • 容器基数通过遍历整个行程数组计算

下图展示了连续整数序列的压缩过程：

RLE 容器

压缩后仅存储 4 个值：

  • 11 后跟 4 个连续递增值
  • 27 后跟 2 个连续递增值

⚠️ 压缩效果取决于数据紧凑性：

  • 100 个连续 short 可从 200 字节压缩到 4 字节
  • 100 个分散 short 编码后从 200 字节膨胀到 400 字节

5. RoaringBitmap 的并集操作

在开始代码示例前，需在 pom.xml 中添加 RoaringBitmap 依赖：

<dependency>
    <groupId>org.roaringbitmap</groupId>
    <artifactId>RoaringBitmap</artifactId>
    <version>0.9.38</version>
</dependency>

并集是首个测试操作。首先声明两个 RoaringBitmap 实例 A 和 B：

@Test
void givenTwoRoaringBitmap_whenUsingOr_thenWillGetSetsUnion() {
    RoaringBitmap expected = RoaringBitmap.bitmapOf(1, 2, 3, 4, 5, 6, 7, 8);
    RoaringBitmap A = RoaringBitmap.bitmapOf(1, 2, 3, 4, 5);
    RoaringBitmap B = RoaringBitmap.bitmapOf(4, 5, 6, 7, 8);
    RoaringBitmap union = RoaringBitmap.or(A, B);
    assertEquals(expected, union);
}

代码说明：

  1. 使用 bitmapOf() 静态工厂方法 创建实例
  2. 通过 or() 方法执行并集操作
  3. 底层执行位图逻辑 OR 运算，且线程安全

6. RoaringBitmap 的交集操作

交集是另一个常用操作。RoaringBitmap 中的交集实现同样简单直接：

@Test
void givenTwoRoaringBitmap_whenUsingAnd_thenWillGetSetsIntersection() {
    RoaringBitmap expected = RoaringBitmap.bitmapOf(4, 5);
    RoaringBitmap A = RoaringBitmap.bitmapOfRange(1, 6);
    RoaringBitmap B = RoaringBitmap.bitmapOf(4, 5, 6, 7, 8);
    RoaringBitmap intersection = RoaringBitmap.and(A, B);
    assertEquals(expected, intersection);
}

关键点：

  1. 使用 bitmapOfRange() 创建范围集合
    • 底层调用 add() 方法添加区间数据
    • 接收两个 long 参数：下界（包含）和上界（不包含）
    • 接收两个 int 参数的 add() 方法已废弃
  2. and() 方法执行交集操作
    • 底层执行位图逻辑 AND 运算，线程安全

7. RoaringBitmap 的差集操作

差集（相对补集）操作通过 andNot() 方法实现：

@Test
void givenTwoRoaringBitmap_whenUsingAndNot_thenWillGetSetsDifference() {
    RoaringBitmap expected = RoaringBitmap.bitmapOf(1, 2, 3);
    RoaringBitmap A = new RoaringBitmap();
    A.add(1L, 6L);
    RoaringBitmap B = RoaringBitmap.bitmapOf(4, 5, 6, 7, 8);
    RoaringBitmap difference = RoaringBitmap.andNot(A, B);
    assertEquals(expected, difference);
}

操作说明：

  1. 集合 A 通过空实例 + add() 方法创建
  2. andNot() 计算 A 与 B 的差集*
    • 底层执行位图逻辑 ANDNOT 运算
    • 只要输入位图不变，操作即线程安全

8. RoaringBitmap 的异或操作

异或（XOR）操作类似于对称差集，结果集排除两集合的公共元素：

@Test
void givenTwoRoaringBitmap_whenUsingXOR_thenWillGetSetsSymmetricDifference() {
    RoaringBitmap expected = RoaringBitmap.bitmapOf(1, 2, 3, 6, 7, 8);
    RoaringBitmap A = RoaringBitmap.bitmapOfRange(1, 6);
    RoaringBitmap B = RoaringBitmap.bitmapOfRange(4, 9);
    RoaringBitmap xor = RoaringBitmap.xor(A, B);
    assertEquals(expected, xor);
}

核心特性：

  • xor() 方法执行位图逻辑 XOR 运算
  • 线程安全操作

9. 与 BitSet 的性能对比

使用 JMH 对比 RoaringBitmap 和 Java BitSet 的性能。首先添加依赖：

<dependency>
    <groupId>org.openjdk.jmh</groupId>
    <artifactId>jmh-generator-annprocess</artifactId>
    <version>1.37</version>
</dependency>
<dependency>
    <groupId>org.openjdk.jmh</groupId>
    <artifactId>jmh-core</artifactId>
    <version>1.37</version>
</dependency>

9.1. 基准测试范围声明

@State(Scope.Thread)
class BitSetsBenchmark {
    private RoaringBitmap rb1;
    private BitSet bs1;
    private RoaringBitmap rb2;
    private BitSet bs2;
    private final static int SIZE = 10_000_000;
}

关键配置：

  • 声明两种类型的集合各两个
  • 设置最大集合大小 SIZE = 10_000_000
  • 使用 Scope.Thread 和默认吞吐量模式
  • 为避免修改输入数据，每次操作生成新集合
  • BitSet 测试中通过克隆保护输入数据

9.2. 基准测试数据初始化

@Setup
public void setup() {
    rb1 = new RoaringBitmap();
    bs1 = new BitSet(SIZE);
    rb2 = new RoaringBitmap();
    bs2 = new BitSet(SIZE);
    for (int i = 0; i < SIZE / 2; i++) {
        rb1.add(i);
        bs1.set(i);
    }
    for (int i = SIZE / 2; i < SIZE; i++) {
        rb2.add(i);
        bs2.set(i);
    }
}

数据分布：

  • 集合 1（rb1/bs1）：包含 0 到 SIZE/2-1 的值
  • 集合 2（rb2/bs2）：包含 SIZE/2 到 SIZE-1 的值

9.3. 基准测试用例

并集操作

@Benchmark
public RoaringBitmap roaringBitmapUnion() {
    return RoaringBitmap.or(rb1, rb2);
}

@Benchmark
public BitSet bitSetUnion() {
    BitSet result = (BitSet) bs1.clone();
    result.or(bs2);
    return result;
}

交集操作

@Benchmark
public RoaringBitmap roaringBitmapIntersection() {
    return RoaringBitmap.and(rb1, rb2);
}

@Benchmark
public BitSet bitSetIntersection() {
    BitSet result = (BitSet) bs1.clone();
    result.and(bs2);
    return result;
}

差集操作

@Benchmark
public RoaringBitmap roaringBitmapDifference() {
    return RoaringBitmap.andNot(rb1, rb2);
}

@Benchmark
public BitSet bitSetDifference() {
    BitSet result = (BitSet) bs1.clone();
    result.andNot(bs2);
    return result;
}

异或操作

@Benchmark
public RoaringBitmap roaringBitmapXOR() {
    return RoaringBitmap.xor(rb1, rb2);
}

@Benchmark
public BitSet bitSetXOR() {
    BitSet result = (BitSet) bs1.clone();
    result.xor(bs2);
    return result;
}

9.4. 基准测试结果

Benchmark                                    Mode  Cnt       Score       Error  Units
BitSetsBenchmark.bitSetDifference           thrpt   25    3890.694 ±   313.808  ops/s
BitSetsBenchmark.bitSetIntersection         thrpt   25    3542.387 ±   296.007  ops/s
BitSetsBenchmark.bitSetUnion                thrpt   25    3012.666 ±   503.821  ops/s
BitSetsBenchmark.bitSetXOR                  thrpt   25    2872.402 ±   348.099  ops/s
BitSetsBenchmark.roaringBitmapDifference    thrpt   25   12930.064 ±   527.289  ops/s
BitSetsBenchmark.roaringBitmapIntersection  thrpt   25  824167.502 ± 30176.431  ops/s
BitSetsBenchmark.roaringBitmapUnion         thrpt   25    6287.477 ±   250.657  ops/s
BitSetsBenchmark.roaringBitmapXOR           thrpt   25    6060.993 ±   607.562  ops/s

结果分析：

  • ✅ RoaringBitmap 在所有操作中均优于 BitSet
  • ⚠️ 但需注意适用场景：
    • 小数据集时使用压缩位图可能浪费资源
    • 当解压 BitSet 不会增加内存占用时，压缩位图可能不适用
    • 若无需压缩，BitSet 提供更极致的速度

10. 总结

本文深入研究了 Roaring Bitmap 数据结构，演示了 RoaringBitmap 的核心操作，并通过性能测试验证了其相对 BitSet 的优势。测试结果表明，在多数场景下 RoaringBitmap 性能显著优于传统 BitSet。

完整示例代码可在 GitHub 获取。

原始标题:Introduction to Roaring Bitmap

« 上一篇： Hibernate实体中的数据库关键词作为列
» 下一篇： 在Java中查找List中的所有重复元素