BitMap

BitMap 的基本思想

BitMap 的基本思想是用一个 bit 位来标记某个元素对应的 Value，而 Key 即是该元素。由于采用了 Bit 为单位来存储数据，可以很大力度的节省空间，常用于对大量整数做去重和查询操作。

位图（bitmap）的方式存储了 [0, 2^32 - 1] 区间上的数据，需要耗费 512MB 的存储空间。

如果我们想快速排序 {6,8,2,5,4}，根据位图我们应该：

BitMap 常见应用场景

• 快速排序
• 快速去重
• 快速查找

BitMap 不足点

1. 数据碰撞：比如将字符串映射到 BitMap 的时候会有碰撞的问题，那就可以考虑用 Bloom Filter 来解决，Bloom Filter 使用多个 Hash 函数来减少冲突的概率。
2. 数据稀疏：又比如要存入 (10,8887983,93452134) 这三个数据，我们需要建立一个 99999999 长度的 BitMap，但是实际上只存了 3 个数据，这时候就有很大的空间浪费，碰到这种问题的话，可以通过引入 Roaring BitMap 来解决。

RoaringBitmap

1. 将 32bit 划分为 2^16 个桶，每个桶有一个 Container 来存放一个数值的低 16 位。
2. 在存储和查询数值时，将数值 k 划分为高 16 位 (k % 2^16) 和低 16 位 (k mod 2^16)，取高 16 位找到对应的桶，然后在低 16 位存放在相应的 Container 中。
3. RBM 常用两种容器结构：ArrayContainer 和 BitmapContainer。
   • ArrayContainer 存放稀疏的数据，BitmapContainer 存放稠密的数据，即：
     • 若一个 Container 中的 Integer 数量小于 4096，就用 char 数组 (ArrayContainer) 来存储值。
     • 若大于 4096，就用 BitmapContainer 来存储值。
   • Integer 的低 16 位是 2Byte，因此对应到 ArraryContainer 就是 2Byte * 4096 = 8KB；同样，BitmapContainer 的 2^16 个 bit 也相当于是 8KB。

short[] content 始终保持有序，方便使用二分查找，且不会存储重复数值。

示例讲解

将 821697800 这个 32 bit 的整数插入 RBM 中，整个算法流程如下：

821697800 对应的 16 进制数为 30FA1D08，其中高 16 位为 30FA，低 16 位为 1D08。

1. 先用二分查找从一级索引（即 ArrayContainer）中找到数值为 30FA 的容器（若容器不存在，则新建一个）。
2. 从图中我们可以看到，该容器是一个 Bitmap 容器。
3. 找到容器后，其低 16 位的数值 1D08，即 7432，因此在 Bitmap 中找到相应位置，将其置为 1 即可。

RBM 处理的是 32 位的数字，如果我们想处理 Long 类型的数字怎么办呢？这个时候可以使用 Roaring64NavigableMap。Roaring64NavigableMap 也是使用拆分模式，将一个 long 类型数据，拆分为高 32 位与低 32 位，高 32 位代表索引，低 32 位存储到对应 RoaringBitmap 中，其内部是一个 TreeMap 类型的结构，会按照 signed 或者 unsigned 进行排序，key 代表高 32 位，value 代表对应的 RoaringBitmap。

Container 分类

• ArrayContainer：当桶内数据的基数不大于 4096 时，会采用它来存储。
• BitmapContainer：当桶内数据的基数大于 4096 时，会采用它来存储。
• RunContainer：使用 Run-Length Encoding 方式压缩存储的元素，对连续数据的压缩效果特别好，但如果数据比较散列，反而会更占用空间，长度没有限制；这种压缩算法的性能和数据的连续性（紧凑性）关系极为密切。
• SharedContainer：它本身是不存储数据的，只是用它来指向 ArrayContainer, BitmapContainer 或 RunContainer，就好比指针的作用一样。这个指针（SharedContainer）可以被多个对象拥有，但是指针所指向的实质东西是被这多个对象所共享的。

ArrayContainer 存储稀疏数据，BitmapContainer 存储稠密数据，可以最大限度地避免内存浪费。

Container 性能总结

读取时间

只有 BitmapContainer 可根据下标直接寻址，复杂度为 O(1)，ArrayContainer 和 RunContainer 都需要二分查找，复杂度 O(log n)。

内存占用

• ArrayContainer 一直线性增长，在达到 4096 后就完全比不上 BitmapContainer 了，适合小数据量的存储。
• BitmapContainer 是一条横线，始终占用 8kb，当大于 4096 会自动转为 BitmapContainer。
• RunContainer 比较奇葩，因为和数据的连续性关系太大，因此只能画出一个上下限范围。不管数据量多少，下限始终是 4 字节；上限在最极端的情况下可以达到 128kb。

空间占用对比

1. 连续数据

2. 稀疏数据

我们向位图中插入 1 和 999w 两个偏移量位的元素，再次对比 BitMap 和 RoaringBitMap 所占用空间大小。

RoaringBitmap 相较于 BitMap 的优势

内存上

