大數據計數原理1+0=1這你都不會算(八)No.60

02-12

插播一條新聞，為什麼要插播，嗯不知道可能今天心情比較好，畢竟中秋了嘛~

今天跟小夥伴們聊聊另外一個統計演算法, Roaring BitMaps。

這個改怎麼翻譯呢??咆哮的點陣圖?s?我翻譯不出來，但是小蕉頭一歪，就給它起了一個狂拽酷霸叼扎天的翻譯 -> 咆哮吧，點陣圖君們。

照例甩一波鏈接。

大數據計數原理1+0=1這你都不會算(一)No.47 <- HashSet

大數據計數原理1+0=1這你都不會算(二)No.50 <- BitMap

大數據計數原理1+0=1這你都不會算(三)No.51 <- BloomFilter

大數據計數原理1+0=1這你都不會算(四)No.52 <- B-Tree

大數據計數原理1+0=1這你都不會算(五)No.55 <- B+Tree

大數據計數原理1+0=1這你都不會算(六)No.57 <- LinearCounting（一）

大數據計數原理1+0=1這你都不會算(七)No.59 <- LinearCounting（二）

來了喔。

根據官方統計，已經有這麼多大項目在用Roaring BitMaps了，老牛逼了。

Apache Lucene and derivative systems such as Solr and Elasticsearch,
Metamarkets』 Druid,
Apache Spark,
Apache Hive,
Apache Tez,
Netflix Atlas,
LinkedIn Pinot,
OpenSearchServer,
Cloud Torrent,
Whoosh,
Pilosa,
Microsoft Visual Studio Team Services (VSTS),
Jive Miru,
eBay』s Apache Kylin.

那麼勤勞又聰明的你一定會問了，這是什麼東西？用來幹啥的？怎麼用的？從用途來看，Roaring BitMaps 就是一個用來進行基數統計的演算法。

用途有三隻：

第一隻當然就是基數統計啦，count之類的，可節省空間了。

第二隻呢，資料庫在執行Join的時候，要知道Join之前是多少量級，Join完又是什麼量級，再執行相應的優化策略。

第三隻呢，是作為索引存在，可以作為資料庫判斷唯一索引的唯一性。

等等。

關於這個演算法呢，也不是什麼非常難的東西，原始論文其實講得蠻詳細的了，看看原始論文一般就能看懂了。但小蕉在這裡，其實用三句話就可以把這個演算法說清楚了。

1、把n長的區間劃分為2^16個桶（n為Roaring BitMaps 的總長度），每個桶放一個Container，作為一級索引存在。

2、每個int數值k為32位的bit，我們取前16位找到對應的桶(k % 2^16)，Container裡面只保存後16位 (k mod 2^16) 。若Container為BitMap，直接把第 (k mod 2^16) 位設置為1即可，若Container為Array，則用二分查找插入法，有序插入。

3、若一個Container裡面的Integer數量小於4096，就用Short類型的有序數組來存儲值。若大於4096，就用BitMap來存儲值。數據用來放稀疏的數據，BitMap用來放緊密的數據（至於為啥，請重新看BitMap的定義及使用範圍）。

實際使用的時候怎麼找到值呢？跟原來插入值一樣，因為Containers是有序的嘛，也有自己的數據範圍，所以首先用二分查找找到數據對應的Container。然後分兩種情況，如果是Container是數組，就再用一次二分查找。如果Container是BitMap，直接找到對應的位是不是1就行了。

好啦，演算法方面就這樣說完了，但是又有小朋友要問了，那這樣存儲完有什麼用呢？只需要定義三種操作，AND,OR,NOT，就可以快速進行兩個集合的操作了。

因為Container有兩種，BitMap和Array ，所以進行合併操作的時候會有三種情況。

1、Array vs Array

2、Array vs BitMap

3、BitMap vs BitMap

分別是怎麼處理呢，下面所說的操作指的你所希望的功能是AND、OR、還是NOT？選一種操作進行計算就行了。

Array vs Array ，直接用演算法merge成一個數組，再進行相應的操作即可。

Array vs BitMap，遍歷一下Array，把它的值一個一個映射到BitMap上並操作，最終統計一下BitMap即可。

BitMap vs BitMap，直接按位操作即可。

實際實現的時候，不僅僅會有Short類型的Array，拓展開可以是任何基礎數據類型的Array，功能越來越豐富了。

關於論文和Github地址，後台直接回復 Roaring 可以獲取到。

沉迷學習，日漸消瘦。大家如果有什麼健身、Java入門、大數據、機器學習入門方面的問題也可以問我，我看到會回的，有什麼想看的想聽的也可以告訴我，我會把放入我的需求池的，啊哈哈哈哈哈。

都看到這了，真愛的你，不點個贊嗎？