基于March算法的網(wǎng)絡(luò)多維數(shù)據(jù)優(yōu)化存儲方法

胡茂美

(合肥濱湖職業(yè)技術(shù)學(xué)院 機(jī)電與汽車工程學(xué)院，安徽 合肥 230601)

數(shù)據(jù)庫技術(shù)的迅速發(fā)展，導(dǎo)致各行各業(yè)積攢過多的數(shù)據(jù)量，信息存儲在企業(yè)發(fā)展過程中具有重要意義.數(shù)據(jù)庫的主要應(yīng)用范圍是決策與分析，為這兩個應(yīng)用提供優(yōu)越的工作平臺[1]，數(shù)據(jù)庫內(nèi)數(shù)據(jù)存儲形式均是多維的.提升在數(shù)據(jù)庫內(nèi)搜索有價值信息的效率，可幫助企業(yè)快速了解其自身情況[2].OLAP技術(shù)為用戶提供了一種決策支持的有效方法[3]，該技術(shù)可提升用戶查詢數(shù)據(jù)速度，方便用戶使用，操作簡單.多維數(shù)據(jù)集屬于OLAP數(shù)據(jù)查詢的核心，通過Data Cube多維分析實現(xiàn)OLAP查詢.在Data Cube內(nèi)包含數(shù)據(jù)的全部細(xì)節(jié)信息，也包含不同粒度中的聚集值.聚集記錄會浪費存儲空間，延長計算時間[4]，降低OLAP分析效率，因此提升多維數(shù)據(jù)存儲效率是目前數(shù)據(jù)庫的主要研究方向.趙亞楠等人針對小文件存儲問題，提出大數(shù)據(jù)分布式存儲方法，提升存儲效率[5]；陳波等人針對大量數(shù)據(jù)管理方式存在的缺陷，提出GeoSOT剖分網(wǎng)格的數(shù)據(jù)存儲方法，集中存儲大量數(shù)據(jù)，提升存儲效率[6].這兩種方法的缺點是未考慮多維數(shù)據(jù)存儲空間較大問題，嚴(yán)重浪費存儲空間.March算法為存儲器中常用的功能測試與地址解碼等測試向量，具備較優(yōu)的故障與存儲時間測量性能[7].為此研究基于March算法的網(wǎng)絡(luò)多維數(shù)據(jù)優(yōu)化存儲方法，節(jié)約存儲空間，提升存儲效率.

1 基于March算法的網(wǎng)絡(luò)多維數(shù)據(jù)優(yōu)化存儲方法

1.1 網(wǎng)絡(luò)多維數(shù)據(jù)存儲結(jié)構(gòu)

網(wǎng)絡(luò)多維數(shù)據(jù)的組織方式共有兩種，分別是維數(shù)據(jù)與度量數(shù)據(jù)組織，前者通過多維數(shù)據(jù)結(jié)構(gòu)與存儲維的結(jié)構(gòu)信息完成數(shù)據(jù)組織[8]，后者通過加快聚集查詢效率完成數(shù)據(jù)組織.

1.1.1 存儲組織多維數(shù)據(jù)

組織維數(shù)據(jù)的步驟如下：

步驟1：存儲組織數(shù)據(jù)特征提??；

步驟2：映射特征點數(shù)據(jù)，使其變成多維數(shù)據(jù)組的坐標(biāo)值.

維層次的偏序存在一定關(guān)系，該關(guān)系的表達(dá)形式是格，通過這些格構(gòu)建一個無環(huán)圖，該圖具備方向性，這就說明能夠由鄰接表描繪并組織維的層次結(jié)構(gòu)及成員間的關(guān)系[9].建立一個在全部層次以上的層次all，以all為起始點，建立一棵樹，all代表其根節(jié)點，all的孩子節(jié)點為其下層的全部成員.組織維成員可完成多維數(shù)據(jù)處理技術(shù)的Roll up與Drill down操作[10].然后，需對其實施編碼，具體步驟如下：

步驟1：整數(shù)編碼，在網(wǎng)絡(luò)多維數(shù)據(jù)組內(nèi)，各維中的坐標(biāo)均是整數(shù)，因此需將維護(hù)成員變更為整數(shù).令多維數(shù)據(jù)集Gα的一個層次h中的成員是p1,…,pn，整數(shù)編碼的步驟為：

a.建立映射函數(shù)f；

b.針對h中的成員p1的f是f(p1)=0；

c.如果pα,1≤α≤n與pβ,1≤β≤n屬于鄰近，且pα≤pβ，那么f(pβ)=f(pα)+1.

