于 亮 蘇 丹 黑龍江省黑河學(xué)院

R樹下的空間數(shù)據(jù)庫索引技術(shù)探討

于 亮 蘇 丹 黑龍江省黑河學(xué)院

近年來，隨著計(jì)算機(jī)的廣泛應(yīng)用和信息處理技術(shù)的快速發(fā)展，地理信息系統(tǒng)（GIS）也得到了快速的發(fā)展，已經(jīng)廣泛應(yīng)用于公共管理、科研等領(lǐng)域?？臻g數(shù)據(jù)庫索引技術(shù)作為地理信息系統(tǒng)的核心內(nèi)容，現(xiàn)已經(jīng)成為空間數(shù)據(jù)庫研究的熱點(diǎn)。本文通過闡述空間數(shù)據(jù)庫索引技術(shù)，分析了空間數(shù)據(jù)庫索引的集中常見技術(shù)，以及探討了其發(fā)展前景。

空間數(shù)據(jù)庫；空間索引技術(shù)；地理信息系統(tǒng)；探討；前景

由于傳統(tǒng)的數(shù)據(jù)庫在空間數(shù)據(jù)的存儲(chǔ)、管理以及信息檢索等方面都存在一定的缺陷，這就使得空間數(shù)據(jù)庫的索引技術(shù)不斷的發(fā)展，其索引技術(shù)越來越受到人們的重視。

引言

空間數(shù)據(jù)庫是計(jì)算機(jī)物理存儲(chǔ)介質(zhì)用來存儲(chǔ)空間數(shù)據(jù)的。對空間數(shù)據(jù)庫的研究，是從上個(gè)世紀(jì)70年代的地圖制圖與遙控感知圖像處理領(lǐng)域開始的，其目的是為了利用衛(wèi)星資源快速的繪制出各種地圖。傳統(tǒng)的數(shù)據(jù)庫為了提高信息檢索效率，都會(huì)建立一系列的索引機(jī)制，索引機(jī)制無需查遍整個(gè)數(shù)據(jù)庫，就可以快速訪問某條特定查詢的數(shù)據(jù)，例如B樹。但這些都是一維索引，無法處理空間數(shù)據(jù)庫中的二維、三維以及三維的空間技術(shù)。

空間數(shù)據(jù)庫索引技術(shù)直接影響到空間數(shù)據(jù)庫系統(tǒng)的成敗?？臻g數(shù)據(jù)庫索引技術(shù)的提出是由兩個(gè)原因決定的：第一，計(jì)算機(jī)存儲(chǔ)器分內(nèi)存和外存兩種，訪問這兩種存儲(chǔ)器所花費(fèi)的時(shí)間相差十萬倍以上。并且在實(shí)際應(yīng)用中，其空間數(shù)據(jù)都在存儲(chǔ)在外存上，如果對外存內(nèi)的空間數(shù)據(jù)的位置不加以索引，那么每查詢一個(gè)數(shù)據(jù)就需要掃描整個(gè)外存上所存儲(chǔ)的數(shù)據(jù)文件，這種數(shù)據(jù)查詢的代價(jià)會(huì)嚴(yán)重影響系統(tǒng)的工作效率。因此，系統(tǒng)的設(shè)計(jì)者必須對磁盤上數(shù)據(jù)位置加以索引，只有通過對內(nèi)存中的計(jì)算來取代對外存多余無效的訪問，才能夠提高系統(tǒng)的工作效率。第二，傳統(tǒng)的數(shù)據(jù)庫索引技術(shù)并不適用空間數(shù)據(jù)的多維空間，因?yàn)閭鹘y(tǒng)的數(shù)據(jù)庫索引技術(shù)的數(shù)據(jù)類型都是在一個(gè)維度上，而空間數(shù)據(jù)庫則具有多維空間，并且目前也并不存在從一維空間映射到高維空間。因此，傳統(tǒng)的數(shù)據(jù)庫索引技術(shù)并不能對空間數(shù)據(jù)庫進(jìn)行有效的索引，所以需要研究能夠適用多維空間數(shù)據(jù)的索引方式。

1.常見的空間數(shù)據(jù)庫索引技術(shù)

1.1 格網(wǎng)空間數(shù)據(jù)庫索引

格網(wǎng)空間數(shù)據(jù)庫索引就是將目標(biāo)空間實(shí)體所在的空間范圍劃分成一系列相同大小的格。每一格都代表一個(gè)桶，用來記錄該格內(nèi)空間實(shí)體的編號。格網(wǎng)空間索引的查找方式非常簡單，數(shù)據(jù)分布較均勻的話，那么查詢的效率較高。但是需要注意的是，格網(wǎng)的大小會(huì)影響到索引表的大小，如果格網(wǎng)太小，索引就會(huì)膨脹，不但查詢效率變低，而且對索引表的維護(hù)費(fèi)用也會(huì)增加。

1.2 K-D樹空間數(shù)據(jù)庫索引

K-D樹是早期用于索引多維空間數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)之一。 K-D樹將每一層的空間都劃分為兩部分。 K-D樹空間索引的原理是沿著樹的根結(jié)點(diǎn)進(jìn)行一維劃分，依次劃分下一層結(jié)點(diǎn)，盡量讓左右子樹中的結(jié)點(diǎn)數(shù)目均衡，如果結(jié)點(diǎn)中包含的點(diǎn)數(shù)小于葉子結(jié)點(diǎn)中包含的最大點(diǎn)數(shù)時(shí)要停止劃分。另外， K-D樹中的每條線都要與樹中的結(jié)點(diǎn)相對應(yīng)。采用K-D樹空間索引需要注意的是，如果樹型結(jié)構(gòu)的遞歸層次越深，則查詢的效率就越低。

