基于R-tree的高維索引結(jié)構(gòu)研究.pdf

1、隨著互聯(lián)網(wǎng)和多媒體技術(shù)的迅猛發(fā)展與普及，人們可以通過計算機輕易地接觸并獲取到大量有用的數(shù)據(jù)。如何對大量數(shù)據(jù)對象進行有效檢索成為了計算機應(yīng)用中的一個非常重要的研究課題，數(shù)據(jù)庫技術(shù)中的索引結(jié)構(gòu)正是為了解決此問題而出現(xiàn)。 傳統(tǒng)的索引結(jié)構(gòu)（如B—tree等）可以很好的解決單維數(shù)據(jù)的檢索問題，然而現(xiàn)在接觸到的數(shù)據(jù)大部分屬于高維數(shù)據(jù)。而由于高維數(shù)據(jù)自身的無序性與復(fù)雜性等特點，傳統(tǒng)的索引結(jié)構(gòu)無法直接對其進行處理，所以必須建立高維索引來進行管理

2、。自從Guttman提出了基于樹形結(jié)構(gòu)的R—tree后，相關(guān)學(xué)者紛紛在此基礎(chǔ)上進行進一步的研究，例如在此基礎(chǔ)上提出的R*—tree等。 本文在對R—tree族以及KDB—tree族索引結(jié)構(gòu)研究的基礎(chǔ)上，對R*—tree在處理點數(shù)據(jù)方面進行了改進。首先分析了R*—tree在處理點數(shù)據(jù)上的弱勢以及改進必須解決的問題；接著在R*—tree結(jié)構(gòu)的基礎(chǔ)上提出了一種新的高維點訪問方法ppR—tree（perfect point R—tree

3、）。該方法的基本結(jié)構(gòu)基于R*—tree，但是在分裂算法中結(jié)合Perfect KDB—tree中自上而下分裂的思想而提出節(jié)點重構(gòu)技術(shù)，可以有效減少節(jié)點間的重疊區(qū)域；另外，在壓縮節(jié)點信息方面，ppR—tree引入了有效維機制，增加了高層節(jié)點的扇出，可以有效降低樹高。最后，通過實驗驗證了ppR—tree在全部測試維的幾乎所有分布中范圍查詢性能優(yōu)于R*—tree，KDB—tree以及Perfect KDB—tree，數(shù)據(jù)點查詢性能優(yōu)于R*—tr