一種分區域雙樹結構的空間資料庫索引方法
2023-12-01 21:10:56
專利名稱：一種分區域雙樹結構的空間資料庫索引方法
技術領域：
本發明涉及一種空間資料庫索引方法。主要用於解決空間數據索引效率和準確性的問題，屬於空間資料庫領域的技術。
背景技術：
空間索引的目的是為了在GIS系統中快速定位到所選中的空間要素，從而提高空間操作的速度和效率。空間索引的技術和方法是GIS關鍵技術之一，是快速、高效的查詢、 檢索和顯示地理空間數據的重要指標，它的優劣直接影響空間資料庫和GIS系統的整體性能。空間數據索引技術還處在不斷的發展和完善階段。目前對於空間數據索引技術及基於它的空間數據查詢還存在很多問題有待進一步解決，如高效索弓I算法的改進；複雜空間查詢方法的優化；查詢操作中幾何過濾方法；動態索引結構的建立等。傳統的數據索引技術有B-樹、B+-樹、二叉樹、ISAM索引、哈希索引等，這些技術都是針對一維屬性數據的主關鍵字索引而設計的，並不能直接應用於空間資料庫的索引。I、基於二叉樹的索引技術
基於二叉樹索引結構的典型範例有kd-樹、K-D-B-樹、LSD樹等。這種索弓I結構的典型 kd-樹一種二分索引樹結構，主要用於索引多維數據點，但對複雜的空間目標，如折線、多邊形、多面體等得索引卻必須採用近似方法和空間映射技術。由此針對空間關係的查詢效率非常低。為了能索引複雜的空間目標，一種是和索引二維空間目標的基於實體標誌重複存儲技術的Mkd-樹被踢出了；為了將kd-樹存儲組織到外存，將Kd-樹與B-樹結合，提出了 K-D-B樹；Skd-樹的提出避免了空間目標的重複存儲和空間映射，用空間目標的中心點來對空間目標集進行二分索引。但是所有這些方法對非點狀空間目標的索引效率都較低。2、基於B-樹的索引技術
B-樹及其變體，被廣泛應用於常規的資料庫管理系統之中，實踐證明其對大型資料庫的索引具有出色表現。目前的空間數據索引技術，很多都是基於B-樹，如Guttman提出的 R-樹。R-樹的思想是將空間目標及其索引空進用最小包圍矩形來近似表示，可以簡化計算、減少存儲空間；將空間上鄰近的目標組織在同一節點或同一分枝，可以減少外存訪問次數。然而由於允許區間的重疊，導致了搜索路徑的平均數量的增加，每一維的區間都要儲存，需要較多的存儲空間。為此，為了避免索引空間重疊的問題，之後提出了 R+-樹；為了減少了查詢對外存的訪問次數，出現了 Cell-樹等。總之這類索引結構需要解決的主要問題仍然是減少區域的重疊，提高搜索效率。3、基於哈希的格網技術
這種方法的基本思路是將索引空間劃分為相等或不相等的一些小方格網，與每個格網相關的空間目標則存儲在同一磁碟頁，而格網的訪問地址則可以直接通過求數組下標或某種算法得到。如Grid file, R-file等。這類方法主要用於索引多維空間點。4、空間目標排序法
其基本思想是將索引空間劃分為許多小的格子，然後每個格子指定一個唯一的數字活編碼，空間則用與其相交的一個或多個格子的數字來表示，或用與其相交格子的編碼求得另一唯一編碼來表示。實質是將k維空間的實體映射到一維空間。用一維的數值對多維的空間目標進行排序，常見的方法有位置鍵(Location Keys), Z-排序(Z_ording)等。
發明內容
技術問題本發明是針對空間資料庫索引方法的解決方案。主要用於解決空間數據索引效率和準確性的問題。技術方案本發明的方法是一種策略性的方法，通過將空間區域分塊，構建兩級空間索引樹，分步索引，達到提高索引效率和索引準確性的目的。一、體系結構
本發明分區域雙樹結構的索引方法是基於新構建的索引樹，該索引樹是由兩個空間索引樹組成的。第一個是擴展的R-樹，它是根據地理空間特徵來存放空間對象。第二個是空間關係索引樹，根據它是用來表示空間區域的空間關係。兩個空間索引樹由在節點上相應的指針連接。其體系結構如圖I所示。 擴展的R-樹擴展的R-樹是在R-樹的基礎上，構建一個平衡樹。它符合R -樹的基本條件。根據空間檢索的需要，R-樹的節點將被重新定義。定義擴展的R-樹的葉節點定義如下
(KI，*P)}，A)(I)
(I, *P)是R-樹葉節點中包含的一對數組，其中*P是空間對象的指針，I是索引空間對象的MBR。A是該空間區域包含的空間對象。定義擴展的R-樹的非葉子節點的定義如下
({(I，child _p*)}， R)(2)
({(I,child_p*)}，R)是R-樹非葉節點中包含的一對數組,其中孩子指針是指向下級節點的指針，I是所有孩子節點所涵蓋的MBR。R是空間關係的特徵向量。該擴展的R-樹具有樹下特點
I)設m(2〈=m〈=M/2)為節點包含索引項的最小數目(m通常取M/2，如果節點包含項目數小於m，則節點下溢，如果節點包含項目數大於M，則節點上溢)，在一層的MBR的數量必須滿足m彡η彡M的條件。換句話說，每一個空間區域至少包含m個MBR，最多包含M個MBR， 這自然限制了空間區域的面積，減少現場空間關係的計算複雜性。2)非葉節點的每個數組是其子節點的粗粒度的抽象。對於任何兩個相鄰層的節點，在第i層的節點代表第i+Ι層的粗粒度；相反第i+Ι層節點代表第i層的精細粒度。空間關係索引樹空間關係索引樹是上面擴展R-樹的一個補充,它反映了空間區域的關係，通過聚類將空間區域聚集在一起。在空間關係索引樹的每個節點上有一個指針， 指針指向相應的在擴展的R樹上具有相同的特徵向量的節點。空間關係檢索樹的構造是基於點的聚類原則。考慮的R-樹不僅可以執行基於地區的搜索，也可以執行基於點的搜索，在構建空間關係索引樹時，不但要具備R-樹的的構建規則，還要具備如下的規則
O空間關係索引樹的構建原則是點集的聚類。在最近距離的點應在同一節點，這意味著，類似的場景特徵向量應放在同一節點。
2)在空間關係索引樹的葉節點中的指針不指向實際的空間對象，而指向ER-樹的相應節點。3)類似空間場景的檢索是通過在空間關係索引樹中搜索最近的空間關係特徵點執行的。二、方法流程
1、查找方法
當要查找一個空間數據時，首先對其聚類，得其空間關係向量，查找所有與其重疊的空間目標或完全落入其的空間目標，必須對所有與其相交的子空間所關聯的索引樹進行查找操作，當找到與其相交的空間區域後，用R-樹的查找算法對其進行索引，如果此空間區域的葉子節點已經是孩子結點，則所引到的目標結點就是所要查找的數據；如果不是孩子結點，則再向下一級進行查找。具體方法描述如下
Algorithm Search (N, ff) //W為所要查找的數據矩形，N為在索引樹中結點的數據
矩形
Begin
R*: the space associated with W R: the space associated with N;
If R* is overlap with R Then
R—Search (N，W) ; //調用R-樹的查找算法 For Each child node of N Do Search (N. Child, W);
Else return;
End;
2、插入方法
當插入一個空間數據時，如果插入的結點位置已經是葉子結點，則直接用R-樹算法將其插入其中，如果插入的位置不是葉子結點，則判斷此位置的孩子結點是否包含所要插入的空間數據；如果包含，則繼續進行插入，如果不包含則直接插入到此結點位置。插入後重新調整空間關係。具體方法描述如下
Algorithm Insert (N. P) //將MBR為P的物體插入到節點為N的索引樹上 Begin
If N is a leaf node of the tree Then R—Insert (N，P);
Else
Begin
Il決定N的下一層空間是否包含P node of N Do
Found:=False;
For Each child Begin
R:=the space associated with N
child;
5If R contain P completely Then Begin
Found:=True;
Insert (N. child, P);
Break;
End;
End;
If Not Found Then R—Insert (N，P);
End;
End;
3、刪除方法
刪除方法當刪除一個數據時，如果刪除的結點位置已經是葉子結點，則直接用R-樹算法將其插入其中，如果刪除的位置不是葉子結點，則判斷此位置的孩子結點是否包含所要刪除的空間數據，如果包含，則繼續進行刪除，如果不包含則直接刪除數據。刪除後重新調整空間關係。方法描述如下
Algorithm Delete (N, P) //從結點N中刪除MBR為P的物體 Begin
If N is a leaf node of the tree Then
R—Delete (N，P) //調用R樹的刪除算法
Else
Begin
Found: =False; //決定N的下一層空間是否包含P
For Each child node of N Do
Begin
R:=the space associated with N』 s child;
If R contain P completely Then Begin
Found:=True;
Delete (N. P);
Break;
End;
End;
If Not Found Then R—Delete(N，P);
End;
End;
有益效果
本發明提出了一種新的空間數據索引的方法，針對空間數據索引時，當數據量很大、範圍很廣時索引效率非常低的問題，提出了一種解決方案。通過本方法構建空間索引樹，可以適當的提高空間索引效率和準確性，尤其當面對海量數據時，隨著數據量的增加，其索引時間的增加會逐漸減慢。
圖I 一般形式的空間索引樹結構2原始的空間分布圖
圖3由圖2所構建的空間索引樹結構圖。
具體實施方案以圖2的空間分布圖為例，首先構建索引樹，得圖3，然後對其進行查找，插入和刪除操作。I.查找方法
以圖2為例，給定查找矩形區域QR，首先對QR進行聚類，求得其空間關係特徵向量R*， 查找所有R*重疊的空間目標或完全落入R*的空間目標，必須對所有與R*相交的子空間所關聯的R樹進行查找操作。例如在圖(I)中，查找所有與R*重疊的數據矩形，過程如下
(1)搜索類似的空間區域R*與根結點RO的索引空間相交，因此在RO中查找，返回滿足查找要求的數據矩形內；
(2)R*與Rl不相交，不用繼續比較；
(3)R*與R2，R3的索引空間相交，因此在R2，R3中查找，返回滿足查找要求的數據矩形 B2. O, C3. I;
2.插入方法
以圖2為例，插入一個數據矩形，必須首先確定其屬於的最小子空間及其關聯結點，然後再將其插入到對應的R樹中。例如在上圖中，要插入數據矩形Al. 0，首先要求出它的數據子空間Rl，然後將其插入到Rl中。3.刪除方法
以圖2為例，刪除一個數據矩形，必須首先確定其屬於的最小子空間及其關聯結點，然後再將其從對應的R樹中刪除該數據矩形。例如在上圖中，要刪除數據矩形B2. 0，首先要確定包圍它的最小子空間R2，然後從R2中將它刪除。
權利要求
1.一種分區域雙樹結構的空間資料庫索引方法，其特點在於構建新的索引樹，該索引樹是由兩個空間索引樹組成的第一個是擴展的R-樹，它是根據地理空間特徵來存放空間對象；第二個是空間關係索引樹，根據它是用來表示空間區域的空間關係；兩個空間索引樹由在節點上相應的指針連接；空間關係索引樹是上面擴展R-樹的一個補充，它反映了空間區域的關係，通過聚類將空間區域聚集在一起，在空間關係索引樹的每個節點上有一個指針，指針指向相應的在擴展的R樹上具有相同的特徵向量的節點。
2.根據權利要求I所述的空間資料庫索引方法，其特點在於所述的擴展的R-樹是在 R-樹的基礎上，構建一個平衡樹，它符合R -樹的基本條件，根據空間檢索的需要，R-樹的節點將被重新定義，擴展的R-樹的葉節點定義為(KI，*P)}，A)，其中(I，*p)是R-樹葉節點中包含的一對數組，其中*P是空間對象的指針，I是索引空間對象的MBR，A是該空間區域包含的空間對象，擴展的R-樹的非葉子節點的定義為({(I，child _p*)}，R)，({(I， child_p*)}，R)是R-樹非葉節點中包含的一對數組,其中孩子指針是指向下級節點的指針，I是所有孩子節點所涵蓋的MBR，R是空間關係的特徵向量，索引空間對象的MBR和空間對象。
3.根據權利要求I所述的空間資料庫索引方法，其特點在於所述的空間關係索引樹是擴展R-樹的一個補充，它反映了空間區域的關係，通過聚類將空間區域聚集在一起，在空間關係索引樹的每個節點上有一個指針，指針指向相應的在擴展的R樹上具有相同的特徵向量的節點。
4.根據權利要求I所述的空間資料庫索引方法，其特點在於所述的索引方法包括a)查找方法當要查找一個空間數據時，首先對其聚類，得其空間關係向量，查找所有與其重疊的空間目標或完全落入其的空間目標，必須對所有與其相交的子空間所關聯的索引樹進行查找操作，當找到與其相交的空間區域後，用R-樹的查找算法對其進行索引， 如果此空間區域的葉子節點已經是孩子結點，則所引到的目標結點就是所要查找的數據； 如果不是孩子結點，則再向下一級進行查找；b)插入方法當插入一個空間數據時，如果插入的結點位置已經是葉子結點，則直接用R-樹算法將其插入其中，如果插入的位置不是葉子結點，則判斷此位置的孩子結點是否包含所要插入的空間數據；如果包含，則繼續進行插入，如果不包含則直接插入到此結點位置，插入後重新調整空間關係；c)刪除方法當刪除一個數據時，如果刪除的結點位置已經是葉子結點，則直接用 R-樹算法將其插入其中，如果刪除的位置不是葉子結點，則判斷此位置的孩子結點是否包含所要刪除的空間數據，如果包含，則繼續進行刪除，如果不包含則直接刪除數據，刪除後重新調整空間關係。
全文摘要
本發明涉及一種空間資料庫索引方法。主要用於解決空間數據索引效率和準確性的問題，該方法是一種策略性的方法，通過將空間區域分塊，構建兩級空間索引樹，分步索引，達到提高索引效率和索引準確性的目的。空間索引的技術和方法是GIS關鍵技術之一，是快速、高效的查詢、檢索和顯示地理空間數據的重要指標，它的優劣直接影響空間資料庫和GIS系統的整體性能。所設計的方法是基於新構建的索引樹，該索引樹是由兩個空間索引樹組成的。第一個是擴展的R-樹，它是根據地理空間特徵來存放空間對象。第二個是空間關係索引樹，根據它是用來表示空間區域的空間關係。兩個空間索引樹由在節點上相應的指針連接。
文檔編號G06F17/30GK102609530SQ20121003217
公開日2012年7月25日 申請日期2012年2月14日 優先權日2012年2月14日
發明者華瑜敏, 吳昊, 張登銀, 程春玲 申請人:江蘇新大誠信息技術有限公司