1.3 R樹空間數(shù)據(jù)庫索引

R樹空間數(shù)據(jù)庫索引是在B樹的基礎(chǔ)上擴(kuò)展了多維空間，是最早支持多維空間存取的方法之一。 R樹作為一種高度平衡樹，不但可以控制樹的深度，而且也可以采用最小外包矩形來表示空間實(shí)體。 R樹有三條特性，第一，葉節(jié)點(diǎn)中存儲(chǔ)該結(jié)點(diǎn)對應(yīng)的空間要素的最小外包矩形和空間要素標(biāo)識(shí)；第二，最小外包矩形在二維空間中是矩形，而在三維中是長方體，以此類推到高維空間；第三， R樹作為動(dòng)態(tài)索引結(jié)構(gòu)，可以同時(shí)進(jìn)行刪除、查詢以及插入等行為，而且對樹結(jié)構(gòu)也不需要定期組織。不過，由于空間數(shù)據(jù)分布的不確定性，所以各層節(jié)點(diǎn)的最小外包矩形很容易重疊，導(dǎo)致在實(shí)際查詢時(shí)會(huì)產(chǎn)生多個(gè)查詢分支，在很大程度上降低了查詢效率。

1.4 四叉樹空間索引

四叉樹空間索引的機(jī)制是基于相同網(wǎng)格而劃分的，其工作空間是在X、 Y方向上進(jìn)行的2N等分，從而形成2N×2N的固定網(wǎng)格，并以此建立N級四叉樹。在四叉樹中，空間要素的標(biāo)識(shí)都記錄在外包絡(luò)矩形覆蓋的每一個(gè)葉節(jié)點(diǎn)中。其在內(nèi)存中的層次樹狀結(jié)構(gòu)的查詢效率較高。另外，層次型的樹狀結(jié)構(gòu)并不適用直接描述數(shù)據(jù)庫表，則可通過對四叉樹的各層節(jié)點(diǎn)都編上碼，從而反映四叉樹的層次結(jié)構(gòu)。

2.空間數(shù)據(jù)庫索引技術(shù)的發(fā)展前景

隨著數(shù)字城市、定位服務(wù)的提出和應(yīng)用以及推廣，空間數(shù)據(jù)庫索引技術(shù)作為地理信息系統(tǒng)的核心，所以其也正朝著高維空間、基于空間關(guān)系等方面發(fā)展?；谌SGIS、多媒體數(shù)據(jù)庫以及空間數(shù)據(jù)庫對多維空間的探索以及更新效率的要求日益迫切，所以，有必要研究一種名可以擴(kuò)展高維空間的索引技術(shù)，高位數(shù)據(jù)索引最關(guān)鍵的一項(xiàng)技術(shù)就是降維，在檢索高維數(shù)據(jù)的同時(shí)，還能夠有效的檢索一維、二維的數(shù)據(jù)。向空間關(guān)系方面發(fā)展，則是由于當(dāng)前的查詢與分析操作都是基于目標(biāo)間的空間關(guān)系，而空間數(shù)據(jù)庫中的空間目標(biāo)大多數(shù)都是不規(guī)則的幾何形狀，并且還存在著較為負(fù)責(zé)的空間關(guān)系，所以在基于空間目標(biāo)的空間關(guān)系上，有必要建一個(gè)基于空間關(guān)系動(dòng)態(tài)索引，這樣不但可以有效地提高空間數(shù)據(jù)庫的查詢和分析的效率，而且還能夠有效的擴(kuò)展空間數(shù)據(jù)庫系統(tǒng)的數(shù)據(jù)組織、分析以及維護(hù)等功能。

3.總結(jié)

空間數(shù)據(jù)庫是隨著地理信息系統(tǒng)的快速發(fā)展而興起的新技術(shù)。由于地理環(huán)境較為復(fù)雜，以及海量空間數(shù)據(jù)的快速查詢、檢索以及空間分析計(jì)算都需要數(shù)據(jù)庫進(jìn)行管理，如果采用傳統(tǒng)的關(guān)系數(shù)據(jù)庫系統(tǒng)來管理空間數(shù)據(jù)，則查詢效率較低，因此為了提高查詢的效率，則選擇采用空間數(shù)據(jù)庫索引技術(shù)。

[1]赫玄惠.空間數(shù)據(jù)庫索引技術(shù)的研究及應(yīng)用[D].華北電力大學(xué)，2012.

[2]吳昊.空間數(shù)據(jù)庫索引技術(shù)與應(yīng)用研究[D].南京郵電大學(xué)，2013.

[3]宋明明.基于R-樹的空間數(shù)據(jù)庫索引技術(shù)研究與應(yīng)用[D].江蘇科技大學(xué)，2014.

[4]余登峰.基于R樹的空間數(shù)據(jù)索引技術(shù)研究與實(shí)現(xiàn)[D].中國地質(zhì)大學(xué)，2006.

[5]周帆.基于R-樹的空間數(shù)據(jù)索引技術(shù)的研究與實(shí)現(xiàn)[D].哈爾濱理工大學(xué)，2009.

[6]陳敏.基于R-樹空間索引的優(yōu)化研究與應(yīng)用[D].福州大學(xué)，2006.

[7]周長英，陳穎.空間數(shù)據(jù)庫索引技術(shù)發(fā)展概況[J].黑龍江科技信息，2010，31∶84.

黑龍江省教育廳科學(xué)技術(shù)項(xiàng)目，項(xiàng)目名稱：空間數(shù)據(jù)庫索引技術(shù)研究，項(xiàng)目編號：12541573。