---
id: e80ed40ea024585819cc03207d51db23
author: snowmerak
title: 充满活力的位图
description: 从数据库位图索引的基本概念，到 Roaring Bitmap 的工作原理，再到 Go 语言中的应用方法。本文探讨面向大规模数据集高效处理的位图优化技术。
language: zh
date: 2025-09-08T13:30:39.840979719Z
path: /blog/posts/vibrant-bitmap-z1743872f
category: database
---

## 什么是位图?

> 这里的位图是一种索引。如果您是因为图形学而进来的,请直接点击返回即可。

### 基本概念

位图是数据库索引技术的一种形式。它将某一列的值表示为位数组或向量中的一个元素或形式,每个比特表示该列中是否存在某个特定值。因此,最基本的形式是为每一行分配一个比特索引,并用0和1表示是否存在。

例如,假设有一个包含性别列的表。该表中有5行数据,性别列的值如下:

1. 男性
2. 女性
3. 男性
4. 女性
5. 其他

在这种情况下,性别列的位图索引可以表示如下:

- 男性: 10100
- 女性: 01010
- 其他: 00001

### 那么它究竟用在哪里呢

大家可能会认为,它不只是用来表示这些内容的。为了真正地使用位图索引,我们来考虑以下情况。

```SQL
CREATE TABLE IF NOT EXISTS Users (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    active BOOLEAN,
    sex BOOLEAN,
    age INT
);
```

假设该表中有1,000,000行数据。然后执行如下查询。

```SQL
SELECT * FROM Users WHERE active = TRUE AND SEX = TRUE;
```

该查询用于查找active和sex列都为TRUE的行。那么,要最快地找到两列都满足TRUE条件的行,可以利用位与(bit and)运算。

- active列的位图索引已预先建立为`1100110011...`(1,000,000位的比特数组),
- sex列的位图索引已预先建立为`1010101010...`(1,000,000位的比特数组)。

这样,对两个位图索引执行位与运算,就能快速找到两列都为TRUE的行。由于这只是简单的位运算,因此可以比其他索引扫描更快地得到结果。

### 权衡取舍

位图索引虽然可以非常高效,但也存在一些权衡取舍。其缺点有很多,这里只谈其中一点。

即位图索引更适合低基数(即列中可能取值较少的情况)。若对高基数的列使用位图索引,位图可能会变得非常大。

对高基数的列使用位图索引时,由于每个唯一值都需要单独生成一个位图,因此可能需要大量存储空间。例如,如果某列有1,000,000个唯一值,就需要生成1,000,000个位图,这可能会非常低效。

## 因此我们

为解决高基数带来的位图问题,可以使用名为Roaring Bitmap的结构。Roaring Bitmap具有多种特性,但其最核心的设计理念和特征是:`根据数据的密度动态选择最合适的存储方式,从而同时最大化压缩率和运算速度`。

### Roaring Bitmap的基本概念

#### 两级索引

Roaring Bitmap为存储一个整数,首先要经过以下两个步骤。虽然称为两级索引,但您可以把它直接理解为一个二维数组。

- 提取高16位:提取整数的高16位,并将其用作索引。它是一个长度为65536的二维数组中外层数组的索引。该数组保存后文所述容器的地址。
- 提取低16位:提取整数的低16位,并将其用作容器内的位置。

#### 容器

如刚才的比喻所示,容器对应二维数组中的内层数组。但与高16位的那一层不同,容器的内部结构会根据其中存储的数据量而变化。Roaring Bitmap支持以下3种容器。

- Array Container:当容器内存储的数据较少时使用。具体而言,当存储的元素不超过4096个时使用。该容器简单地以有序整数数组实现,可以通过二分查找来定位元素。
- Bitmap Container:当容器内存储的数据较多时使用。具体而言,当存储的元素超过4096个时使用。该容器以65536位(8192字节)的位图实现,每个比特表示对应位置的整数是否存在。
- Run Container:该容器用于存储连续的整数范围。例如,对于1, 2, 3, 4, 5这样的连续整数,存储效率很高。该容器以(起始值, 长度)对的列表实现。如果全部都存在呢?那就意味着从头到尾都存在,因此只需存储(0, 65536)一项即可。

这种方式使Roaring Bitmap能够非常高效地使用内存,并在各种数据密度下提供最优的性能。

### Roaring Bitmap的功能

#### 基本功能

Roaring Bitmap提供以下基本功能。

- 插入:向位图中添加新的整数。在此过程中,可以选择合适的容器,或根据需要转换容器。
- 删除:从位图中移除已有的整数。此过程同样会根据容器的状态进行适当处理。
- 查找:检查特定整数是否存在于位图中。此过程执行速度非常快。

