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

要点位图基本算法及其应用场景。篇带位图算法的引技优化实现。概述

位图算法，位图是篇带指使用一个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。