令多維數(shù)據(jù)空間是(G1,G2,…,Gn,F1,F2,…,Fp)，每個維的尺寸一致，由Gα表示，利用上述操作完成整數(shù)編碼，編碼后的多維數(shù)組是(g1,g2,…,gn,f1,f2,…,fp)，那么多維數(shù)據(jù)位置是pos=(…((g1*G2+g2)*G3+…+gn-2)*Gn-1+gn-1)*Gn+gn.

1.1.2 存儲組織度量數(shù)據(jù)

令(G1,G2,…,Gn,F1,F2,…,Fp)，多維數(shù)據(jù)集Gα組建的數(shù)組是G1×G2×…×Gn，順序存儲過程中，依據(jù)G1,G2,…,Gn順序排列度量元素的位置[12].

1.2 March算法

March算法屬于常用的存儲器測試方法，即對存儲器內(nèi)的存儲方法展開測試，優(yōu)化網(wǎng)絡(luò)多維數(shù)據(jù)存儲方法.該算法存在高故障覆蓋率與低時間復(fù)雜度的優(yōu)勢.測試步驟如下：

步驟1：在全部存儲器內(nèi)寫入所有是零的背景；

步驟2：讀取首個存儲單元，其正確讀取結(jié)果是0；

步驟3：將一個1錄入首個存儲單元，隨后讀取該單元，正確讀取結(jié)果是1；

步驟4：同理，剩余存儲單元執(zhí)行步驟2與3，以全部存儲單元完成操作為止[13]；

步驟5：所有單元的內(nèi)容都是1，代表全部單元的背景均是1；

步驟6：讀取首個存儲單元[14]，正確讀取結(jié)果是1；

步驟7：將一個0錄入首個存儲單元，隨后讀取該單元，正確讀取結(jié)果是0；

步驟8：同理，剩余存儲單元執(zhí)行步驟6與7，以全部存儲單元完成操作為止.

步驟6能夠執(zhí)行反操作，代表能夠以最后一個單元為起始點，按照順序執(zhí)行讀取操作[15]，結(jié)束條件是首個單元完成操作，以公式的形式表達(dá)如下：

(1)

其中，第i行第j列的存儲單元是Bij；讀取Bij的操作是RBij；將1錄入Bij內(nèi)的操作是W(1)Bij；將0錄入內(nèi)的操作是W(0)Bij；所有Bij的集合是?ij；集合?ij中的總和是∑；公式中全部操作過程中的分隔符是“，”；背景0與1是下標(biāo)0與1.

利用公式(1)能夠計算獲取存儲方法的復(fù)雜度是2(1+1)N+N=5N，N代表單元數(shù)量.測試的操作次數(shù)由5N描繪，5N乘上完成各操作的時間就是總測試時間.5N的大小與測試時間成正比.

通過增加March算法的測試向量，加強其測試效率與故障覆蓋率，增加后的數(shù)據(jù)叫作數(shù)據(jù)背景(Data Back-ground).在March算法內(nèi)讀取與錄入數(shù)據(jù)是1與0的情況下，便需將正向與逆向的數(shù)據(jù)背景用于相應(yīng)的存儲方法中.

2 實驗分析

首先構(gòu)建一個P2P網(wǎng)絡(luò)，在該網(wǎng)絡(luò)內(nèi)各塑造一個Web服務(wù)器與Tracker Server服務(wù)器，剩余節(jié)點是OLAP網(wǎng)絡(luò)節(jié)點，在該網(wǎng)絡(luò)節(jié)點內(nèi)建立一個虛擬的多維數(shù)據(jù)庫，該數(shù)據(jù)庫內(nèi)共包含50 000個文件夾，利用方法對該數(shù)據(jù)庫內(nèi)的多維數(shù)據(jù)實施優(yōu)化存儲，驗證本文方法的有效性.

選取大數(shù)據(jù)分布式存儲方法[5]，GeoSOT剖分網(wǎng)格數(shù)據(jù)存儲方法[6]作為本文的對比方法，測試本文方法在優(yōu)化前后存儲不同文件夾數(shù)量時的各項性能，共實施5次實驗，記錄每次實驗的優(yōu)化前后的數(shù)據(jù)存儲時間，取5次記錄時間的均值，測試結(jié)果如表1所示.

表1 3種方法的各項性能對比結(jié)果

