OLAP聚集計(jì)算中的維存儲(chǔ)技術(shù)

宋愛(ài)波 張若儒 趙經(jīng)華 何戰(zhàn)國(guó)

(東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，南京211189)

OLAP是一種針對(duì)數(shù)據(jù)倉(cāng)庫(kù)中的數(shù)據(jù)進(jìn)行聯(lián) 機(jī)訪問(wèn)和分析的主要技術(shù)［1］.然而，傳統(tǒng)DBMS的行存儲(chǔ)結(jié)構(gòu)嚴(yán)重制約了OLAP聚集計(jì)算效率.按行存儲(chǔ)和讀取數(shù)據(jù)適合以寫(xiě)操作為主的事務(wù)處理，不適于以讀操作為主的OLAP.早期的列存儲(chǔ)模型DSM 是由 Copeland等［2］在1985年提出的.DSM將每個(gè)關(guān)系按列進(jìn)行垂直劃分，將每個(gè)列值以(元組ID，列值)對(duì)形式進(jìn)行存儲(chǔ).在列存儲(chǔ)中，只有被查詢的列才會(huì)讀入內(nèi)存，而行存儲(chǔ)需要讀入所有列，因此列存儲(chǔ)比行存儲(chǔ)具有更高的數(shù)據(jù)查詢效率.此外，列存儲(chǔ)還具有更高的數(shù)據(jù)壓縮比.如今，商業(yè) 列 數(shù) 據(jù) 庫(kù) 有 SenSage［3］，Sybase IQ［4］，Big-Table［5］等，開(kāi) 源 列 數(shù) 據(jù) 庫(kù) 有 MonetDB［6］，C-store［7］，HBase［8］等.根據(jù) Feinberg 等［9］在 2011年1月關(guān)于數(shù)據(jù)倉(cāng)庫(kù)的分析報(bào)告，與傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)相比，列數(shù)據(jù)庫(kù)在數(shù)據(jù)分析(包括OLAP等)方面表現(xiàn)出卓越的性能.

目前，Sybase IQ還不能很好地支持高維OLAP數(shù)據(jù)的維層次特性，可擴(kuò)展性較差.Zou等［10］建立在HBase上的索引表CCindex能較好地支持范圍查詢，但沒(méi)有考慮數(shù)據(jù)的層次性.文獻(xiàn)［11］提出的維層次編碼能夠支持OLAP的多維層次性，但是其B+樹(shù)的傳統(tǒng)構(gòu)建方法產(chǎn)生的開(kāi)銷(xiāo)太大，且仍采用行存儲(chǔ)結(jié)構(gòu)，讀取大規(guī)模列數(shù)據(jù)時(shí)效率不高.

HBase是BigTable的開(kāi)源實(shí)現(xiàn)，以HDFS(Hadoop分布式文件系統(tǒng))為底層存儲(chǔ)，是一個(gè)提供高可靠性、高性能、列存儲(chǔ)、實(shí)時(shí)讀寫(xiě)的大規(guī)模分布式數(shù)據(jù)庫(kù)系統(tǒng).在HBase中，列可動(dòng)態(tài)擴(kuò)展，能較好地支持OLAP數(shù)據(jù)的維層次屬性;它還能利用Hadoop系統(tǒng)的MapReduce框架對(duì)列數(shù)據(jù)進(jìn)行高效并行計(jì)算.鑒于此，本文提出了一種基于 HBase的OLAP維存儲(chǔ)模型，采用自底向上的方法構(gòu)建維層次編碼B+樹(shù)索引，避免了利用傳統(tǒng)的自頂向下方法進(jìn)行分裂操作所造成的巨大開(kāi)銷(xiāo)，因而可以快速獲取任意維層次的OLAP數(shù)據(jù)，更好地支持上層OLAP的聚集運(yùn)算.

1 維存儲(chǔ)

本節(jié)介紹了OLAP多維數(shù)據(jù)模型和HBase存儲(chǔ)機(jī)制，給出OLAP維存儲(chǔ)模型在HBase上的實(shí)現(xiàn)，為生成基于維層次編碼的B+樹(shù)索引提供支持.

1.1 OLAP多維數(shù)據(jù)模型