#### 集合运算

Roaring Bitmap还支持以下集合运算。

- 并集(Union):生成包含两个位图所有元素的新位图。
- 交集(Intersection):生成仅包含两个位图中都存在的元素的新位图。
- 对称差集(Symmetric Difference):生成仅包含两个位图中其中一个存在的元素的新位图。

这些运算会根据位图的容器类型进行优化,因此执行速度非常快。

### 在Go语言中

在Go语言中,可以使用`github.com/RoaringBitmap/roaring`包轻松地使用Roaring Bitmap。该包提供了Roaring Bitmap的全部功能,并针对Go语言的特性进行了优化。

#### 安装

```bash
go get github.com/RoaringBitmap/roaring/v2
```

#### 使用示例

```go
package main

import (
	"log"

	"github.com/RoaringBitmap/roaring/v2"
)

func main() {
	b1 := roaring.BitmapOf(1, 2, 3, 4)     // 用1, 2, 3, 4初始化
	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // 用2, 4, 6, 8, 12初始化

	b1.Add(5)  // 添加5
	b2.Add(10) // 添加10

	b2.Remove(12) // 移除12

	and := roaring.FastAnd(b1, b2)
	or := roaring.FastOr(b1, b2)

	// bitmap运算会修改原始对象,因此使用副本
	xor := b1.Clone()
	xor.Xor(b2)

	log.Printf("and result: %v", and.ToArray())
	log.Printf("or result: %v", or.ToArray())
	log.Printf("xor result: %v", xor.ToArray())
}
```

```shell
2025/09/08 22:16:27 and result: [2 4]
2025/09/08 22:16:27 or result: [1 2 3 4 5 6 8 10]
2025/09/08 22:16:27 xor result: [1 3 5 6 8 10]
```

除上述示例代码中未出现的主要功能外,还包括:

- `Contains(x uint32) bool`:检查特定值是否存在于位图中
- `GetCardinality() uint64`:返回位图中包含的元素个数
- `Rank(x uint32) uint64`:返回小于或等于特定值的元素个数
- `ToBytes() ([]byte, error)`:将位图序列化为字节切片
- `FromBytes(data []byte) error`:从字节切片恢复位图
- `Clone() *Bitmap`:创建位图的副本
- `Clear()`:清空位图
- `NextValue(x uint32) int64`:返回大于或等于x的下一个元素
- `PreviousValue(x uint32) int64`:返回小于或等于x的前一个元素
- `Maximum() uint32`:返回位图中最大的元素
- `Minimum() uint32`:返回位图中最小的元素

以上就是这些功能。详细内容请参考[官方文档](https://pkg.go.dev/github.com/RoaringBitmap/roaring/v2)。

另外,roaring包内部还包含支持uint64的包,而不仅限于uint32。它提供几乎相同的接口,因此可以直接替换使用。

```go
package main

import (
	"log"

	"github.com/RoaringBitmap/roaring/v2/roaring64"
)

func main() {
	b1 := roaring64.BitmapOf(1, 2, 3, 4)     // 用1, 2, 3, 4初始化
	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // 用2, 4, 6, 8, 12初始化

	b1.Add(5)  // 添加5
	b2.Add(10) // 添加10

	b2.Remove(12) // 移除12

	and := roaring64.FastAnd(b1, b2)
	or := roaring64.FastOr(b1, b2)

	// bitmap运算会修改原始对象,因此使用副本
	xor := b1.Clone()
	xor.Xor(b2)

	log.Printf("and result: %v", and.ToArray())
	log.Printf("or result: %v", or.ToArray())
	log.Printf("xor result: %v", xor.ToArray())
}
```

### 结语

Roaring Bitmap是一种强大的工具,能够高效地存储和操作高基数的整数集合。在Go语言中,使用`github.com/RoaringBitmap/roaring`包即可轻松利用Roaring Bitmap的全部功能。该包通过多种容器类型和优化的运算,最大化内存使用效率和性能。在数据库索引、日志分析、统计计算等多个领域,都可以利用Roaring Bitmap实现高效的数据处理。

Roaring Bitmap在大规模数据集上尤其表现出色,可广泛应用于各种应用程序中。结合Go语言简洁高效的语法,Roaring Bitmap为开发者提供了强大的工具。随着Roaring Bitmap的发展,预计将会有更多功能和优化出现。

> 我为什么要做这些呢?是为了在时序数据库中对每个标签进行索引,并实现快速的并集运算。