雷鋒網(wǎng) AI 科技評論按，本文本文來自公眾號“程序員小灰”（ID：chengxuyuanxiaohui），原載于知乎，雷鋒網(wǎng)獲授權轉載。

兩個月之前——

為滿足用戶標簽的統(tǒng)計需求，小灰利用 Mysql 設計了如下的表結構，每一個維度的標簽都對應著 Mysql 表的一列：

要想統(tǒng)計所有90后的程序員該怎么做呢？

用一條求交集的SQL語句即可：

Select count（distinct Name） as 用戶數(shù) from table whare age = '90后' and Occupation = '程序員' ;

要想統(tǒng)計所有使用蘋果手機或者00后的用戶總合該怎么做？

用一條求并集的SQL語句即可：

Select count（distinct Name） as 用戶數(shù) from table whare Phone = '蘋果' or age = '00后' ;

兩個月之后——

———————————————

1. 給定長度是 10 的 bitmap，每一個 bit 位分別對應著從 0 到 9 的 10 個整型數(shù)。此時 bitmap 的所有位都是 0。

2. 把整型數(shù) 4 存入 bitmap，對應存儲的位置就是下標為4的位置，將此 bit 置為 1。

3. 把整型數(shù)2存入bitmap，對應存儲的位置就是下標為2的位置，將此bit置為1。

4. 把整型數(shù)1存入bitmap，對應存儲的位置就是下標為1的位置，將此bit置為1。

5. 把整型數(shù)3存入bitmap，對應存儲的位置就是下標為3的位置，將此bit置為1。

要問此時 bitmap 里存儲了哪些元素？顯然是 4,3,2,1，一目了然。

Bitmap 不僅方便查詢，還可以去除掉重復的整型數(shù)。

1. 建立用戶名和用戶 ID 的映射：
   

   

2. 讓每一個標簽存儲包含此標簽的所有用戶 ID，每一個標簽都是一個獨立的 Bitmap。
   

3. 這樣，實現(xiàn)用戶的去重和查詢統(tǒng)計，就變得一目了然：

1. 如何查找使用蘋果手機的程序員用戶？
   

   

2. 如何查找所有男性或者00后的用戶？

   

   

   

   

一周之后......

我們以上一期的用戶數(shù)據(jù)為例，用戶基本信息如下。按照年齡標簽，可以劃分成 90 后、00 后兩個 Bitmap：

用更加形象的表示，90 后用戶的 Bitmap 如下：

這時候可以直接求得非90后的用戶嗎？直接進行非運算？

顯然，非 90 后用戶實際上只有 1 個，而不是圖中得到的 8 個結果，所以不能直接進行非運算。

同樣是剛才的例子，我們給定 90 后用戶的 Bitmap，再給定一個全量用戶的 Bitmap。最終要求出的是存在于全量用戶，但又不存在于 90 后用戶的部分。

如何求出呢？我們可以使用異或操作，即相同位為 0，不同位為 1。

【 圖片來源：null  所有者：null 】

25769803776 L  =  11000000000000000000000000000000000 B

8589947086 L = 1000000000000000000011000011001110 B

1.解析 Word 0，得知當前 RLW 橫跨的空 Word 數(shù)量為 0，后面有連續(xù) 3 個普通 Word。

2.計算出當前 RLW 后方連續(xù)普通 Word 的最大 ID 是  64 X  (0 + 3) -1 = 191。

3. 由于 191 < 400003，所以新 ID 必然在下一個 RLW（Word4）之后。

4.解析 Word 4，得知當前 RLW 橫跨的空 Word 數(shù)量為 6247，后面有連續(xù) 1 個普通 Word。

5.計算出當前 RLW（Word4）后方連續(xù)普通 Word 的最大 ID 是 191 + （6247 + 1）X64  = 400063。

6.由于 400003 < 400063，因此新 ID 400003 的正確位置就在當前 RLW（Word4）的后方普通 Word，也就是 Word 5 當中。

最終插入結果如下：

官方說明如下：

* Though you can set the bits in any order (e.g., set(100), set(10), set(1),
* you will typically get better performance if you set the bits in increasing order (e.g., set(1), set(10), set(100)).
*
* Setting a bit that is larger than any of the current set bit
* is a constant time operation. Setting a bit that is smaller than an
* already set bit can require time proportional to the compressed
* size of the bitmap, as the bitmap may need to be rewritten.

幾點說明：

1. 該項目最初的技術選型并非Mysql，而是內存數(shù)據(jù)庫hana。本文為了便于理解，把最初的存儲方案寫成了Mysq數(shù)據(jù)庫。

2. 文中介紹的Bitmap優(yōu)化方法在一定程度上做了簡化，源碼中的邏輯要復雜得多。比如對于插入數(shù)據(jù)400003的定位，和實際步驟是有出入的。

3. 如果同學們有興趣，可以親自去閱讀源碼，甚至是嘗試實現(xiàn)自己的Bitmap算法。雖然要花不少時間，但這確實是一種很好的學習方法。

EWAHCompressedBitmap對應的maven依賴如下：

<dependency>
 <groupId>com.googlecode.javaewah</groupId>
 <artifactId>JavaEWAH</artifactId>
 <version>1.1.0</version>
</dependency>

雷峰網(wǎng)版權文章，未經(jīng)授權禁止轉載。詳情見轉載須知。