大數據計數原理1+0=1這你都不會算(八)
插播一條新聞，為什么要插播，嗯不知道可能今天心情比較好，畢竟中秋了嘛~
今天跟小伙伴們聊聊另外一個統計算法, Roaring BitMaps。
這個改怎么翻譯呢??咆哮的位圖?s?我翻譯不出來，但是小蕉頭一歪，就給它起了一個狂拽酷霸叼扎天的翻譯 -> 咆哮吧，位圖君們。
照例甩一波鏈接。
來了喔。
根據官方統計，已經有這么多大項目在用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入門、大數據、機器學習入門方面的問題也可以問我，我看到會回的，有什么想看的想聽的也可以告訴我，我會把放入我的需求池的，啊哈哈哈哈哈。
都看到這了，真愛的你，不點個贊嗎?
【本文為51CTO專欄作者“大蕉”的原創稿件，轉載請通過作者微信公眾號“一名叫大蕉的程序員”獲取授權】
