R樹下的空間數據庫索引技術探討

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

R樹下的空間數據庫索引技術探討

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

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

空間數據庫；空間索引技術；地理信息系統；探討；前景

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

引言

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

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

1.常見的空間數據庫索引技術

1.1 格網空間數據庫索引

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

1.2 K-D樹空間數據庫索引

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

1.3 R樹空間數據庫索引

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

1.4 四叉樹空間索引

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

2.空間數據庫索引技術的發展前景

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

3.總結

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

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

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

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

[4]余登峰.基于R樹的空間數據索引技術研究與實現[D].中國地質大學，2006.

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

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

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

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