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

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

写入在某个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

查询同写入操作，先计算出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];

}

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

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

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

roaring bitmap

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

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

最新评论