摘 要：隨著信息技術的蓬勃發(fā)展，信息技術應用領域的數(shù)據(jù)量也越來越大，數(shù)據(jù)倉庫的運用也越來越廣泛和普遍，特別是在大數(shù)據(jù)時代，隨著數(shù)據(jù)量的增加，數(shù)據(jù)倉庫管理的數(shù)據(jù)也越來越多，數(shù)據(jù)方體的數(shù)據(jù)量也越來越大，因此也給數(shù)據(jù)方體的存儲和查詢帶來了巨大的挑戰(zhàn)，怎樣能夠支持對大型數(shù)據(jù)方體的快速查詢，又能減少存儲空間，在聯(lián)機分析處理系統(tǒng)將是非常關鍵的一環(huán)，通過基于哈希算法的增強編碼位圖索引技術能夠有效地減少存儲空間并且提高查詢效率。

關鍵詞：數(shù)據(jù)方體；哈希；增強編碼位圖索引

中圖分類號：TP391.3；TP181

隨著信息技術的高速發(fā)展，數(shù)據(jù)量也越來越大，數(shù)據(jù)倉庫管理的數(shù)據(jù)方體的數(shù)據(jù)量也與日俱增，這給數(shù)據(jù)方體的存儲和管理以及查詢，利用都帶來了巨大的挑戰(zhàn)和困難，不但存儲是個問題，而且想要快速地從數(shù)據(jù)倉庫中準確地獲取數(shù)據(jù)也是一大難點。數(shù)據(jù)方體一般采用多維數(shù)組或者關系表的形式來存儲，由于關系表歷史悠久，使用廣泛，各大數(shù)據(jù)庫廠商都支持，并且具有很成熟的模型，經(jīng)受住了時間的考驗，還有一些多維數(shù)組不具有的優(yōu)點比如對海量數(shù)據(jù)的適應能力以及對軟硬件的適應能力等，所以很多時候數(shù)據(jù)方體都以關系表方式存儲數(shù)據(jù)。由于數(shù)據(jù)方體的數(shù)據(jù)量一般都非常大，特別是在大數(shù)據(jù)時代，數(shù)據(jù)方體存儲的數(shù)據(jù)就更大了，因此，當數(shù)據(jù)方體以關系表方式存儲數(shù)據(jù)的時候，為了提高查詢處理性能，快速響應查詢需求，除了對數(shù)據(jù)方體進行一些預處理之外，還必須對數(shù)據(jù)方體建立索引以滿足日益增加的數(shù)據(jù)量和查詢需求，目前，數(shù)據(jù)方體都采用樹索引和位圖索引。

1 現(xiàn)有編碼位圖索引的不足與缺陷

位圖索引有簡單的位圖索引（也稱之為標準的位圖索引）和編碼的位圖索引，簡單位圖索引，實現(xiàn)簡單，而且一目了然，對于基數(shù)較小的列，效果很好，可以節(jié)省空間，簡單位圖索引的大小與列的不同值的個數(shù)成正比，也可以大大降低被掃描數(shù)據(jù)的數(shù)量，索引只需掃描一次，位圖就可以對所有的行通過位操作進行定位，從而大大提高查詢速度。但是對于高基數(shù)的列，簡單的位圖索引不再有效，為此，有人提出了編碼位圖索引，假設某個事實表的產(chǎn)品維具有1000000種不同的商品，如果要在產(chǎn)品維上創(chuàng)建簡單的位圖索引的話，將會產(chǎn)生1000000個位向量，但是如果采用編碼位圖索引的話，只需要[log21000000]=20個位向量，再加上一個映射表。這樣編碼位圖索引相對簡單位圖索引來說，就大大減少了存儲空間。

由于引入了編碼映射表，從而也就減少了位向量的數(shù)量，但是，在很多情況下，并不總是有效，比如產(chǎn)品名屬性，通常名稱很長，產(chǎn)品的種類也很多，比如淘寶的產(chǎn)品種名稱通常有幾十個漢字，品種也上百萬種，以品種數(shù)量100萬為例，編碼映射表將需要幾十M或者上百M的存儲空間，有時甚至比整個位向量的存儲空間還要大，這樣，不但占據(jù)大量的存儲空間，而且查詢效率也很低下，因為如果編碼映射表很大的話，有時候還不得不為編碼映射表建立索引來提高查詢效率，這是二級索引，為編碼映射表建立索引，又額外地增加了存儲空間。

