《GIS中幾種空間數據索引方法探究》由會員分享，可在線閱讀gis空間查詢方法有哪些gis空間查詢方法有哪些，更多相關《GIS中幾種空間數據索引方法探究（7頁珍藏版）》請在人人文庫網上搜索。
1、 1引言空間索引也稱為空間訪問方法是對存儲在介質上的數據位置信息的描述,是指依據空間對象的位置和形狀或空間對象之間的某種空間關系按一定的順序排列的一種數據結構,其中包含空間對象的概要信息,如對象的標識外接矩形及指向空間對象實體的指針。作為一種輔助的空間數據結構,空間索引介于空間操作算法和空間對象之間,它通過篩選作用與特定空間操作無關的空間對象被排除從而提高空間操作的速度和效率。近年來地理信息系統快速發展,其主要功能之一就是檢索空間數據以及查詢所需的信息。而空間索引技術作為空間數據庫和地理信息系統的關鍵技術,其性能的優劣將直接影響空間數據的存儲效率以及空間檢索的性能,關系到地理信息系統的整體性能
2、。目前地理信息系統中兩種常用的對象分割方法是規則分割方法和基于對象的分割方法。和這兩種分割方法相對應的空間索引為基于規則網格的空間索引(網格索引、BSP樹索引、四叉樹索引和基于對象分割的空間索引(R樹家族索引。在這些索引結構中,又以網格空間索引、四叉樹空間索引和R樹系列空間索引最為常見。2幾種常見空間索引分類及特點2.1 網格索引網格索引的基本思想是將研究區域按一定規則用橫豎線分為小的網格,記錄每個網格所包含的地理對象。當用戶進行空間查詢時,首先計算查詢對象所在的網格,然后通過該網格快速查詢所選的地理對象。網格索引算法大致分為三類:基于固定網格劃分的空間索引算法、基于多層次網格的空間索引算法和
3、自適應層次網格空間索引算法。將一幅地圖分割成a*b的固定網格,為落入每個格網GIS中幾種空間數據索引方法探究孫卓成(中國地質大學(武漢信息工程學院湖北·武漢 摘要:空間索引技術是空間數據庫和地理信息系統的關鍵技術,其性能的優劣將直接關系到地理信息系統的整體性能。本文對GIS中幾種常見的空間索引技術作了介紹,并分析優缺點,為今后進一步的研究提供參考依據。關鍵詞:空間索引地理信息系統中圖分類號:C914 文獻標識碼:A 文章編號:1007-3973(-097-1(2IPS 設備串接于路由器與防火墻,利用 IPS 能夠快速終結 DoS 與 DDoS、未知的蠕蟲、異常
4、應用程序流量攻擊所造成的網絡阻塞,實現對工業以太網的防護,同時它能保護防火墻和核心交換機等網絡設備免遭入侵和攻擊。IPS 會在此類網絡攻擊擴散到網絡的其它地方之前阻止這個惡意的通信,在網絡中起到防御的作用。具體實現方式是IPS 將檢查入網的數據包,確定這種數據包的真正用途,然后決定是否允許這種數據包進入你的網絡。這種技術從源頭控制了對工業以太網的惡意攻擊。具體部署參考圖2。上級過程監控網絡底層網絡核心路由器現場底層交換機現場終端控制主機圖2IPS入侵防御系統4結語工業以太網由于其成本上的優勢和良好的開放性和廣泛性,正慢慢進入生產領域。做為當前工業控制領域的熱點方向,它吸引了大量的廠商介入其領域
5、,但是其特有的性質使其容易受到網絡安全的影響,從而制約其發展。相信隨著研究的深入,工業以太網應用中的安全問題將逐步得到解決。參考文獻:1馮冬芹,金建祥,褚健.工業以太網關鍵技術初探J.信息與控制,2003,6月:.2彭杰,應啟戛,工業以太網的安全性研究J.儀器儀表學報,2004,8月:第25卷第4期.3陳宏,基于工業以太網的控制數據加密研究D.浙江大學碩士學位論文,2005年2月.4王玉敏,工業以太網信息安全J.儀器儀表標準化與計量,2007,4:10.,Snort,吳薄峰等.譯入侵檢測實用解決方案M.北京:機械工業出版社,2005. 內的地圖目標建立索引,這
6、樣只需檢索原來區域的1/a*b,以達到快速檢索的目的。該算法的優點是操作簡單,在涉及的數據量不大、不需要進行復雜操作時具有一定的適應性。將一幅地圖分割成若干大小相同的小塊,將落入該小塊內的地圖目標存入該小塊、塊對應的存儲區域中,根據需要可以將小塊劃分成更小的塊,建立多級索引。該算法的優點是檢索的效率比較高,相比于純粹的網格索引減少了特定的比較次數。但是網格劃分的精細程度無法保證最優。對處于網格邊緣的對象沒有一個很好的解決辦法,沒有考慮到地圖目標的水平與垂直分布對網格劃分的影響。其網格大小由各具體的地圖目標的外接矩形決定,避免了網格索引中網格劃分的人為因素。算法的優點是網格劃分穩定自動,以各地圖
7、目標的外接矩形的大小作為劃分依據,避免了重復存儲,在存儲效率上有一定改善。不足就是算法實現復雜,建立索引前,必須知道各地圖目標外界矩形的長、寬,按其面積大小排序;建立索引后,進行插入或刪除操作時,涉及的地圖目標的外接矩形面積若不是原有面積大小,則需要重新進行排序,效率反而會下降。2.2 四叉樹索引四叉樹索引,類似于網格索引,也是對地理空間進行網格劃分,對地理空間遞歸進行四分來構建四叉樹,直到自行設定的終止條件(比如每個節點關聯圖元的個數不超過3個,超過3個,就再四分,最終形成一顆有層次的四叉樹。每個葉子節點存儲了本區域所關聯的圖元標識列表和本區域地理范圍,非葉子節點僅存儲本區域地理范圍。由于四
8、叉樹的生成和維護比較簡單,且當空間數據對象分布比較均勻時,基于四叉樹的空間索引可以獲得比較高的空間數據插入和查詢效率。2.3 R樹家族索引這是一種面向對象分割技術的索引算法,將空間對象按范圍劃分,每個節點都對應一個區域和磁盤頁,非頁節點的磁盤頁中存儲著其子節點的區域范圍;葉節點的磁盤頁中存儲著其區域范圍內的所有空間對象的外接矩形。R樹算法是一種層次數據結構動態索引算法,它是B 樹在K維空間上的自然擴展,是一種高度平衡樹。R樹由根節點、中間節點和葉節點三類節點組成,中間節點代表數據集空間中的一個矩形,該矩形包含了所有其他孩子節點的最小外接矩形,葉節點存儲的是實際對象的外接矩形。R樹允許節點相互覆
9、蓋,這種覆蓋可以使R樹保持較高的空間利用率和保持樹的平衡。相比網格索引,無需預知整個研究區域的索引范圍就能建立空間索引,減少了大地理對象的存儲冗余。由于它是按數據來組織索引結構,是一種完全動態的索引結構,不需要周期性的索引重組。但是節點之間的過多覆蓋不能保證檢索路徑的唯一性,有的甚至會檢索整個樹,造成查詢效率的降低。在1987年提出了R+樹。R+樹與R樹類似,區別在于R+樹中兄弟節點對應的空間區域無重疊,這樣就消除了R樹劃分空間時因允許節點重疊而產生的死區域,減少無效查詢次數,提高空間索引的效率,但插入刪除操作則效率降低。R+樹中間節點的所有矩形都是不相交的。如果一個對象的MBR被
10、兩個或多個R+樹高層節點中的矩形分割,與這些非葉節點中矩形相聯系的每個項都有指向這個對象的一個后繼葉節點。這樣樹的高度增加,但搜索操作的性能會有很大提高。于1990提出了R*樹。R*樹相對于R樹優化的地方是強制重新插入算法,其思路是:當新的空間對象索引項的插入導致節點溢出時,選擇部分節點在同層節點間進行調整,以推遲節點分裂,從而達到優化R樹整體結構的目的?；赗*樹的空間索引算法提高了空間利用率,減少了節點分裂次數,但同時增加了CPU的計算代價。2.4 金字塔索引于1998年提出了金字塔方法,該方法基于一種特殊的優化高維數據的不均衡分割策略,其原理是先將d維空
11、間分成2d個金字塔,共享數據空間的中心點為頂點,然后再將每個金字塔分割成平行于金字塔基的數據頁。金字塔索引結構是將高維數據轉化為一維數據,利用B+樹進行操作。金字塔索引結構的優點是當處理范圍查詢時,這種索引結構的性能優于其他的索引結構,而且查詢處理效率不會隨著維數的增加而降低,原因在于在處理范圍查詢時充分利用了金字塔空間中相近的點在B+樹中更有可能在B+樹的同一個數據頁上這個事實。但金字塔索引結構的優點是基于均勻數據分布和超立方體查詢的,對于那些覆蓋數據空間邊界的查詢不是很理想,而現實世界中的數據很少是服從均勻分布的。3結論在這些索引中,不同的索引有各自的優點和缺點以及適用范圍。需要選取哪種空
12、間索引方法,要根據實際情況和需求來確定。實際應用中也是采用多種索引結構的方法,取長補短。高效的空間索引方法一直是很多學者專家研究的課題,有很多問題需要進一步的解決的例如高效索引樹算法的改進、復雜空間查詢方法的優化以及查詢插入操作中算法的優化。參考文獻:1 吳信才.地理信息系統原理與方法M.北京:電子工業出版社,2002.2 郭際元.空間數據庫M.3 吳永英,張吉根,李晨陽.金字塔多維索引分析及其算法實現J.計算機工程與科學,2006,28.4 陳敏.GIS空間索引技術探究J.福建電腦,2005,8.5 梁浩,吳敏軍.兩類典型空間GIS索引技術的分析與評測J.安陽工學院學報,2006,20(4..R-tree:gC.,1984,47-57.