OLAP多維數(shù)據(jù)在數(shù)據(jù)倉(cāng)庫(kù)中一般以星型模式組織，即將若干個(gè)維表以事實(shí)表為中心聯(lián)系起來(lái)(見(jiàn)圖1)［12］.為構(gòu)建這一星型模型，首先要確定度量屬性，也就是人們對(duì)其值感興趣的屬性，余下的屬性則作為維屬性.圖1中，將銷(xiāo)售數(shù)量(SaleNum)和總量(Quantity)這2個(gè)屬性作為度量屬性.維用于表示人們觀察度量值的特定角度;比如地區(qū)維，即可以根據(jù)地區(qū)來(lái)統(tǒng)計(jì)某個(gè)產(chǎn)品的數(shù)量.

圖1 星型模式

維通常具有層次性.若維中屬性之間可以進(jìn)行度量比較，則將這種屬性稱(chēng)作維的層次.如時(shí)間維中有年、月、日3個(gè)層次，日的信息可以通過(guò)上卷操作轉(zhuǎn)換為月或年的信息，年的信息可以通過(guò)下鉆操作轉(zhuǎn)換為月或日的信息.

1.2 HBase存儲(chǔ)機(jī)制

HBase在概念上以表的形式存儲(chǔ)數(shù)據(jù)(見(jiàn)表1)，但在物理上則按照列族進(jìn)行存儲(chǔ)(見(jiàn)表2和表3).表由行和列組成，所有列被劃分為若干個(gè)列族.通過(guò)行和列確定的一個(gè)存貯單元稱(chēng)為Cell.每個(gè)Cell都可以保存多個(gè)版本的數(shù)據(jù)，通過(guò)時(shí)間戳來(lái)索引.行關(guān)鍵字是用來(lái)檢索記錄的主鍵，通過(guò)主鍵或主鍵加時(shí)間戳可以定位一行數(shù)據(jù).

一張表先被橫向劃分成多塊，每塊稱(chēng)為一個(gè)Region，數(shù)據(jù)按照行主鍵的字典序排序存儲(chǔ);在Region中數(shù)據(jù)再按列族劃分，存儲(chǔ)在HDFS上.

表1 HBase數(shù)據(jù)存儲(chǔ)的概念視圖

表2 列族A存儲(chǔ)的物理視圖

表3 列族B存儲(chǔ)的物理視圖

1.3 基于HBase的OLAP維存儲(chǔ)模型

OLAP維存儲(chǔ)模型以(維層次編碼，度量值)對(duì)形式重新組織OLAP多維數(shù)據(jù)，用于支持基于維層次編碼的B+樹(shù)索引，使其根據(jù)維層次編碼一次性查找到相應(yīng)度量值，避免每次查詢都要進(jìn)行維表與事實(shí)表的連接操作.維值經(jīng)過(guò)編碼后，其占用的存儲(chǔ)空間大大減少.

在HBase中，首先根據(jù)星型模式分別存儲(chǔ)事實(shí)表和維表.存儲(chǔ)維表時(shí)，每個(gè)維的所有屬性形成一個(gè)列族，每個(gè)屬性是一個(gè)列.將事實(shí)表中的維屬性集和度量屬性集定義為不同列族.以圖1中的多維數(shù)據(jù)模型為例，其在HBase中的事實(shí)表見(jiàn)表4，時(shí)間維表見(jiàn)表5，其他維表類(lèi)似于時(shí)間維.

表4 HBase中事實(shí)表存儲(chǔ)的概念視圖

表5 HBase中時(shí)間維表存儲(chǔ)的概念視圖

定義好各表的模式后，對(duì)OLAP多維數(shù)據(jù)中具有層次性的維進(jìn)行維層次編碼.

定義1維層次樹(shù)可以形式化定義為DTree=(V，E).其中，V為維中各個(gè)層次的所有成員的有序集;E為各個(gè)成員之間的層次關(guān)系，即維層次樹(shù)中的邊連接關(guān)系.如時(shí)間維從上往下的層次為(年，月，日)，其維層次樹(shù)如圖2所示.

圖2 時(shí)間維的維層次樹(shù)

定義2Pij(j∈1，2，…，v)為維表 Di中的第 j層屬性集(j值越大，其在層次樹(shù)中的層次越低)，其值域?yàn)?/p>

式中，dij為維表Di中的第j層屬性;k為第j層不同屬性的個(gè)數(shù).

