GoSuda

活跃位图

By snowmerak
views ...

什么是 Bitmap？

此处的 Bitmap 是一种索引类型。如果您是抱着图形学方面的想法点进来的，那么可以点击返回键了。

基本概念

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

例如，假设有一个包含性别列的表。该表有 5 行，性别列的值如下：

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

在这种情况下，性别列的 Bitmap 索引可以表示如下：

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

那么它到底用在哪里呢？

因此，大家都会认为它不仅仅是为了表示这些。为了正确使用 Bitmap 索引，我们考虑以下情况。

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 的行的方法就是利用比特 AND 运算。

  • 假设 active 列的 Bitmap 索引已预先索引为 1100110011... (1,000,000 个比特数组)，
  • 假设 sex 列的 Bitmap 索引已预先索引为 1010101010... (1,000,000 个比特数组)。

那么，对这两个 Bitmap 索引执行比特 AND 运算，可以快速找到两个列都为 TRUE 的行。由于是简单的比特运算，因此获取结果的速度将比其他索引扫描快得多。

权衡

Bitmap 索引可能非常高效，但也有一些权衡。尽管存在许多其他缺点，但目前我们只提及一个。

那就是 Bitmap 索引更适用于低基数（即列中可能值的数量较少的情况）。在高基数列上使用 Bitmap 索引可能会导致 Bitmap 变得非常大。

在高基数列上使用 Bitmap 索引时，由于必须为每个唯一值生成单独的 Bitmap，因此可能需要大量的存储空间。例如，如果列中有 1,000,000 个唯一值，则必须生成 1,000,000 个 Bitmap，这可能非常低效。

那么我们

我们可以使用 Roaring Bitmap 来替代高基数带来的 Bitmap。Roaring Bitmap 具有多种特性，但其最大的基本理念和特性是“根据数据的密度动态选择最合适的存储方式，从而最大化压缩率和运算速度”。

Roaring Bitmap 的基本概念

两阶段索引

Roaring Bitmap 在存储一个整数时，首先需要经过以下两个阶段。说是两阶段索引，其实可以理解为二维数组。

  • 提取高 16 位：提取整数的高 16 位，并将其用作索引。它成为一个长度为 65536 的二维数组中外部数组的索引。该数组存储了后续将提及的容器的地址。
  • 提取低 16 位：提取整数的低 16 位，并将其用作容器内的位置。

容器

这个容器正如刚才比喻的那样，对应于二维数组中的内部数组。但是，与高 16 位的容器不同，这个容器的内部结构会根据内部数据的多少而变化。Roaring Bitmap 支持以下三种容器。

  • Array Container：当内部存储的数据较少时使用此容器。具体来说，当存储少于 4096 个元素时使用。此容器仅由排序的整数数组实现。可以通过二分查找来查找元素。
  • Bitmap Container：当内部存储的数据较多时使用此容器。具体来说，当存储超过 4096 个元素时使用。此容器由 65536 位（8192 字节）的 Bitmap 实现。每个比特表示该位置的整数是否存在。
  • Run Container：当存储连续的整数范围时使用此容器。例如，当存储 1, 2, 3, 4, 5 等连续整数时，效率很高。此容器由 (起始值, 长度) 对的列表实现。如果所有值都存在？那意味着从头到尾都存在，只需存储 (0, 65536) 即可。

这种方式使得 Roaring Bitmap 能够非常有效地利用内存，并为各种数据密度提供最佳性能。

Roaring Bitmap 的功能

基本功能

Roaring Bitmap 提供以下基本功能。

  • 插入：向 Bitmap 添加新的整数。在此过程中，可以选择合适的容器，或者在需要时转换容器。
  • 删除：从 Bitmap 中移除现有整数。在此过程中，也会根据容器的状态进行适当的处理。
  • 搜索：检查特定整数是否存在于 Bitmap 中。此过程执行速度非常快。

集合运算

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

  • 并集 (Union)：创建包含两个 Bitmap 所有元素的新 Bitmap。
  • 交集 (Intersection)：创建仅包含两个 Bitmap 中都存在的元素的新 Bitmap。
  • 对称差集 (Symmetric Difference)：创建仅包含两个 Bitmap 中一个存在的元素的新 Bitmap。

这些运算根据 Bitmap 的容器类型进行了优化，执行速度非常快。

在 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：检查特定值是否存在于 Bitmap 中
  • GetCardinality() uint64：返回 Bitmap 中包含的元素数量
  • Rank(x uint32) uint64：返回小于或等于特定值的元素数量
  • ToBytes() ([]byte, error)：将 Bitmap 序列化为字节切片
  • FromBytes(data []byte) error：从字节切片恢复 Bitmap
  • Clone() *Bitmap：创建 Bitmap 的副本
  • Clear()：初始化 Bitmap
  • NextValue(x uint32) int64：返回大于或等于 x 的下一个元素
  • PreviousValue(x uint32) int64：返回小于 x 的上一个元素
  • Maximum() uint32：返回 Bitmap 中最大的元素
  • Minimum() uint32：返回 Bitmap 中最小的元素

有关这些功能的详细信息，请参阅官方文档。

值得注意的是，roaring 包内部不仅支持 uint32，还包含支持 uint64 的包。它们提供几乎相同的接口，因此可以直接替换使用。

 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 将会不断发展，并带来更多功能和优化。

我为什么会做这个呢？为了在时序数据库中实现每个标签的索引和快速的并集运算。