根據(jù)表1可知，在存儲不同文件夾數(shù)量時，本文方法的系統(tǒng)響應(yīng)時間在文件夾數(shù)量較少時優(yōu)勢不明顯，當(dāng)文件夾數(shù)量超過20000時，本文方法的系統(tǒng)響應(yīng)時間顯著低于其余兩種方法；其余兩種方法在存儲多維數(shù)據(jù)時所占內(nèi)存較大，本文方法存儲多維數(shù)據(jù)時的占用內(nèi)存較小，原因是本文方法中包含壓縮存儲過程，有效減小內(nèi)存占用空間；在文件夾數(shù)量較少時，其余兩種方法存儲多維數(shù)據(jù)時的導(dǎo)入與導(dǎo)出響應(yīng)時間較短，與本文方法的多維數(shù)據(jù)導(dǎo)入與導(dǎo)出響應(yīng)時間差距不大，當(dāng)文件夾數(shù)量較多時，其余兩種方法的多維數(shù)據(jù)導(dǎo)入與導(dǎo)出響應(yīng)時間明顯增長，響應(yīng)速度顯著下降，本文方法的多維數(shù)據(jù)導(dǎo)入與導(dǎo)出響應(yīng)時間無明顯變化，僅有小幅度增長現(xiàn)象，響應(yīng)速度較快.實驗證明：在存儲不同文件夾數(shù)量時，本文方法的響應(yīng)速度較快即存儲效率高，內(nèi)存占用空間最小，具備較優(yōu)的數(shù)據(jù)存儲性能.

測試3種方法分別存儲文件夾數(shù)量為5 000與50 000個時的數(shù)據(jù)存儲信噪比，測試在不同壓縮比時3種方法在數(shù)據(jù)存儲過程中的信噪比，測試結(jié)果如圖1與圖2所示.

根據(jù)圖1與圖2可知，文件夾數(shù)量為5 000時，壓縮比逐漸提升，本文方法在存儲多維數(shù)據(jù)時的信噪比無明顯變化，平均信噪比為94.5 dB；其余兩種方法的信噪比前期下降幅度較小，當(dāng)壓縮比超過50后，其信噪比下降幅度均較大，平均信噪比分別為67.9 dB與69.9 dB；文件數(shù)量為50 000時，壓縮比逐漸提升，本文方法在存儲多維數(shù)據(jù)時的信噪比出現(xiàn)小幅度下降趨勢，平均信噪比為85.3 dB；其余兩種方法的信噪比下降幅度較大，當(dāng)壓縮比為80時，兩種方法均出現(xiàn)數(shù)據(jù)存儲失真情況，平均信噪比為38.1 dB與39.3 dB.

壓縮比圖1 文件夾數(shù)量為5 000時的信噪比

壓縮比圖2 文件夾數(shù)量為50 000時的信噪比

實驗證明：文件夾數(shù)量較大時，本文方法在存儲多維數(shù)據(jù)過程中的信噪比有所降低，但依舊高于其余兩種方法，在不同壓縮比時，本文方法在數(shù)據(jù)存儲過程中的信噪比最高.

文件夾數(shù)量為50 000時，3種方法的各項性能差距最為明顯，因此測試3種方法在存儲文件夾數(shù)量為50 000時且不同稀疏度情況下的數(shù)據(jù)存儲信噪比，數(shù)據(jù)稀疏度越高，所需存儲的字?jǐn)?shù)越少，在不同稀疏度時的數(shù)據(jù)存儲過程中的信噪比測試結(jié)果如圖3所示.

稀疏度圖3 不同稀疏度時的信噪比測試結(jié)果

根據(jù)圖3可知，隨著稀疏度的不斷提升，3種方法數(shù)據(jù)存儲過程中的信噪比均有所增長，其余兩種方法的信噪比增長幅度較小，當(dāng)稀疏度達(dá)到10時，大數(shù)據(jù)分布式存儲方法的信噪比不再發(fā)生改變，穩(wěn)定在25 dB左右；當(dāng)稀疏度達(dá)到12時，GeoSOT剖分網(wǎng)格數(shù)據(jù)存儲方法的信噪比不再發(fā)生改變，穩(wěn)定在30 dB左右；本文方法的信噪比在前期增長速度較為緩慢，當(dāng)稀疏度超過8時，信噪比增長速度較快.實驗證明：在不同稀疏度時，本文方法的多維數(shù)據(jù)存儲性能最優(yōu).

3 結(jié) 論

數(shù)據(jù)庫在各大領(lǐng)域的廣泛應(yīng)用，導(dǎo)致各領(lǐng)域的網(wǎng)絡(luò)多維數(shù)據(jù)累積量顯著增長，造成傳統(tǒng)的多維數(shù)據(jù)存儲方法不足以滿足用戶對數(shù)據(jù)庫的高要求.因此提出基于March算法的網(wǎng)絡(luò)多維數(shù)據(jù)優(yōu)化存儲方法，提升數(shù)據(jù)優(yōu)化存儲性能，更好地符合MOLAP快速性的要求.