定義3dom(Pij)中各成員的二進(jìn)制編碼為BPij，其值域?yàn)?/p>

式中，w為Pij中各屬性成員的二進(jìn)制編碼位數(shù)，其最小取值為α(log2k)，α為向上取整運(yùn)算.如圖2所示，在時(shí)間維中，年層次有3個(gè)不同屬性值，則年層次中k=3，月層次和日層次中k分別為12和31.為了應(yīng)用的擴(kuò)展，為某些成員不確定的層次(如年層次)預(yù)留一些編碼位數(shù)，即取 w＞α(log2k);而對(duì)于成員中確定的層次(如月層次上只有12個(gè)月)，則w=α(log212)=4.對(duì)一個(gè)維的每個(gè)層次生成一個(gè)二進(jìn)制編碼表.時(shí)間維的維層次屬性二進(jìn)制編碼表見(jiàn)表6.

表6 時(shí)間維的維層次屬性二進(jìn)制編碼表

定義4維表Di中，主鍵為Ks(長(zhǎng)度為L(zhǎng)Ks)、時(shí)間戳為T(mén)t(長(zhǎng)度為L(zhǎng)Tt)的維值的維層次編碼可表示為

該維層次編碼是由各層次的二進(jìn)制編碼按層次由高到低組合起來(lái)，再加上每個(gè)事實(shí)表記錄的主鍵和時(shí)間戳所構(gòu)成的.主鍵和時(shí)間戳組合的唯一性，確保了維層次編碼的唯一性.

傳統(tǒng)的OLAP聚集計(jì)算難以避免維表與事實(shí)表間的多次連接操作，是造成其效率低下的原因之一.為解決該問(wèn)題，對(duì)于每個(gè)維表，通過(guò)一次與事實(shí)表的連接操作，預(yù)先將維值與度量值關(guān)聯(lián)起來(lái)，以(維層次編碼，度量值)對(duì)的形式保存在HBase中，由此便可通過(guò)層次編碼的B+樹(shù)索引直接查詢到度量值，大大提高了查詢效率.以表5為例，根據(jù)表6進(jìn)行編碼，同時(shí)將表4和表5在時(shí)間ID上進(jìn)行連接，獲取事實(shí)表記錄的主鍵和度量值，便可以得到該維的維層次編碼-度量表(見(jiàn)表7).

表7 時(shí)間維的維層次編碼-度量表

維存儲(chǔ)模型利用了HBase能動(dòng)態(tài)地在列族中增刪和更新列的特性，有利于對(duì)多維數(shù)據(jù)模型的擴(kuò)展.要增加或刪除一個(gè)維，只需在HBase中增加或刪除一個(gè)維表即可;對(duì)某個(gè)維中的屬性進(jìn)行增刪或更新時(shí)，僅需對(duì)HBase中相應(yīng)維表的對(duì)應(yīng)列進(jìn)行操作.這種維存儲(chǔ)模型可以方便地動(dòng)態(tài)更新維和維中屬性，因而能夠適應(yīng)多種應(yīng)用及擴(kuò)展.

2 基于維層次編碼的B+樹(shù)索引

索引管理是數(shù)據(jù)訪問(wèn)管理的重要內(nèi)容.索引是對(duì)數(shù)據(jù)庫(kù)表中一個(gè)或多個(gè)列的值進(jìn)行排序的結(jié)構(gòu).在經(jīng)常查詢的數(shù)據(jù)上建立索引，是提高查詢效率最為簡(jiǎn)單有效的方法.B+樹(shù)是在數(shù)據(jù)庫(kù)中索引普遍應(yīng)用的數(shù)據(jù)結(jié)構(gòu)，具有高效、靈活等優(yōu)點(diǎn).

2.1 B+樹(shù)的定義

B+樹(shù)索引是一顆分層的平衡樹(shù)，樹(shù)中的節(jié)點(diǎn)分為2種類(lèi)型:葉子節(jié)點(diǎn)和中間節(jié)點(diǎn).

定義5一棵m階B+樹(shù)或者為空，或者滿足下列性質(zhì):

1)中間節(jié)點(diǎn)最多有n棵子樹(shù)，且結(jié)構(gòu)為s，A0，(Z1，A1)，(Z2，A2)，…，(Zs，As).其中，Al為子樹(shù)指針，0≤l≤s≤n;Zl為關(guān)鍵字，且 Zl＜ Zl+1.所有中間節(jié)點(diǎn)的關(guān)鍵字互不相同.