2 基于哈希算法的增強編碼位圖索引實現(xiàn)

本文將使用一種新的基于哈希算法方法來優(yōu)化編碼位圖索引，從而減少存儲空間，并且提高查詢效率。

哈希算法是將任意長度的數(shù)據(jù)值映射為較短的長度，通常為固定位數(shù)的二進制值，這個較短的固定位數(shù)的二進制值稱為哈希值，本方法的基本思路是通過增加1個位向量，使用有限數(shù)量的編碼映射表來提高查詢速度和減少編碼映射表的存儲空間。

2.1 設計哈希函數(shù)

由于產(chǎn)品品種是100萬（以前文提到的淘寶產(chǎn)品數(shù)量和名稱為例），所以，我們至少需要[log21000000]=20個位向量來存儲產(chǎn)品名稱列的索引，前文提到，我們會增加一個二進制位來存儲索引，我們最多會有可能使用21位二進制來存儲該產(chǎn)品名稱列的索引。因此，我們需要設計一個能夠產(chǎn)生20位二進制的哈希函數(shù)，我們稱之為哈希函數(shù)1，同時設計多個能夠產(chǎn)生21位二進制的哈希函數(shù)，我們稱之為哈希函數(shù)2。為什么還要設計多個能夠產(chǎn)生21位二進制的哈希函數(shù)，后面會有更進一步的介紹。

2.2 計算產(chǎn)品哈希值

掃描整個關系表，對每條記錄中的產(chǎn)品名稱用哈希函數(shù)1計算哈希值，將生成的哈希值存到相應位向量里，由于我們使用了21位位向量，所以這個時候最高位為0，其余20位就是用哈希算法1計算出來的哈希值。

2.3 處理哈希碰撞問題

由于哈希函數(shù)總是會有一定的概率出現(xiàn)碰撞問題，也就是說會有一定的概率即使不同的輸入值也會產(chǎn)生相同的二進制結果。事實證明，即使設計很好的哈希算法，也總是會有一定的概率出現(xiàn)碰撞問題，只是出現(xiàn)碰撞的概率不同罷了，哈希算法2就是用來解決碰撞問題的，下面進行更為詳細的描述。

假設對產(chǎn)品y用哈希算法1來計算哈希值，碰巧的是，對y進行計算出來的哈希值與之前某個產(chǎn)品x計算的哈希值發(fā)生了碰撞，即二者的哈希值一樣，由于x在前面已經(jīng)計算過，不需要再進行修改，所以我們這個時候從哈希算法2中取出一個算法來對y產(chǎn)品來重新進行哈希計算，由于哈希算法2計算出來的結果是21位二進制值，而計算x使用的是哈希算法1，生成的哈希值是20位的，因此哈希算法2計算出來的哈希值一定不會與x的哈希值相同，這就解決了碰撞問題。

由于每一個哈希算法都有可能產(chǎn)生碰撞問題，同樣，用同一個哈希算法2計算出來的哈希值也有可能會產(chǎn)生碰撞問題，當遇到產(chǎn)品z計算出來的哈希值與y產(chǎn)生碰撞的時候，需要使用哈希算法2中的另一個哈希算法來產(chǎn)生哈希值以避免碰撞。由于一個設計良好的哈希算法盡管有一定的概率會產(chǎn)生碰撞問題，但往往概率很小，對于一個產(chǎn)生20位，21位二進制這樣的哈希算法，其重復率一般為幾十萬分之一，故哈希算法2并不需要太多函數(shù)，對于100萬產(chǎn)品級別來說，只需要兩到三個哈希算法2對應的哈希函數(shù)。

2.4 生成位圖編碼映射表

當遇到哈希碰撞的時候，由于為了解決碰撞沖突，使用了哈希算法2中的一個或者多個哈希函數(shù)，當我們在進行查詢操作的時候，不知道使用了哪一個哈希函數(shù)來計算產(chǎn)生碰撞的產(chǎn)品，因此我們需要將哈希算法2中計算出來的哈希值和對應的產(chǎn)品名稱在位圖編碼映射表中記錄下來，供查詢時使用。

