「Redis」BitMap 再絮叨

不積跬步，無以至千里；不積小流，無以成江海。

之前寫過一篇關於 BitMap 的文章，寫的並不通透，在大數據下 BitMap 優勢還是顯而易見的，所以決定重寫，面試的時候你能掌握以下絕對是你的加分項。

在我們平時開發過程中，難免會有一些 <strong>bool 型 數據需要存取

比如以下場景：

• 某個用戶是否點贊過某篇文章
• 某個用戶今天是否登陸過
• 某個用戶的簽到情況
• 統計產品的月活

什麼是 BitMap

位圖 並不是特殊的數據結構，它的內容其實就是普通的字符串，也就是 <strong>byte數組，用二進制表示，只有 0 和 1

我們可以使用普通的 <strong>get/set 直接獲取和設置 整個位圖 的內容也可以使用位圖操作 <strong>getbit/setbit 等將 <strong>byte 數組 看成<strong>「位數組」來處理。

如下：

用法

居然不支持 MarkDown, 只有截圖上來了。

優勢

1. 基於最小的單位 bit 進行存儲，節省空間。
2. set 時間複雜度 O(1)、get 時間複雜度 O(n)，操作是非常快的。
3. 二進制數據的存儲，進行相關計算的時候非常快。
4. 自動擴容，如果設置了某個偏移位置超出了現有的內容範圍，就會 自動 將位數組進行零擴充。

弊端

1. redis中bit映射被限制在512MB之內，所以最大是2^32位，再大時需要分片存取。建議每個key的位數都進行控制，因為讀取時候時間複雜度O(n)，越大的串讀的時間花銷越多。
2. offset 稀疏時不建議用，浪費大量內存

空間、時間粗略計算方式

在一臺 2010MacBook Pro上，offset 為 2^32-1（分配512MB）需要～300ms，

offset為2^30-1(分配128MB)需要～80ms，

offset為2^28-1（分配32MB）需要～30ms，

offset為2^26-1（分配8MB）需要8ms。

大概的空間佔用計算公式是：($offset/8/1024/1024)MB

使用場景

用戶簽到

記錄用戶每天簽到情況，同時能快速知道用戶某天是否簽到

偽代碼：

活躍用戶

統計某段時間內的活躍用戶 只需要一個key，然後用戶id為偏移量offset，如果登陸過就設置為1，反之就設置為0，

偽代碼：

視頻屬性的無限延伸

一個擁有億級數據量的短視頻app，視頻存在各種屬性(是否加鎖、是否特效等等)，需要做各種標記。數據量大又無限延伸， BitMap可能會達到瓶頸，我們考慮用分片來處理。

key：由屬性id＋視頻分片id組成。value：按照視頻id對分片 來決定偏移量offset

以上只是舉了幾個典型的例子，具體情況具體分析該如何設計key 和 offset。

避坑

bitcout bitpos 的 start end 都是 <strong>字節索引

有圖有真相：

點關注 不迷路

以上就是這篇的全部內容，能看到這裡的都是 <strong>人才。

如果你從本篇內容有收穫，求 <strong>點贊，求 <strong>關注

如果本文有任何錯誤，請批評指教，不勝感激 ！

閱讀更多 不住隔壁的王老師 的文章

關鍵字: 絮叨 數據結構 設計