2)子樹(shù)Al中的所有關(guān)鍵字都大于等于Zl并小于Zl+1.子樹(shù)As中的所有關(guān)鍵字都大于等于Zs，子樹(shù)A0中的所有關(guān)鍵字都小于Z1.

3)根節(jié)點(diǎn)至少有2棵子樹(shù)，其他中間節(jié)點(diǎn)至少有α(n/2)棵子樹(shù).

4)所有葉子節(jié)點(diǎn)都處于同一個(gè)層次，包含了全部關(guān)鍵字以及相應(yīng)的數(shù)據(jù)或數(shù)據(jù)地址.當(dāng)其包含數(shù)據(jù)時(shí)，稱(chēng)之為聚簇索引;當(dāng)其包含數(shù)據(jù)地址時(shí)，稱(chēng)之為非聚簇索引.

在聚簇索引中，數(shù)據(jù)的索引順序與物理順序相同;在非聚簇索引中，數(shù)據(jù)的索引順序與物理順序沒(méi)有必然聯(lián)系.通常，聚簇索引有利于范圍查詢，而非聚簇索引有利于單行查詢.

深秋的山野飄溢著濃郁的花香，這東泉嶺上像是一個(gè)天然的分界線，上面似乎永遠(yuǎn)的云霧繚繞，站在這里總會(huì)有云朵飄逸過(guò)來(lái)，下面則草木郁郁蔥蔥，直抵山下的村子，充滿著人間的煙火味。風(fēng)影的臉上帶有幾分落寞，這大千世界在他眼里成了一座迷宮，不管怎么走都走不到盡頭，找不到出口。這個(gè)世界要說(shuō)簡(jiǎn)單其實(shí)非常的簡(jiǎn)單，可要是復(fù)雜起來(lái)，那簡(jiǎn)直就是一個(gè)蛛網(wǎng)密布永遠(yuǎn)糾結(jié)不清的陰陽(yáng)八卦圖。風(fēng)影感到了從未有過(guò)的迷茫，這紅塵世界離他越來(lái)越遠(yuǎn)，他的神經(jīng)末梢只能感覺(jué)到一點(diǎn)點(diǎn)輕微的顫動(dòng)。

2.2 B+樹(shù)索引的創(chuàng)建

考慮在OLAP維存儲(chǔ)中，通常只是按照維值查找數(shù)據(jù)，而且聚集計(jì)算通常要進(jìn)行大規(guī)模的范圍查詢，因此本文采用B+樹(shù)的聚簇索引.在B+樹(shù)的生成上，采用自底向上構(gòu)建的方法，避免了傳統(tǒng)的自頂向下插入法所造成的巨大節(jié)點(diǎn)分裂開(kāi)銷(xiāo).

在建立B+樹(shù)時(shí)，關(guān)鍵字是維層次編碼，數(shù)據(jù)是度量值.自底向上構(gòu)造B+樹(shù)需要滿足以下2個(gè)條件:①查找鍵值已排序;②查找鍵不含重復(fù)值.在構(gòu)建的維層次編碼-度量表中，維層次編碼的有序性和唯一性滿足這2個(gè)條件.

葉子節(jié)點(diǎn)所在層次被稱(chēng)為第0層，葉子節(jié)點(diǎn)以上層數(shù)依次遞增.B+樹(shù)的建立是一個(gè)自底向上反復(fù)迭代的過(guò)程，共有3層循環(huán).內(nèi)層循環(huán)用于向新申請(qǐng)的節(jié)點(diǎn)塊中填充關(guān)鍵字;第2層循環(huán)用于申請(qǐng)一個(gè)新的節(jié)點(diǎn);最外層循環(huán)對(duì)每一層節(jié)點(diǎn)進(jìn)行管理.若在第2層循環(huán)結(jié)束后，只創(chuàng)建了一個(gè)節(jié)點(diǎn)塊，則說(shuō)明該節(jié)點(diǎn)是根節(jié)點(diǎn)，保存根節(jié)點(diǎn)信息后，最外層循環(huán)結(jié)束，B+樹(shù)創(chuàng)建完畢.

2.3 B+樹(shù)索引的查找

