數(shù)據(jù)倉庫的索引技術(shù)

1、 數(shù)據(jù)倉庫的索引技術(shù)TOC o 1-5 h z HYPERLINK l bookmark0 【摘要】1 HYPERLINK l bookmark2 【關(guān)鍵詞】1 HYPERLINK l bookmark4 【ABSTRACT】1 HYPERLINK l bookmark6 【KEYWORDS】2 HYPERLINK l bookmark10 1前言2 HYPERLINK l bookmark12 2數(shù)據(jù)倉庫常用的索引技術(shù)2 HYPERLINK l bookmark14 2.1位圖索引2 HYPERLINK l bookmark16 簡單位圖索弓丨技術(shù)(SimpleBitmapIndex)2 H

2、YPERLINK l bookmark18 編碼位圖索弓丨(EncodedBitmapIndex)3 HYPERLINK l bookmark20 B樹索弓4 HYPERLINK l bookmark22 連接索弓4 HYPERLINK l bookmark26 投影索弓5 HYPERLINK l bookmark32 各種索弓技術(shù)的特點及比較6 HYPERLINK l bookmark34 總結(jié)7 HYPERLINK l bookmark36 【參考文獻】7【摘要】數(shù)據(jù)倉庫系統(tǒng)中性能問題是非常重要的問題，索弓技術(shù)是提高性能的有效手段之一。本文分析與評述了數(shù)據(jù)倉庫中所使用的索引技術(shù)，這些技術(shù)包

3、括：位圖索引、B樹索引、連接索弓、投影索弓等。針對各自的特點，對這幾種技術(shù)進行了比較，對數(shù)據(jù)倉庫的研究與開發(fā)有較大的指導(dǎo)意義?！娟P(guān)鍵詞】數(shù)據(jù)倉庫位圖索引B樹索引連接索引投影索引【ABSTRACT】Theefficiencyofdatawarehouseisanimportantissue.Indextechnologiescanimprovetheefficiencyofdatawarehouse.Thepaperanalyzesandcomparewithindextechnologiesindatawarehouse,includingB-Treeindex,bitmapindex,joi

4、nindexandprojectionindex.Wecomparewiththeircharacteristics,whichcangiveaneffectiveguideondevelopmentandstudyondatawarehouse.KEYWORDS】DataWarehouse；BitmapIndex；B-TreeIndex；JoinIndex；ProjectionIndex1前言數(shù)據(jù)倉庫(Datawarehouse)是一個面向主題的、集成的、穩(wěn)定的、隨時間而變化的包含大量歷史數(shù)據(jù)的數(shù)據(jù)集合，它用于支持經(jīng)營管理中的決策制定過程。在數(shù)據(jù)倉庫中使用高效的索引技術(shù)不僅是必要的，而且是可

5、行的。數(shù)據(jù)倉庫面向分析型應(yīng)用，其數(shù)據(jù)是相對穩(wěn)定的，對數(shù)據(jù)倉庫的操作主要是讀取查詢數(shù)據(jù)，很少進行更新。這些少量的更新操作一般都是在非工作時間進行的，而且采用批處理方式，具有周期性?；跀?shù)據(jù)倉庫的上述特點，在進行數(shù)據(jù)的更新和索引的重新組織時，數(shù)據(jù)和索引都處于未被使用的狀態(tài)，因此可以采用一些復(fù)雜的索引來提高數(shù)據(jù)倉庫的查詢性能。目前，傳統(tǒng)的數(shù)據(jù)庫索引技術(shù)仍然是數(shù)據(jù)倉庫中建立索引的重要方法。同時，新的數(shù)據(jù)倉庫索引技術(shù)也在不斷發(fā)展。2數(shù)據(jù)倉庫常用的索引技術(shù)數(shù)據(jù)倉庫管理系統(tǒng)中的索引能夠提供一個相對快捷的方式定位數(shù)據(jù)。數(shù)據(jù)倉庫中常用的索引技術(shù)有位圖索引(bitmapindex)、B樹索弓I(B-Treeind

6、ex)、連接索引(joinindex)、投影索引(projectionindex)等。2.1位圖索引位圖索引是數(shù)據(jù)倉庫系統(tǒng)最常用的索引技術(shù)，目前有兩種位圖索引，一種是簡單的位圖索引，另一種是對簡單位圖索引的改進，稱為編碼位圖索引。位圖索引基本設(shè)計思想是用一個0、1位串來表示一個元組某一屬性的取值，位串中的位的位置表示了關(guān)系表中元組的位置。2.1.1簡單位圖索引技術(shù)(SimpleBitmapIndex)對于屬性域中的每個值v,設(shè)計一個不同的位向量Bv。如果給定的屬性域包含n個不同的取值，則位圖索引中的每項要用n位向量來表示。如果數(shù)據(jù)表中某一元組的屬性值為v,則在位圖索引的對應(yīng)行表示該值的位為1,