運用該方式，對關系表中所有的記錄進行哈希計算，最后，基于哈希算法的編碼位圖索引和編碼映射表就建立完成，如圖1所示。

圖1 基于哈希的增強編碼位圖索引

從示意圖1，可以看出，當使用哈希算法1對產(chǎn)品g進行計算的時候，發(fā)生了碰撞，因此使用哈希算法2中的一個哈希函數(shù)進行計算，產(chǎn)生一個21位二進制的哈希函數(shù)，并將之記錄在編碼映射表中。按照這種方式，處理所有的產(chǎn)品名稱，由于產(chǎn)生20位二進制哈希函數(shù)發(fā)生碰撞的幾率大約為幾十萬分之一，所以，最后形成的編碼映射表非常小，對于百萬級來說，編碼映射表中只有十幾條記錄。

2.5 查詢操作

當我們在對產(chǎn)品關鍵字進行查詢的時候，仍然要用到哈希算法1的函數(shù)，但是不用再使用哈希算法2中的哈希函數(shù)了，哈希算法2中的一系列哈希函數(shù)，僅僅在構造索引的時候需要用到，比如我們要查詢產(chǎn)品x的記錄，首先在編碼映射表中進行定位，確認產(chǎn)品x是否在編碼映射表中，如果產(chǎn)品x不在編碼映射表中，表明x在計算哈希值的時候，沒有與之前的產(chǎn)品的哈希值重復，故只需要對x使用哈希算法1來計算其哈希值，然后通過這個哈希值在編碼索引表中進行定位，從而快速搜尋滿足條件的記錄。

但是如果x能夠在編碼映射表中找到，說明在使用哈希算法1計算x的哈希值的時候，與之前的某個產(chǎn)品計算出來的哈希值重復了，這個時候，只需要從編碼映射表中取出x對應的哈希值，然后利用這個哈希值去索引表中查詢滿足條件的記錄，由于索引編碼表非常小，查詢產(chǎn)品x是否在索引編碼中以及從索引編碼表中取出對應的哈希值，都是非常迅速的。

3 存儲空間和查詢性能分析

本方法的實現(xiàn)可以在Windows和Linux/Unix平臺上運行，運行測試的機器為Windows PC機，硬件配置為4核處理器，16G內存，數(shù)據(jù)方體的測試產(chǎn)品名稱數(shù)量為100萬，基于該產(chǎn)品的記錄數(shù)為1000萬，針對這一產(chǎn)品維建立基于哈希算法的增強位圖索引，在存儲空間和查詢性能上與編碼位圖索引進行了比較，在存儲空間上盡管增加了一位來處理哈希重復問題，但編碼映射表卻大大節(jié)省了空間，總的說來節(jié)省了約50M，幾乎節(jié)省了整個編碼映射表。由于在一個只有十幾條記錄上查詢哈希值，因此在查詢性能上也有大幅提高，做到了既節(jié)省空間，有提高了查詢效率。但是要做到既節(jié)省空間又要提高索引查詢效率，很關鍵的一點是要提前設計好產(chǎn)生不同位數(shù)的哈希函數(shù)，并且要降低這些哈希函數(shù)的碰撞概率。

4 結束語

因此，基于該哈希算法的增強的位圖編碼索引方法，在數(shù)據(jù)方體中的使用，不但可以大大減少索引的存儲空間，而且也能大大地優(yōu)化，提高了查詢性能。該方法也為研究數(shù)據(jù)方體索引技術的相關人員提供了一個新的思路和一定的參考價值。

參考文獻：

[1]王珊，李翠平，李盛恩.數(shù)據(jù)倉庫與數(shù)據(jù)分析教程[M].北京：高等教育出版社，2012.

[2]郭偉斌，陳東文.數(shù)據(jù)庫索引技術的研究與應用[J].電腦開發(fā)與應用，2007（09）.

[3]李曉東，陳忱.基于多維鏈表的數(shù)據(jù)庫索引技術研究與實現(xiàn)[J].計算機工程與應用，2004（22）.

作者簡介：張海洋（1975-），男，四川人，本科，首席軟件工程師，研究方向：計算機數(shù)據(jù)保護、存儲備份、大數(shù)據(jù)、數(shù)據(jù)庫電話。

作者單位：冠群電腦（中國）有限公司，北京 100022