基于維層次編碼的B+樹(shù)索引的查找主要包括以下3個(gè)步驟:

①根據(jù)要查找的維值和提供的主鍵(可選)、時(shí)間戳(可選)，生成該維值的維層次編碼C，將C作為查找的關(guān)鍵字.若不提供主鍵或時(shí)間戳，則將C中對(duì)應(yīng)主鍵或時(shí)間戳的編碼置為0，此時(shí)的查找結(jié)果可能會(huì)有多個(gè).如果查詢請(qǐng)求同時(shí)提供了維值、主鍵和時(shí)間戳，則查找結(jié)果最多只有1個(gè).

②執(zhí)行B+樹(shù)的查找算法.首先判斷查找關(guān)鍵字的值是否小于根節(jié)點(diǎn)的第1個(gè)關(guān)鍵字，條件成立則說(shuō)明它比所有值都小，查找失敗;然后從根節(jié)點(diǎn)開(kāi)始，找到符合條件的關(guān)鍵字，根據(jù)其指針找到下一層的節(jié)點(diǎn)，直到在葉子節(jié)點(diǎn)中找到符合條件的第1個(gè)數(shù)據(jù)項(xiàng).若沒(méi)有符合條件的結(jié)果，則查找失敗;若查找成功，則返回?cái)?shù)據(jù)塊號(hào)和第1個(gè)數(shù)據(jù)項(xiàng)的槽號(hào).

③若第2步中查找成功，且查找的關(guān)鍵字中主鍵和(或)時(shí)間戳的編碼為0，則從第2步中獲得的塊首地址和槽號(hào)開(kāi)始進(jìn)行掃描，查找所有除去主鍵和(或)時(shí)間戳部分編碼后與關(guān)鍵字相同的數(shù)據(jù)項(xiàng)，將其作為查詢結(jié)果返回，并記錄數(shù)據(jù)項(xiàng)的個(gè)數(shù).

2.4 B+樹(shù)索引的更新

當(dāng)向數(shù)據(jù)庫(kù)中追加數(shù)據(jù)時(shí)，也會(huì)向B+樹(shù)中追加索引.當(dāng)B+樹(shù)中的節(jié)點(diǎn)塊滿時(shí)，會(huì)發(fā)生分裂.與傳統(tǒng)方法構(gòu)建的B+樹(shù)不同，此時(shí)的分裂操作僅涉及到每一層的最后一個(gè)節(jié)點(diǎn)，且不是將原有節(jié)點(diǎn)分裂，而是在申請(qǐng)到一個(gè)新節(jié)點(diǎn)塊后，直接把新索引項(xiàng)追加到新節(jié)點(diǎn)中.當(dāng)根節(jié)點(diǎn)分裂時(shí)，會(huì)申請(qǐng)2個(gè)新節(jié)點(diǎn)塊，其中一個(gè)作為新的根塊，原來(lái)的根節(jié)點(diǎn)成為普通的節(jié)點(diǎn).

一個(gè)節(jié)點(diǎn)塊能索引多個(gè)數(shù)據(jù)項(xiàng);當(dāng)追加數(shù)據(jù)時(shí)，索引塊分裂的幾率很小.因此，B+樹(shù)的更新比傳統(tǒng)方法構(gòu)建的B+樹(shù)簡(jiǎn)單許多，體現(xiàn)在以下幾個(gè)方面:

1)向數(shù)據(jù)塊中追加數(shù)據(jù)時(shí)，索引信息不一定會(huì)發(fā)生修改.

2)需要修改索引信息時(shí)，只需要提供待追加的維層次編碼和新建數(shù)據(jù)塊的塊號(hào).

3)可以在操作前從根節(jié)點(diǎn)開(kāi)始，依次讀出每一層中最后一個(gè)節(jié)點(diǎn)塊的塊號(hào)，將其保存在緩沖區(qū)中.待需要向上分裂時(shí)，可以重復(fù)調(diào)用此塊號(hào).

3 性能分析

3.1 列存儲(chǔ)和行存儲(chǔ)

在數(shù)據(jù)倉(cāng)庫(kù)環(huán)境中，通常是周期性地裝載大量新數(shù)據(jù)，在此后較長(zhǎng)的一段時(shí)間內(nèi)進(jìn)行大量的實(shí)時(shí)查詢，且查詢主要是對(duì)大量列數(shù)據(jù)的聚合操作.

