于 亮 蘇 丹 黑龍江省黑河學院

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

于 亮 蘇 丹 黑龍江省黑河學院

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

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

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

引言

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

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

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

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

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

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

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

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

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

1.4 四叉樹空間索引

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

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

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

3.總結

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

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

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

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

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

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

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

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

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