0
雷鋒網(wǎng) AI 科技評論按，本文本文來自公眾號“程序員小灰”（ID：chengxuyuanxiaohui），原載于知乎，雷鋒網(wǎng)獲授權(quán)轉(zhuǎn)載。
兩個月之前——
為滿足用戶標(biāo)簽的統(tǒng)計(jì)需求，小灰利用 Mysql 設(shè)計(jì)了如下的表結(jié)構(gòu)，每一個維度的標(biāo)簽都對應(yīng)著 Mysql 表的一列：
要想統(tǒng)計(jì)所有90后的程序員該怎么做呢？
用一條求交集的SQL語句即可：
Select count（distinct Name） as 用戶數(shù) from table whare age = '90后' and Occupation = '程序員' ;
要想統(tǒng)計(jì)所有使用蘋果手機(jī)或者00后的用戶總合該怎么做？
用一條求并集的SQL語句即可：
Select count（distinct Name） as 用戶數(shù) from table whare Phone = '蘋果' or age = '00后' ;
兩個月之后——
———————————————
1. 給定長度是 10 的 bitmap，每一個 bit 位分別對應(yīng)著從 0 到 9 的 10 個整型數(shù)。此時 bitmap 的所有位都是 0。
2. 把整型數(shù) 4 存入 bitmap，對應(yīng)存儲的位置就是下標(biāo)為4的位置，將此 bit 置為 1。
3. 把整型數(shù)2存入bitmap，對應(yīng)存儲的位置就是下標(biāo)為2的位置，將此bit置為1。
4. 把整型數(shù)1存入bitmap，對應(yīng)存儲的位置就是下標(biāo)為1的位置，將此bit置為1。
5. 把整型數(shù)3存入bitmap，對應(yīng)存儲的位置就是下標(biāo)為3的位置，將此bit置為1。
要問此時 bitmap 里存儲了哪些元素？顯然是 4,3,2,1，一目了然。
Bitmap 不僅方便查詢，還可以去除掉重復(fù)的整型數(shù)。
建立用戶名和用戶 ID 的映射：
讓每一個標(biāo)簽存儲包含此標(biāo)簽的所有用戶 ID，每一個標(biāo)簽都是一個獨(dú)立的 Bitmap。
3. 這樣，實(shí)現(xiàn)用戶的去重和查詢統(tǒng)計(jì)，就變得一目了然：
如何查找使用蘋果手機(jī)的程序員用戶？
如何查找所有男性或者00后的用戶？
一周之后......
我們以上一期的用戶數(shù)據(jù)為例，用戶基本信息如下。按照年齡標(biāo)簽，可以劃分成 90 后、00 后兩個 Bitmap：
用更加形象的表示，90 后用戶的 Bitmap 如下：
這時候可以直接求得非90后的用戶嗎？直接進(jìn)行非運(yùn)算？
顯然，非 90 后用戶實(shí)際上只有 1 個，而不是圖中得到的 8 個結(jié)果，所以不能直接進(jìn)行非運(yùn)算。
同樣是剛才的例子，我們給定 90 后用戶的 Bitmap，再給定一個全量用戶的 Bitmap。最終要求出的是存在于全量用戶，但又不存在于 90 后用戶的部分。
如何求出呢？我們可以使用異或操作，即相同位為 0，不同位為 1。
【 圖片來源：null 所有者：null 】
25769803776 L = 11000000000000000000000000000000000 B
8589947086 L = 1000000000000000000011000011001110 B
1.解析 Word 0，得知當(dāng)前 RLW 橫跨的空 Word 數(shù)量為 0，后面有連續(xù) 3 個普通 Word。
2.計(jì)算出當(dāng)前 RLW 后方連續(xù)普通 Word 的最大 ID 是 64 X (0 + 3) -1 = 191。
3. 由于 191 < 400003，所以新 ID 必然在下一個 RLW（Word4）之后。
4.解析 Word 4，得知當(dāng)前 RLW 橫跨的空 Word 數(shù)量為 6247，后面有連續(xù) 1 個普通 Word。
5.計(jì)算出當(dāng)前 RLW（Word4）后方連續(xù)普通 Word 的最大 ID 是 191 + （6247 + 1）X64 = 400063。
6.由于 400003 < 400063，因此新 ID 400003 的正確位置就在當(dāng)前 RLW（Word4）的后方普通 Word，也就是 Word 5 當(dāng)中。
最終插入結(jié)果如下：
官方說明如下：
* 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.
幾點(diǎn)說明：
該項(xiàng)目最初的技術(shù)選型并非Mysql，而是內(nèi)存數(shù)據(jù)庫hana。本文為了便于理解，把最初的存儲方案寫成了Mysq數(shù)據(jù)庫。
文中介紹的Bitmap優(yōu)化方法在一定程度上做了簡化，源碼中的邏輯要復(fù)雜得多。比如對于插入數(shù)據(jù)400003的定位，和實(shí)際步驟是有出入的。
如果同學(xué)們有興趣，可以親自去閱讀源碼，甚至是嘗試實(shí)現(xiàn)自己的Bitmap算法。雖然要花不少時間，但這確實(shí)是一種很好的學(xué)習(xí)方法。
EWAHCompressedBitmap對應(yīng)的maven依賴如下：
<dependency>
<groupId>com.googlecode.javaewah</groupId>
<artifactId>JavaEWAH</artifactId>
<version>1.1.0</version>
</dependency>
雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