首先，列存儲(chǔ)能提高查詢所需列數(shù)據(jù)的吞吐量，減少I(mǎi)/O操作.查詢語(yǔ)句中的謂詞是基于列來(lái)定義的，列存儲(chǔ)可以快速鎖定該列數(shù)據(jù)，不會(huì)檢索無(wú)關(guān)列的數(shù)據(jù)，避免了行存儲(chǔ)中大量無(wú)效的磁盤(pán)I/O操作.尤其是在表的列數(shù)較多時(shí)，性能的提升會(huì)更加明顯.例如，一個(gè)表有5×107條記錄，每條記錄占用1 KB，平均每列數(shù)據(jù)占用10 B.在行存儲(chǔ)模式下，對(duì)某列數(shù)據(jù)進(jìn)行聚集操作，假設(shè)磁盤(pán)塊大小為64 KB，則需進(jìn)行5×107×1 KB/64 KB=781 250次I/O操作.在列存儲(chǔ)模式下，只需讀取該列數(shù)據(jù)，進(jìn)行5×107×10 B/64 KB=7 630次I/O操作.由此可見(jiàn)，列存儲(chǔ)的查詢效率比行存儲(chǔ)提高了上百倍.

此外，列存儲(chǔ)在數(shù)據(jù)壓縮方面也比行存儲(chǔ)具有優(yōu)勢(shì).同一列的數(shù)據(jù)具有相同的數(shù)據(jù)類(lèi)型，數(shù)據(jù)的相似度比較大.行存儲(chǔ)中不同列有不同的數(shù)據(jù)類(lèi)型，很難為多種數(shù)據(jù)類(lèi)型選擇一個(gè)合適的壓縮算法.將壓縮算法應(yīng)用于列存儲(chǔ)數(shù)據(jù)庫(kù)中，可以降低數(shù)據(jù)的存儲(chǔ)空間，進(jìn)而降低磁盤(pán)同步和數(shù)據(jù)導(dǎo)入時(shí)間.

HBase和MySQL導(dǎo)入數(shù)據(jù)的時(shí)間比較見(jiàn)表8.由表可知，列數(shù)據(jù)庫(kù) HBase相比行數(shù)據(jù)庫(kù)MySQL在導(dǎo)入數(shù)據(jù)時(shí)間上具有明顯優(yōu)勢(shì).

表8 HBase和MySQL導(dǎo)入數(shù)據(jù)時(shí)間比較 ms

3.2 B+樹(shù)索引

B+樹(shù)上操作的時(shí)間通常由存取磁盤(pán)的時(shí)間和CPU計(jì)算時(shí)間構(gòu)成.與高速的CPU計(jì)算相比，磁盤(pán)I/O操作慢很多，因此可忽略CPU的計(jì)算時(shí)間，只分析磁盤(pán)訪問(wèn)次數(shù).

設(shè)一個(gè)維上B+樹(shù)索引的節(jié)點(diǎn)數(shù)為M，高度為h，最小度數(shù)t≥2，由B+樹(shù)的性質(zhì)可知

索引的創(chuàng)建采用自底向上的方法，無(wú)需分裂操作，存入磁盤(pán)的時(shí)間復(fù)雜度為O(M).一次查詢需要讀磁盤(pán)O(h)=O(logtM)次，對(duì)關(guān)鍵字進(jìn)行掃描的次數(shù)不超過(guò)2t，故查詢操作總的時(shí)間復(fù)雜度為O(th)=O(tlogtM).索引的更新可能需要申請(qǐng)新的節(jié)點(diǎn).在最壞情況下，每層最后一個(gè)節(jié)點(diǎn)均已包含最大關(guān)鍵字?jǐn)?shù)，添加新的索引項(xiàng)需要遞歸向上層申請(qǐng)新節(jié)點(diǎn)，訪問(wèn)磁盤(pán)的時(shí)間復(fù)雜度為O(h)=O(logtM).

將維層次編碼代替原關(guān)鍵字，可大大降低存儲(chǔ)空間.若維成員個(gè)數(shù)共計(jì)256個(gè)，簡(jiǎn)單位圖索引中的編碼需要256 bit，而維層次編碼只需8 bit，數(shù)據(jù)壓縮比為32.隨著維成員個(gè)數(shù)的增加，數(shù)據(jù)壓縮比呈指數(shù)型增長(zhǎng).同時(shí)，維層次編碼的壓縮效果約是整數(shù)編碼的3～4倍.

