Bitmaps 數據結構模型

Bitmap 本身不是一種數據結構，實際上它就是字符串，但是它可以對字符串的位進行操作。 比如 “abc” 對應的 ASCII 碼分別是 97、98、99。對應的二進制分別是 01100010、01100010、01100011, 如下所示：

    a        b         c
+--------+--------+--------+
|01100001|01100010|01100011|
+--------+--------+--------+

位圖的最大優點之一是它們在存儲信息時通常可以極大地節省空間。

例如，在一個用增量用戶 ID 表示不同用戶的系統中，僅使用 512 MB 內存就可以記住 40 億個用戶的單個比特信息。
1bit * 4,000,000,000 = 500,000,000 B = 488,281.25 KB = 476.8 MB

GETBIT 僅返回指定索引處的位的值。超出范圍的位（尋址超出目標密鑰中存儲的字符串長度的位）始終被視為零。

root@ubuntu-x64_01:~#  redis-cli --no-auth-warning -h 192.168.88.11 -p 6380 -a "******" get k1 
"a"root@ubuntu-x64_01:~#  redis-cli --no-auth-warning -h 192.168.88.11 -p 6380 -a "******" --eval getbit.lua k1
"01100001"

setbit

設置健的第offset個位的值（從0算起），如有8個用戶 userid = 0, 1, 2, 3, 4, 5, 6,7 ， 其中用戶 1， 3， 5 對網站進行了訪問 ， 那么Bitmaps初始化如下：

setbit key offset value

192.168.88.11:6380> setbit users:2023-12-09 1 1
(integer) 0
192.168.88.11:6380> setbit users:2023-12-09 3 1
(integer) 0
192.168.88.11:6380> setbit users:2023-12-09 5 1
(integer) 0# 獲取當前哪些用戶訪問了 ， 其中 1 表示訪問過的用戶 
root@ubuntu-x64_01:~#   /redis-cli --no-auth-warning -h 192.168.88.11 -p 6380 -a "******" --eval getbit.lua users:2023-12-09
"01010100"

getbit

獲取健的第offset位的值（從0算起）， 如下獲取 user 5 是否在 2023-12-09 訪問過， 1表示訪問，0表示沒有訪問，如果offset不存在，返回結果也是0, 超出范圍的位始終被視為零。

192.168.88.11:6380> getbit users:2023-12-09 5
(integer) 1

bitcount

獲取Bitmaps指定范圍值為1的個數，如統計 2023-12-09 這天訪問的用戶數量

192.168.88.11:6380> bitcount users:2023-12-09
(integer) 3

bitop

bitmaps之前的運算，它可以做and（交集）、or（并集）、not（非）、xor（異或），并將結果保存在 destkey ，如計算 2023-12-09、2023-12-10 兩天都訪問過的用戶數量

root@ubuntu-x64_01:~#  redis-cli  --no-auth-warning -h 192.168.88.11 -p 6380 -a "******" --eval getbit.lua users:2023-12-09
"01010100"
root@ubuntu-x64_01:~#  redis-cli  --no-auth-warning -h 192.168.88.11 -p 6380 -a "******" --evalgetbit.lua users:2023-12-10
"01100110"192.168.88.11:6380> bitop and users:2023-12-09_10 users:2023-12-09 users:2023-12-10
(integer) 1192.168.88.11:6380> bitcount users:2023-12-09_10
(integer) 2root@ubuntu-x64_01:~#  redis-cli --no-auth-warning -h 192.168.88.11 -p 6380 -a "******" --eval getbit.lua users:2023-12-09_10
"01000100"

小結

將位圖拆分為多個鍵很簡單，例如為了對數據集進行分片，并且通常最好避免使用巨大的鍵。要將位圖拆分到不同的鍵上，而不是將所有位設置為一個鍵，一個簡單的策略就是為每個鍵存儲 M 位，并使用 獲取鍵名稱和bit-number/M在鍵（bit-number MOD M）內尋址的第 N 位。

假設 M=10 , 約100個用戶（有點少，僅用作舉例）：

則 第91個用戶尋址如下：健名稱： 91 MOD 10 = 1 即 key = user1 ， N = 91/10 = 9

則 第65個用戶尋址如下：健名稱： 65 MOD 10 = 5 即 key = user5 ， N = 65/10 = 6

SETBIT 、 GETBIT 、BITFIELD 均為 O(1)。

BITCOUNT、BITOP、BITPOS 是 O(n)，其中n是比較中最長字符串的長度。