一篇帶給你索引技術(shù)之位圖

作者：咸X蛋 2022-03-29 08:18:32

位圖算法，是指使用一個(gè)bit位來表示數(shù)據(jù)狀態(tài)。通常應(yīng)用于海量數(shù)據(jù)去重、海量數(shù)據(jù)計(jì)算及判斷海量數(shù)據(jù)中是否存在某個(gè)數(shù)據(jù)的場景中。

要點(diǎn)

位圖基本算法及其應(yīng)用場景。
位圖算法的優(yōu)化實(shí)現(xiàn)。

概述

以海量數(shù)據(jù)中是否存在某個(gè)數(shù)據(jù)的應(yīng)用場景為例，假設(shè)用16個(gè)bit位，分別表示數(shù)字0-15。bit位的值，表示該數(shù)字是否存在，0表示不存在，1表示存在。如上圖所示，在該數(shù)據(jù)集合中，存在的元素有1、2、6、10、11和13。

可以發(fā)現(xiàn)，在數(shù)據(jù)比較稠密的情況下，位圖算法能夠節(jié)約存儲(chǔ)空間，如圖中，使用2個(gè)字節(jié)便可以表示16個(gè)數(shù)字，同時(shí)可以在O(1)的時(shí)間復(fù)雜度下，判斷是否存在某個(gè)數(shù)字，大大提高了計(jì)算速度。

但是，在數(shù)據(jù)稀疏時(shí)，存儲(chǔ)空間會(huì)存在一定程度的浪費(fèi)。由于位圖算法中，位圖空間的大小是一定的，并不會(huì)根據(jù)存儲(chǔ)數(shù)據(jù)量的大小而改變。因此，當(dāng)位圖空間中存儲(chǔ)的數(shù)據(jù)量很小時(shí)，大量地位圖空間是空閑的，存在大量的浪費(fèi)。

算法實(shí)現(xiàn)

位圖算法在主流開發(fā)語言中，都有對應(yīng)的實(shí)現(xiàn)。基本操作主要有寫入、查詢、刪除、交集、并集等。下面通過一個(gè)示例來了解一下，位圖算法的實(shí)現(xiàn)。

位圖結(jié)構(gòu)定義例子使用char類型數(shù)組來存儲(chǔ)位圖信息(通常的實(shí)現(xiàn)中，會(huì)使用長整型數(shù)組)，一個(gè)char類型有8個(gè)bit位。定義結(jié)構(gòu)如下：

// 為了簡化問題，LEN必須定義為CHAR_SIZE的倍數(shù)
#define LEN 16
#define CHAR_SIZE 8
typedef char BitSet[LEN/CHAR_SIZE];

寫入在某個(gè)bit位寫入數(shù)據(jù)時(shí)，首先通過整除，計(jì)算出該bit位在數(shù)組的哪個(gè)下標(biāo)，然后，用取余計(jì)算出char元素中的哪個(gè)bit上。最后通過或運(yùn)算將對應(yīng)位設(shè)置為1。

// 置bit位
void set(BitSet& bits, int pos) {
    // 查找對應(yīng)數(shù)組下標(biāo)
    int unit = pos / CHAR_SIZE;
    // 查找在字節(jié)中的bit位
    int p = pos % CHAR_SIZE;
    // 通過與運(yùn)算實(shí)現(xiàn)對應(yīng)bit位置1
    bits[unit] = bits[unit] | (0x1 << p);

查詢同寫入操作，先計(jì)算出bit位置，查找到對應(yīng)的bit位，然后返回該位置的數(shù)值。

// 查詢bit位
int get(BitSet& bits, int pos) {
    // 查找對應(yīng)數(shù)組下標(biāo)
    int unit = pos / CHAR_SIZE;
    // 查找在字節(jié)中的bit位
    int p = pos % CHAR_SIZE;
    // 通過與運(yùn)算實(shí)現(xiàn)對應(yīng)bit位置1
    return  (bits[unit] & (0x1 << p)) > 0 ? 1 : 0;
}

刪除首先查找到對應(yīng)的位置，然后通過與運(yùn)算將該位置清空。

// 清空bit位
void clear(BitSet& bits, int pos) {
    // 查找對應(yīng)數(shù)組下標(biāo)
    int unit = pos / CHAR_SIZE;
    // 查找在字節(jié)中的bit位
    int p = pos % CHAR_SIZE;
    // 通過與運(yùn)算實(shí)現(xiàn)對應(yīng)bit位置1
    bits[unit] = bits[unit] & (~(0x1 << p));
}

交集對數(shù)組逐個(gè)元素進(jìn)行或運(yùn)算。

// 求位圖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];
    }
}

并集對數(shù)組逐元素進(jìn)行與運(yùn)算。

// 求位圖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];
    }
}

在生產(chǎn)實(shí)現(xiàn)時(shí)，可能會(huì)進(jìn)行一些優(yōu)化：

使用CPU指令優(yōu)化，如SSE等，一次能進(jìn)行128位的運(yùn)算，可以提高計(jì)算速度。
某些業(yè)務(wù)場景下，一個(gè)數(shù)據(jù)狀態(tài)可能有大于2個(gè)，可以使用多個(gè)bit位來表示一個(gè)數(shù)據(jù)狀態(tài)。

擴(kuò)展

為了解決位圖稀疏時(shí)，位圖低效率的問題，工業(yè)界，有多種位圖壓縮算法，其中，最經(jīng)典的是RoaringBitmap。

RoaringBitmap的核心思想是，將整數(shù)進(jìn)行分桶，高16位的值作為其桶的索引，每個(gè)桶對應(yīng)一個(gè)容器。如下圖所示：

roaring bitmap

容器的結(jié)構(gòu)有三種類型：有序數(shù)組、未壓縮位圖、和行程長度編碼。

有序數(shù)組：當(dāng)?shù)?6位中，元素個(gè)數(shù)小于4096時(shí)，采用有序數(shù)組的結(jié)構(gòu)進(jìn)行存儲(chǔ)。在查找元素時(shí)，使用二分查找方法。取值4096的原因是，存儲(chǔ)4096個(gè)16位的整數(shù)，所占用的存儲(chǔ)空間：。
未壓縮位圖：未壓縮位圖的存儲(chǔ)結(jié)果就是本文所描述的位圖存儲(chǔ)結(jié)構(gòu)，使用一個(gè)固定的連續(xù)內(nèi)存塊實(shí)現(xiàn)。
行程長度編碼(run-length encoding)：行程長度編碼是一種無損數(shù)據(jù)壓縮技術(shù)，其原理是，將連續(xù)出現(xiàn)的數(shù)據(jù)存儲(chǔ)為起始值和計(jì)算兩部分。比如，數(shù)據(jù)列表[1,2,3,4,5,6]存儲(chǔ)為[1,5]，表示以1開始，后面連續(xù)遞增5個(gè)數(shù)值。在很多實(shí)現(xiàn)中，行程長度編碼容器，需要手動(dòng)調(diào)用，才能轉(zhuǎn)換為該容器。

在進(jìn)行插入和刪除操作之后，需要根據(jù)元素個(gè)數(shù)進(jìn)行容器轉(zhuǎn)換。插入元素時(shí)，若元素個(gè)數(shù)達(dá)到4096，則需要轉(zhuǎn)換為未壓縮位圖進(jìn)行存儲(chǔ)。刪除元素時(shí)，若元素個(gè)數(shù)小于4096時(shí)，則需要轉(zhuǎn)換為有序數(shù)組存儲(chǔ)。