3.3 可擴(kuò)展性分析

HBase中，可在列族中動(dòng)態(tài)增刪某個(gè)列.利用這一特點(diǎn)，可以根據(jù)應(yīng)用場(chǎng)景動(dòng)態(tài)增加或刪除某個(gè)維和某個(gè)度量.在基本事實(shí)表中，定義維族和度量族2個(gè)列族，維族中將每個(gè)維定義為一個(gè)列，度量族中將每個(gè)度量定義為一個(gè)列.增刪某個(gè)維后需將對(duì)應(yīng)的B+樹(shù)索引進(jìn)行增刪;增刪某個(gè)度量后，需在每個(gè)維的維層次編碼-度量表的度量列族中增刪對(duì)應(yīng)的度量列.可見(jiàn)，在維和度量屬性上，本文算法具有較好的可擴(kuò)展性.

4 結(jié)語(yǔ)

本文分析了當(dāng)前OLAP聚集計(jì)算的現(xiàn)狀，在研究 OLAP數(shù)據(jù)模型和列存儲(chǔ)的基礎(chǔ)上，根據(jù)OLAP從維角度查詢度量值的特性，提出了一種OLAP維存儲(chǔ)模型，利用HBase的列存儲(chǔ)機(jī)制高效地管理了OLAP多維數(shù)據(jù).在此基礎(chǔ)上，提出了一種自底向上構(gòu)建基于維層次編碼的B+樹(shù)索引的方法，提高了對(duì)OLAP海量多維數(shù)據(jù)查詢的效率，為上層OLAP聚集計(jì)算提供了有效的支持.

References)

［1］Chaudhuri S，Dayal U.An overview of data warehousing and OLAP technology ［J］.SIGMOD Record，1997，26(1):65-74.

［2］Copeland G P，Khoshafian S N.A decomposition storage model［C］//Proceedings of the 1985 ACM SIGMOD International Conference on Management of Data.New York，USA，1985:268-279.

［3］Neil Roiter.SenSage opens SIEM data to business intelligence tools［EB/OL］.(2011-02-04)［2011-05-05］.http://www. networkcomputing. com/wan-security/sensage-opens-siem-data-to-business-intelligence-tools.php.

［4］羅潤(rùn)升.Sybase IQ紅寶書(shū)［M］.北京:中國(guó)水利水電出版社，2008:2-5.

［5］Chang F，Dean J，Ghemawat S，et al.BigTable:a distributed storage system for structured data［J］.ACM Transactions on Computer Systems，2006，26(2):4-8.

［6］Vermeij M，Quak W，Kersten M，et al.MonetDB，a novel spatial column-store DBMS［EB/OL］.(2008-10-31)［2011-05-05］.http://www.gdmc.nl/publications/2008/MonetDB.pdf.

［7］Stonebraker M，Abadi D J，Batkin A，et al.C-store:a column-oriented DBMS［C］//Proceedings of the 31st International Conference on Very Large Data Bases.Trondheim，Norway，2005:553-564.

［8］Hadoop Wiki.HBase:bigtable-like structured storage for Hadoop HDFS［EB/OL］.(2012-02-23)［2012-04-17］.http://wiki.apache.org/hadoop/Hbase.

［9］Feinberg D，Beyer M A.Magic quadrant for data warehouse database management systems［EB/OL］.(2011-01-28)［2011-05-05］.http://www.sybase.com/files/White_Papers/Gartner_MagicQuad_forDataWarehouse-DMS.pdf.

［10］Zou Yongqiang，Liu Jia，Wang Shicai.CCIndex:a complemental clustering index on distributed ordered tables for multi-dimensional range queries［J］.Lecture Notes in Computer Science，2010，6289:247-261.

［11］張延鵬.Data Cube中基于維層次的OLAP算法研究［D］.秦皇島:燕山大學(xué)信息科學(xué)與工程學(xué)院，2010.

［12］Karayaxmidis N，Tsois A，Sellis T，et al.Processing star querieson hierarchically-clustered facttables［C］//Proceedings of the 28th International Conference on Very Large Data Bases.Hong Kong，China，2002:730-741.