7、該行的其它位為0。假設(shè)在一個與銷售事實相對應(yīng)的數(shù)據(jù)立方中，有一個顧客的性別屬性Gender,一個是產(chǎn)品的種類屬性Item。其中Gender屬性有兩個不同的值：“M”和“F”。產(chǎn)品的種類屬性Item有四個不同的取值：“a”，“b”，“c”和“d”。設(shè)數(shù)據(jù)立方中共有8個元組。如果在Gender屬性上建立位圖索引則需要2個位向量，每個向量共8位。在Item上建立位圖索引需要四個位向量，每個向量共8位。這兩個索引如圖1所示。RIDItemGenderR1aFR2aMR3bFR4bFR5bMR6cFR7cMR8dM基本表RIDabcdR11000R21000R30100R40100R50100R6001

8、0R70010R80001Item位圖索引表圖1簡單位圖索引示意圖RIDMFR101R210R301R401R510R601R710R81001Gender位圖索引表2.1.2編碼位圖索引(EncodedBitmapIndex)編碼位圖索引是對簡單位圖索引的改進。為了壓縮位圖索引向量，利用編碼的方法把某一屬性的不同值進行編碼。編碼位圖索引由一個位圖向量集合(不同于簡單位圖索引的位圖向量集)、一個映射表(MappingTable)和一個檢索布爾函數(shù)(RetrievalBooleanFunction)集組成。其中映射表實現(xiàn)對一個屬性域值的編碼，該映射表定義了一組檢索布爾函數(shù)f,實現(xiàn)屬性值到編碼值的

9、映射。一個檢索函數(shù)的自變量為屬性I的域，其值域是具有k個比特位的編碼數(shù)。這里，k=(log2III),III表示屬性I的域中的不同取值個數(shù)，即屬性I的基數(shù)。一個元組j(記為tj)中的屬性I的值記為tj.I,根據(jù)映射表tj.I的編碼值為f(tj.I),它的第i位記做f(tj.I)i(i=0，1，k-1)，則屬性I的索引位圖向量集中的第j行的Bi位等于f(tj.I)i(i=0，1，,k-1)。例如，圖2是對應(yīng)圖1的基本表中的Item屬性的編碼位圖索引。其中，“a”編碼為“00”，“b”編碼為“01”，“c”編碼為“10”，“d”編碼為“11”。對于Item取值為“a”的元組，在位圖向量B1和B0上

10、相應(yīng)的取值都為“0”。類似的Item取值為“b”的元組,位圖向量B,和B0的取值為“0”和“1”。本例中，屬性Item有4個不同的取值，所以k=2?；颈砦粓D向量映射表RIDItemR1aR2aR3bR4bR5bR6cR7cR8dRIDB2B0R100R200R301R401R501R610R710R811圖2編碼位圖索引舉例Item值編碼值a00b01c10d11上例中在Item屬性上有四個不同值，對于簡單位圖索引要四個位向量，而對于碼的位圖索引只需二個位向量。如果有12000個不同值，對于簡單位圖索引需要12000個位向量，對于編碼位圖索引只需(Iog2ll2000l)=14個位向量。顯然

