一篇带给你索引技术之位图

要点

• 位图基本算法及其应用场景。
• 位图算法的优化实现。

概述

位图算法，是指使用一个bit位来表示数据状态。通常应用于海量数据去重、海量数据计算及判断海量数据中是否存在某个数据的场景中。

以海量数据中是否存在某个数据的应用场景为例，假设用16个bit位，分别表示数字0-15。bit位的值，表示该数字是否存在，0表示不存在，1表示存在。如上图所示，在该数据集合中，存在的元素有1、2、6、10、11和13。

可以发现，在数据比较稠密的情况下，位图算法能够节约存储空间，如图中，使用2个字节便可以表示16个数字，同时可以在O(1)的时间复杂度下，判断是否存在某个数字，大大提高了计算速度。

但是，在数据稀疏时，存储空间会存在一定程度的浪费。由于位图算法中，位图空间的大小是一定的，并不会根据存储数据量的大小而改变。因此，当位图空间中存储的数据量很小时，大量地位图空间是空闲的，存在大量的浪费。

算法实现

位图算法在主流开发语言中，都有对应的实现。基本操作主要有写入、查询、删除、交集、并集等。下面通过一个示例来了解一下，位图算法的实现。

位图结构定义例子使用char类型数组来存储位图信息(通常的实现中，会使用长整型数组)，一个char类型有8个bit位。定义结构如下：

// 为了简化问题，LEN必须定义为CHAR_SIZE的倍数
#define LEN 16
#define CHAR_SIZE 8
typedef char BitSet[LEN/CHAR_SIZE];

写入在某个bit位写入数据时，首先通过整除，计算出该bit位在数组的哪个下标，然后，用取余计算出char元素中的哪个bit上。最后通过或运算将对应位设置为1。

// 置bit位
void set(BitSet& bits, int pos) {
    // 查找对应数组下标
    int unit = pos / CHAR_SIZE;
    // 查找在字节中的bit位
    int p = pos % CHAR_SIZE;
    // 通过与运算实现对应bit位置1
    bits[unit] = bits[unit] | (0x1 << p);

查询同写入操作，先计算出bit位置，查找到对应的bit位，然后返回该位置的数值。

// 查询bit位
int get(BitSet& bits, int pos) {
    // 查找对应数组下标
    int unit = pos / CHAR_SIZE;
    // 查找在字节中的bit位
    int p = pos % CHAR_SIZE;
    // 通过与运算实现对应bit位置1
    return  (bits[unit] & (0x1 << p)) > 0 ? 1 : 0;
}

删除首先查找到对应的位置，然后通过与运算将该位置清空。

// 清空bit位
void clear(BitSet& bits, int pos) {
    // 查找对应数组下标
    int unit = pos / CHAR_SIZE;
    // 查找在字节中的bit位
    int p = pos % CHAR_SIZE;
    // 通过与运算实现对应bit位置1
    bits[unit] = bits[unit] & (~(0x1 << p));
}

交集对数组逐个元素进行或运算。

// 求位图b1和b2的并集
void unionn(const BitSet& b1, const BitSet& b2, BitSet& res) {
    for (auto i = 0; i < (LEN/CHAR_SIZE); ++i) {
        res[i] = b1[i] | b2[i];
    }
}

并集对数组逐元素进行与运算。

// 求位图b1和b2的交集
void inter(const BitSet& b1, const BitSet& b2, BitSet& res) {
    for (auto i = 0; i < (LEN/CHAR_SIZE); ++i) {
        res[i] = b1[i] & b2[i];
    }
}

在生产实现时，可能会进行一些优化：

• 使用CPU指令优化，如SSE等，一次能进行128位的运算，可以提高计算速度。
• 某些业务场景下，一个数据状态可能有大于2个，可以使用多个bit位来表示一个数据状态。

扩展

为了解决位图稀疏时，位图低效率的问题，工业界，有多种位图压缩算法，其中，最经典的是RoaringBitmap。

RoaringBitmap的核心思想是，将整数进行分桶，高16位的值作为其桶的索引，每个桶对应一个容器。如下图所示：

roaring bitmap

容器的结构有三种类型：有序数组、未压缩位图、和行程长度编码。

• 有序数组：当低16位中，元素个数小于4096时，采用有序数组的结构进行存储。在查找元素时，使用二分查找方法。取值4096的原因是，存储4096个16位的整数，所占用的存储空间：。
• 未压缩位图：未压缩位图的存储结果就是本文所描述的位图存储结构，使用一个固定的连续内存块实现。
• 行程长度编码(run-length encoding)：行程长度编码是一种无损数据压缩技术，其原理是，将连续出现的数据存储为起始值和计算两部分。比如，数据列表[1,2,3,4,5,6]存储为[1,5]，表示以1开始，后面连续递增5个数值。在很多实现中，行程长度编码容器，需要手动调用，才能转换为该容器。

在进行插入和删除操作之后，需要根据元素个数进行容器转换。插入元素时，若元素个数达到4096，则需要转换为未压缩位图进行存储。删除元素时，若元素个数小于4096时，则需要转换为有序数组存储。

参考

• Better bitmap performance with Roaring bitmaps。
• Consistently faster and smaller compressed bitmaps with Roaring。
• https://github.com/RoaringBitmap/CRoaring.git。