多維索引(數(shù)據(jù)庫)

時(shí)間：2022-12-20 20:30:01 | 來源：信息時(shí)代

時(shí)間：2022-12-20 20:30:01 來源：信息時(shí)代

    多維索引 : 為方便查找多維空間數(shù)據(jù)而構(gòu)造的基于屬性特征的數(shù)據(jù)結(jié)構(gòu)。多媒體數(shù)據(jù)是多維空間中的點(diǎn),每個(gè)點(diǎn)有若干屬性,每個(gè)屬性是一維。多媒體數(shù)據(jù)所需要支持的查詢種類包括: 部分屬性匹配、各屬性值分別滿足所規(guī)定范圍的查詢、最相似查詢和包含給定媒體數(shù)據(jù)的區(qū)域或區(qū)域集的查詢。如果按照傳統(tǒng)的方法為多媒體數(shù)據(jù)建立一維索引,執(zhí)行查詢操作,理論和實(shí)踐都證明,不僅性能達(dá)不到要求,開銷也極其昂貴。因此,必須對(duì)多媒體數(shù)據(jù)建立多維索引。目前,支持多維索引的方法主要有三大類:類散列表、類樹和位圖。
1. 類散列表
(1)網(wǎng)格: 首先由J. Nievergelt等人于1984年提出。網(wǎng)格是比一維索引性能要好,且最為簡單的數(shù)據(jù)結(jié)構(gòu)之一。網(wǎng)格的每一維網(wǎng)格線把空間分成條狀,不同維的網(wǎng)格線的數(shù)目可以不同,同一維的線之間可以有不同的距離。網(wǎng)格空間的每一個(gè)子空間可以被看成是散列表的一個(gè)桶,落入子空間的每個(gè)點(diǎn)的記錄都存放在屬于該空間的塊中。如有必要,可以使用溢出塊來增加子空間的體積。在多媒體數(shù)據(jù)分布得相當(dāng)均勻的情況下,使用網(wǎng)格法進(jìn)行范圍查詢、部分匹配和相似查詢可以獲得較好的性能。
(2)分段散列:1976年由W.A. Burkhard和R.L.Rivest分別提出。分段散列法構(gòu)造散列函數(shù),使分別散列數(shù)據(jù)的m個(gè)屬性得到的m個(gè)二進(jìn)制位拼接成n位的二進(jìn)制數(shù),而拼接的結(jié)果就是該多媒體數(shù)據(jù)所在的桶號(hào)。通常,即使數(shù)據(jù)分布不均勻,分段散列法用于部分匹配也可以取得較好的效果。
2.類樹
(1) 多鍵索引: 是建立索引的索引,即,一棵樹的每一層結(jié)點(diǎn)都是一個(gè)屬性的索引。這種簡單的類屬方法對(duì)于范圍查詢和最鄰近查詢較有用,但對(duì)部分匹配,其性能較差,且開銷較大。
(2) Kd樹: 一種二叉樹,又叫k維搜索樹,是1975年J.L.Bentley提出的。Kd樹的內(nèi)部結(jié)點(diǎn)只有屬性、劃分左右子女的屬性值、指向左右子女的指針; 樹的不同層的屬性不同; 葉結(jié)點(diǎn)中存放著盡可能多的紀(jì)錄。Kd樹可以較好地支持部分匹配、范圍查詢和最臨近查詢。不過,由于中間結(jié)點(diǎn)存放的信息少,如果每個(gè)結(jié)點(diǎn)占用一個(gè)存儲(chǔ)塊,那么,不僅浪費(fèi)空間,并且遍歷一條路經(jīng)所需的I/O多于B樹。通過將多個(gè)內(nèi)結(jié)點(diǎn)壓縮到一個(gè)存儲(chǔ)塊內(nèi)和將內(nèi)結(jié)點(diǎn)設(shè)計(jì)成具有多分支,就可以有效地提高性能。
(3) 四叉樹: 于1974年由R. A. Finke和J. L.Bentley第一次提出。四叉樹的每個(gè)內(nèi)結(jié)點(diǎn)對(duì)應(yīng)于n維空間的n方體。通常,一個(gè)n維的四叉樹有2n個(gè)子結(jié)點(diǎn),所以,在維數(shù)高的情況下可以只保留非空指針和關(guān)聯(lián)的非空象限標(biāo)示以節(jié)省空間。四叉樹可以用于部分匹配、范圍查詢和最臨近查詢。
(4) R樹: 首先于1984年由A.Guttman提出,并分別由T. K. Sellis等人和N. Beeckmann等人于1987年和1990年進(jìn)行了擴(kuò)展。R樹表示多維區(qū)域組成的數(shù)據(jù)區(qū),它的內(nèi)結(jié)點(diǎn)對(duì)應(yīng)于其中的某個(gè)子區(qū)域,并用子區(qū)域替代鍵表示子結(jié)點(diǎn)的內(nèi)容。子區(qū)域之間可以有重疊,當(dāng)然,重疊要盡可能小; 所有的子區(qū)域不一定覆蓋整個(gè)數(shù)據(jù)區(qū),但是都完全包含在數(shù)據(jù)區(qū)內(nèi)。R樹適用于查找指定數(shù)據(jù)所在的位置,如果子區(qū)域都是點(diǎn),也可以用于部分匹配、范圍查詢和最臨近查詢。
3.位圖法
Glaser創(chuàng)立的Nucleus公司申請(qǐng)了位圖索引的專利,并開發(fā)了一個(gè)數(shù)據(jù)庫管理系統(tǒng),在該系統(tǒng)中位圖索引既是索引結(jié)構(gòu)又是數(shù)據(jù)表示。最早商業(yè)應(yīng)用是1970年美國計(jì)算機(jī)公司(computer corporation of America,CCA)上市的數(shù)據(jù)庫管理系統(tǒng)“Model204”,用于加快查詢的處理過程。位圖索引的思想是由P.O’Neil于1987年第一次公開介紹,并于1997年進(jìn)行了改進(jìn)。Oracle公司于2001年申請(qǐng)了相關(guān)專利: 在類B⁺-樹結(jié)構(gòu)中支持位圖索引。位圖索引最簡單的形式是,每個(gè)屬性的位圖索引是長度為n(多媒體數(shù)據(jù)總數(shù))的位向量的集合。每一個(gè)位向量對(duì)應(yīng)于屬性可能出現(xiàn)的每一個(gè)值。如果第i個(gè)數(shù)據(jù)的某屬性值為v,那么對(duì)應(yīng)于值v的位向量在位置i上的取值為1,否則該向量的位置i上的取值為0。在實(shí)際問題中,位向量中會(huì)有許多取值為0的位,為了節(jié)省位圖索引空間,可以通過采用游程長度編碼來對(duì)位圖索引進(jìn)行壓縮。位圖索引能夠支持部分匹配、范圍查詢、最臨近查詢。