11、編碼位圖索引較簡單位圖索引有較大的優(yōu)勢。2.2B樹索引B樹是一種動態(tài)調(diào)節(jié)的平衡樹，它引入了一種效率很高的外查找機制，比較適合于字段值分散且重復(fù)值少的字段。一個B樹索引包含一個由高層結(jié)點和相繼低層結(jié)點組成的層次結(jié)構(gòu)。在B樹索引中有兩類結(jié)點：分支結(jié)點：簡單地指向相應(yīng)的低層結(jié)點。葉子結(jié)點：存放B樹方法的實際內(nèi)容。即包含指向葉子所對應(yīng)的行的實際位置。在B樹索引中，一個非常重要的變量就是建立在鍵值基礎(chǔ)上的分區(qū)索引。分區(qū)索引是一種特殊的B樹索引。在這種索引中，根據(jù)一定范圍的鍵值，表被分解成若干小部分(分區(qū))。利用時間進行分區(qū)是常用的方法。B樹結(jié)構(gòu)的特點是簡潔性、易維護性及支持具有高可選擇性列值的高速檢索。

12、這種方法適合于對索引列值等值查找和范圍查找的查詢。表的大小，無論它包含數(shù)百行還是數(shù)百萬行記錄，對于從其相應(yīng)表中提取用B樹索引的數(shù)據(jù)的速度差別很小，甚至沒有影響。下圖是一個B樹索引的例子，在其中查找行標(biāo)識48的步驟如下：從根結(jié)點r開始，因為4536，所以根據(jù)36右側(cè)的指針找到結(jié)點a2；在結(jié)點a2中，444879，根據(jù)44和79之間的指針找到結(jié)點b4；在結(jié)點b4中存在行標(biāo)識48，查找任務(wù)結(jié)束。圖3B-樹結(jié)構(gòu)2.3連接索引復(fù)雜的查詢語句通常需要多表連接，連接索引能夠提高多表連接的性能。連接索引包括這樣的索引項，它的內(nèi)容是連接的且滿足連接要求的表的元組標(biāo)志(TID)，它的每一元組包括所有要連接的表的元

13、組標(biāo)志(TID)。例如,如果兩個關(guān)系R(RID,A)和S(SID,B)在屬性A和B上連接，則連接索引記錄包含(RID，SID)對，其中RID和SID分別來自R和S的記錄標(biāo)志符。連接索引能夠在多表中建立，連接索引能夠?qū)⑺蟹线B接條件的連接記錄下來。為進一步加快查詢處理速度，可以將連接索引和位圖索引混合起來使用，即在連接索引中使用Bitmap技術(shù)，利用Bitmap技術(shù)的性質(zhì)，指出實際表中的值。例如，在一個星型模式中，事實表Sales與維表Customer和Item三者之間的鏈接關(guān)系如圖4所示。它們的鏈接索引表如圖5所示。對連接索引的進一步改進是位圖連接索引。上例中，我們要對顧客的Gender為男

14、性的銷售建立位圖連接索引，這要通過事實表Sales與維表Customer作連接操作來完成。事實表Sales中與Customer的Gender屬性等于M的Customer_id相對應(yīng)的元組，位圖連接索引的值為1,否則為0。如圖6所示，位向量的長度等于事實表的元組數(shù)。圖4事實表Sales與Customer和Item表的連接.LMT5CT72陽TIM-Customer上m制境Myirtll1haaT72JUL1ETbriCustomer/Sales連接索引表Item/Sales連接索引表Customer/Item/Sales連接索引表圖5事實表Sales與Customer和Item表連接的連接索引表

