基于哈希算法的增強(qiáng)編碼位圖數(shù)據(jù)方體索引的研究與實(shí)現(xiàn)

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

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

中圖分類號(hào)：TP391.3；TP181

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

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

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

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

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

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

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

2.1 設(shè)計(jì)哈希函數(shù)

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

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

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

2.3 處理哈希碰撞問題

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

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

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

2.4 生成位圖編碼映射表

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

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

圖1 基于哈希的增強(qiáng)編碼位圖索引

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

2.5 查詢操作

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

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

3 存儲(chǔ)空間和查詢性能分析

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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