Bitmap 比较适用于数据分布比较稠密的存储场景中，对于原始的 Bitmap 来说，若要存储 uint32 类型数据，这就需要 2^32 长度的 bit 数组。通过计算可以发现 (2^32 / 8 bytes = 512MB)，一个普通的 Bitmap 需要耗费 512MB 的存储空间。如果我们只存储几个数据的话依然需要占用 521M 空间，这就有些浪费空间了，因此我们可以采用对位图进行压缩的 RoaringBitMap，以此减少内存和提高效率。

性能上

RoaringBitmap 除了比 Bitmap 占用内存少之外，其并集和交集操作的速度也要比 Bitmap 的快。原因归结为以下几点：

1. 计算上的优化：对于 RoaringBitmap 本质上是将大块的 Bitmap 分成各个小块，其中每个小块在需要存储数据的时候才会存在。所以当进行交集或并集运算的时候，RoaringBitmap 只需要去计算存在的一些块而不需要像 Bitmap 那样对整个大的块进行计算。如果块内非常稀疏，那么只需要对这些小整数列表进行集合的 AND、OR 运算，这样的话计算量还能继续减轻。这里既不是用空间换时间，也没有用时间换空间，而是用逻辑的复杂度同时换取了空间和时间。同时在 RoaringBitmap 中 32 位长的数据，被分割成高 16 位和低 16 位，高 16 位表示块偏移，低 16 位表示块内位置，单个块可以表达 64k 的位长，也就是 8K 字节。这样可以保证单个块都可以全部放入 L1 Cache，可以显著提升性能。
2. 程序逻辑上的优化：
   • RoaringBitmap 维护了排好序的一级索引，以及有序的 ArrayContainer 当进行交集操作的时候，只需要根据一级索引中对应的值来获取需要合并的容器，而不需要合并的容器则不需要对其进行操作直接过滤掉。
   • 当进行合并的 ArrayContainer 中数据个数相差过大的时候采用基于二分查找的方法对 ArrayContainer 求交集，避免不必要的线性合并花费的时间开销。
   • RoaringBitmap 在做并集的时候同样根据一级索引只对相同的索引的容器进行合并操作，而索引不同的直接添加到新的 RoaringBitmap 上即可，不需要遍历容器。
   • RoaringBitmap 在合并容器的时候会先预测结果，生成对应的容器，避免不必要的容器转换操作。

StarRocks 的 Bitmap 去重是基于 Roaring Bitmap 实现的，Roaring Bitmap 只能对 TINYINT，SMALLINT，INT 和 BIGINT 类型的数据去重。如想要使用 Roaring Bitmap 对其他类型的数据去重，则需要构建全局字典。

如列基数较低，值大量重复，例如 ENUM 类型的列，使用 Bitmap 索引能够减少查询的响应时间。

如列基数较高，推荐使用 Bloom filter 索引。

Bitmap index 和 Bitmap 去重二者虽然都使用 Bitmap 技术，但引入原因和解决的问题完全不同。前者用于低基数的枚举型列的等值条件过滤，后者则用于计算一组数据行的指标列的不重复元素的个数。

BloomFilter

布隆过滤器的原理是，当一个元素被加入集合时，通过 K 个散列函数将这个元素映射成一个位数组中的 K 个点，把它们置为 1。检索时，我们只要看看这些点是不是都是 1 就（大约）知道集合中有没有它了：如果这些点有任何一个 0，则被检元素一定不在；如果都是 1，则被检元素很可能在。这就是布隆过滤器的基本思想。

Bloom filter 本质就是：K 个 hash 函数 + BitMap。

判断是否存在

向布隆过滤器查询某个 key 是否存在时，先把这个 key 通过多个 hash 函数进行运算，查看对应的位置是否都为 1，只要有一个位为 0，那么说明布隆过滤器中这个 key 不存在。如果这几个位置全都是 1，那么说明极有可能存在。

记住结论：不存在的一定不存在，存在的不一定存在。BloomFilter 只能保证过滤掉不包含的元素，而不能保证误判包含。

Bloom filter 使用场景

1. 解决缓存穿透的问题
2. 海量数据下垃圾邮件解决方案（垃圾短信、黑名单建验）
3. 海量去重（爬虫 URL 去重和分库分表注册手机号唯一性解决方案）
4. SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间。

Bloom filter 优缺点

优点

• 占用空间小，查询速度快，空间效率和查询时间都远远超过一般的算法。

缺点

• 有一定的误识别率，即某个元素可能存在，但实际上并不存在。
• 可以添加元素但删除元素困难，因为无法确定某个位置是由哪个元素映射而来的。因为删掉元素会导致误判率增加。

BloomFilter 参数取值

假设 BloomFilter 中元素总 bit 数量为 m（即 bit array 大小），插入的元素个数为 n，hash 函数的个数为 k，误判率为 p。

如果最小化误判率，则 k 的取值：

而 p 的取值又和 m, n 有如下关系：

将 m 的计算公式带入上式，可得给定 n 和 p，k 的取值应为：

如何解决布隆过滤器不支持删除的问题？

Counting Bloom Filter 将标准 Bloom Filter 位数组的每一位扩展为一个小的计数器（counter），在插入元素时给对应的 k（k 为哈希函数个数）个 Counter 的值分别加 1，删除元素时给对应的 k 个 Counter 的值分别减 1。Counting Bloom Filter 通过多占用几倍的存储空间的代价，给 Bloom Filter 增加了删除操作。

end