用位圖索引技術實作超大規模資料量的分組算法

最近在做一個商業智能軟體，也就是我們大家通常說的BI。找了許多資料，關于資料挖掘裡面資料立方體的算法到時介紹的很多，但是個人卻始終覺得沒有什麼實際的意義。而我所說的位圖索引，也是書中概念的一部分。我把它拿來用來了，但是不是書中所說的一般的方式。個人也覺得挺幸運的，僥幸的知道了位圖索引的概念，然後又僥幸的通過位圖索引解決了大資料量處理的問題。可能前人已經想到了類似的方法，但是以下說訴，都是個人的思想。

先介紹下位圖索引的概念。如果有個二維的銷售表，包含以下幾個字段：省份、銷售員、産品類型、産品。簡單的假設表的值如下：

銷售

省份	銷售員	産品類型	産品
江蘇	jack	手機	iphone
江蘇	jane	家電	電視機
浙江	apple	手機	n97
浙江	tom	家電	電冰箱
江蘇	Jerry	家電	電磁爐

位圖索引，簡單的了解就是用位置去表示值，而且能知道制定位置是否存在值。實際的位圖索引是這樣子的資料結構：

針對省份裡面的“江蘇”，因為表裡面第0、1、4行是江蘇，那麼可以就在該行用1表示。具體結果如下：

行号	江蘇	浙江
1
1	1
2	1
3	1
4	1

上面的表格其實是圖的資料結構，可以用圖的算法進行壓縮存儲。但是，前提是：保證索引快速準确。因為圖經過壓縮後，如果我想知道第n行第m列的位置是0還是1，還要經過算法的轉化。如果直接用二維數組儲存上訴索引，那麼直接能取到制定位置。

現在來介紹下分組的算法：

假設我們要對省份、産品類型兩個字段進行分組：

省份裡面有兩個值：江蘇和浙江。先把江蘇的索引給取出來，是11001。然後取産品類型的位圖索引：手機-10100、家電01011。

我們把江蘇-11001和手機-10100比較，同時有1的位置就是既有江蘇又有手機的位置，也就是對11001、10100求與運算，得到結果10000，10000不全為0，說明存在這個分組，而且位置是第0行。再将江蘇-11001和家電-01011求與得到01001，存在這個分組，而且位置是第1、4行。如果全部為0，說明不存在這個組合的分組。

這樣一層次一層次的周遊下去，就會得到一個樹形的資料結構。也就是分組的結果。如下：

root---江蘇（11001）---手機（10000）

      ---家電（01001）

       ---浙江（00110）---手機（00100）

    ---家電（00010）

這樣分組的好出有一下幾點：

1.速度快。主要運算基本都是“與”運算

上訴的分組過程中，字段不同值之間的分組結果其實是不相幹的。（我想先算江蘇或者先算浙江都一樣，而且兩者互相直接沒有任何關系，因為它們的位圖索引其實是互斥的）

不相幹帶來幾個好處：

2.傳統的分組算法，必須将關系表周遊幾遍，得到最終準确結果，才能準确展示。而位圖索引的不相幹性，表明了分組完全可以部分計算。比如說：我隻計算江蘇的分組，一層一層的與下去，當結果數根節點的個數打到了目前頁裡面的條數，那麼就可以break了（後者你背景繼續算）。

是以，部分計算、部分展示的特性是其強大的優點。

3.多線程計算。不相幹代表了計算結果互不影響，那麼多線程計算就是必須添加進去了。可以多線程計算分組、或者彙總

4.過濾（條件分組）很友善。拿過濾條件（過濾條件也可以轉換成位圖），與樹節點中的每個節點求與操作，如果全0，從樹中舍棄該節點及其子節點。比如說求條件為“銷售員=jack”下的省份、産品類型分組，該條件的位圖為：10000，然後去上面的樹進行與操作。實際的過濾條件可能較為複雜，需要進過各種“與”、“或”等操作得到。

5.彙總值、平均值等計算方法。隻要取根節點裡面所存位圖的，然後取位圖中值為1的位置相應的彙總字段，求彙總即可。也可以加入多線程。

6.排序非常簡單。隻要對一個節點的子節點進行排序就行。簡單的疊代周遊

7.省去許多重複計算。比如存在了“省份、銷售員、産品類型”的結果，求“省份、銷售員”就直接從前者的樹裡面截取就得到了。

實際操作中存在幾個難點：

位圖索引的儲存、壓縮問題。

我是用了幾種方法：

1.用long數組儲存。一個long值就是64個位置，那麼每個位置都與實際的位置想對應。為何不用int或者short之類的呢。因為long是64位，假如640000行資料，我隻要10000個long，意味着位圖索引與的時候隻要周遊10000次。而用int，就是20000次了。

2.long數組能快速的取，快速的周遊，但是在大資料量的時候，所占的記憶體空間也很大。比如說1000W行的資料，那麼就是1000W/64個long值，大約是1M的記憶體空間。假如該字段裡面的值不是很多，我們還可以接受這種資料結構。假如省份有10000個，那麼這樣子就不行了，會記憶體溢出。當然可以将索引儲存到本地檔案，用的時候再讀取。但是這畢竟不是最終解決之道。

3.我用了其他兩中方式來儲存上述狀況，但是這兩種還有差别。

第一種：一個有順序的“1”的位置清單。假如1000W行資料中，省份=“江蘇”的位置隻有1,10000行這兩個位置，那麼就是儲存的1和10000。這種情況在數字字段裡面較多，因為一些随機數字重複出現的機率很低。但是這樣資料結構必須用的時候才能生成。原因很簡單：1000W個不同的數字，就說明有1000W個不同的位圖索引，每個裡面的都有一個位置，而這個位置又是一個整數，也就是說明有1000W個整數在記憶體中。顯然不可取。是以呢，快速的生成這種資料結構是個值得研究的，而且這種資料結構與上面的long數組做“與”操作的算法，也必須完美。

第二種：因為long[]數組中肯定存在許多的0，這些0毫無意義，其實隻要我們知道這些資料那些位置是0就好。這種就是對0的壓縮。

本人上述的兩種方式，都能快速知道随機某個位置是否是0（都是是通過二分法），隻是比數組的直接索引慢了一點。運算時間還可以接受。

個人認為一個“與”、“或”運算的事件最好不能超過100us。一般客戶等個1s就算長的，1s除以100us等于1W，說明最多可以有1W次與操作，也就是1W個樹節點，而1W個節點是大資料量展示一頁顯示差不多的量。

位圖運算的難點根本在于位圖的資料結構和計算方法。

本來想用B+樹實作壓縮的，後來發現效率有點低（雖然壓縮度最大），就放棄了。可能是我掌握的不太好的原因吧，有機會肯定要重新試一下。

說了這麼多廢話的，本來想放源碼的，但是因為商業機密（即使這些代碼都是本人寫的），不得不、、、

感興趣的、有不明白的可以私信M我