15、F110001011000001111M001110100111110000圖6事實表Sales關(guān)于Gender屬性對應(yīng)的位圖連接索引2.4投影索引投影索引是利用投影的概念把某一個表T上的某一屬性A的值以同樣的順序都保存起來，投影索引的每一行是屬性A的一個值。值索引中值X的次序與T中值X的次序一致。數(shù)據(jù)倉庫中的查詢一般只在表中的部分屬性上進行，在這些建立投影索引會大大提高查詢的性能。假設(shè)C是表T的一個列，那么在該列上建立的投影索引就是C中的列值按行號排序的存儲序列。該索引的存儲序列中各值的存儲位里以存儲頁P和在該頁中的存儲位置S來表示。如果列C的取值長度為6個字節(jié)，每一個存儲頁的大小為3K字節(jié)

16、，則每一個存儲頁可以存放500個列C的值。由于列C的索引是按行號排序的，只要給出行號R，就可以根據(jù)公式（3.1）計算出相應(yīng)列C取值的存儲頁P及在該頁中的存儲位置S；如果已知列C取值相應(yīng)的存儲位里，根據(jù)公式（3.2）可以確定其行號。（公式3.1）P=R/500（取整）；S=R%500（取模）（公式3.2）R=500*P+S雖然投影索引類似于一種垂直分割，但表T中的記錄不一定垂直存儲，垂直存儲的只是列C的索引。而該索引的各項取值是從表T中的列C中復(fù)制過來的，不影響表T的存儲格式。首先采用投影索引的是Sybase，使用的名稱是“快速投影索引”。在不僅要檢索到所需的記錄，而且要確定索引列值的情況下，投

17、影索引是非常有效的。3各種索引技術(shù)的特點及比較索引描述優(yōu)點缺點商業(yè)實現(xiàn)B樹索引把存儲塊組織成一棵樹來減少I/0操作需要少的I/O操作；.適合于咼基數(shù)的列；能自動數(shù)據(jù)文件大小相適應(yīng)的索引層次；索引空間的需求獨立于被索引列的基數(shù)；.易于創(chuàng)建；低基數(shù)的列效果不好；不支持即席查詢；對寬范圍查詢I/O代價相對較咼：在獲取數(shù)據(jù)之間索引不能合并；大多數(shù)據(jù)的商用數(shù)據(jù)（0raleRedBrick等）簡單位圖索引為索引屬性的每個取值建立一個位向量，向量長度等于元組數(shù)。對應(yīng)的元組中相應(yīng)的索引位置1，若該值出現(xiàn)，否則為0適合于低基數(shù)的列；.利用位操作；.獲取數(shù)據(jù)之前可合并索引；便于在并行機上執(zhí)行；可以咼效地完成對屬性

18、的數(shù)量型函數(shù)（如count）的查詢；.易于創(chuàng)建；:易于插入新的索引值；.適合于OLAP；高基數(shù)的列效果不好；更新索引列代價較高；不能很好處理稀疏數(shù)據(jù)OracleAscenialSybaseRedBrickDB2編碼位圖索引對屬性的域進行二進制編碼有效地利用空間；可以實現(xiàn)寬的范圍查詢；對于等值查詢效率低；很難找到好的的編碼方案；當(dāng)有新的屬性值出現(xiàn)，現(xiàn)有的位數(shù)不能滿足，需重建；DB2位圖連接索引索引的創(chuàng)建通過維表對事實表的約束實現(xiàn)的靈活性較好；有效地執(zhí)行；支持星型杳詢；索引列的次序很重要OracleAscenialRedBrick投影索引通過實際存儲被索引表的列值建索引當(dāng)只檢索表中的幾個列時，加速比較咼；只能用于檢索原數(shù)據(jù)；Sybase4總結(jié)為了提高查詢速度，最理想的情況是查詢能夠盡可能使用已有的索引。因此，應(yīng)該為多數(shù)表建立多個索引，特別是要在維表上建立索引。在星型模型中，一個維表可能包含數(shù)量較多的記錄，并經(jīng)常以各種不同的方式被使用，而與維表有關(guān)的事實表的記錄更是數(shù)量繁多。因此，如果在維表上有高效的索引，就能夠