GoSuda

充满活力的位图

By snowmerak views ...

什么是位图?

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

基本概念

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

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

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

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

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

那么它究竟用在哪里呢

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

1CREATE TABLE IF NOT EXISTS Users (
2    id INT PRIMARY KEY,
3    name VARCHAR(100),
4    active BOOLEAN,
5    sex BOOLEAN,
6    age INT
7);

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

1SELECT * 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语言的特性进行了优化。

安装

1go get github.com/RoaringBitmap/roaring/v2

使用示例

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2"
 7)
 8
 9func main() {
10	b1 := roaring.BitmapOf(1, 2, 3, 4)     // 用1, 2, 3, 4初始化
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // 用2, 4, 6, 8, 12初始化
12
13	b1.Add(5)  // 添加5
14	b2.Add(10) // 添加10
15
16	b2.Remove(12) // 移除12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// bitmap运算会修改原始对象,因此使用副本
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

12025/09/08 22:16:27 and result: [2 4]
22025/09/08 22:16:27 or result: [1 2 3 4 5 6 8 10]
32025/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:返回位图中最小的元素

以上就是这些功能。详细内容请参考官方文档。

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

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2/roaring64"
 7)
 8
 9func main() {
10	b1 := roaring64.BitmapOf(1, 2, 3, 4)     // 用1, 2, 3, 4初始化
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // 用2, 4, 6, 8, 12初始化
12
13	b1.Add(5)  // 添加5
14	b2.Add(10) // 添加10
15
16	b2.Remove(12) // 移除12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// bitmap运算会修改原始对象,因此使用副本
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

结语

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

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

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