一種支持多版本空間數據的索引方法

張亞軍，華一新

(信息工程大學地理空間信息學院，河南鄭州450052)

一、引 言

在具有版本管理功能的地理信息系統中，多版本空間數據一般采用空間數據庫來管理［1-2］。隨著空間數據庫的不斷更新，空間數據在不同時間段對應著不同的版本［3］(如圖1所示)。

圖1 多版本空間數據示意圖

為了實現對不同版本空間數據的快速檢索，建立其空間數據庫索引是關鍵。

二、現狀分析

目前，空間數據庫常用的索引方法有格網索引、四叉樹索引和R樹系列索引3種［4-5］，這方面的研究相對比較成熟，基本思想都是對研究的空間區域進行劃分(如圖2所示)，用最小外接矩形(MBR)來代替空間對象的形態參與計算，算出每個劃分區域所對應的索引號以及空間對象所對應的索引號。其中區域劃分和索引號編碼是算法的核心，研究成果較多［4-8］，本文不再贅述。

圖2 區域劃分示意圖

由上圖可以看出，格網索引和四叉樹索引屬于靜態索引，在計算索引號時空間區域大小保持不變，用戶在進行空間數據更新導致版本提升時不能超出該區域范圍，否則區域大小的改變會引起整個索引的重建。圖3以格網索引為例，數據庫更新前線狀目標 L 由點 P0、P1、P2、P3、P4、P5組成，原始空間區域為R0，計算其經過的格網如圖中所示。如果用戶修改線狀目標L(例如增加點P6)得到一個新版本，則修改后的空間區域變為R1，此時區域R0中已經計算的索引號就會隨著區域R1的產生而變化，極端情況下需要對整個空間區域中的目標進行索引重建。因此，對多版本空間數據的索引屬于動態索引，其索引隨版本提升而動態變化。

由于R樹索引對空間區域采用的是動態劃分，因此比較適合隨時間動態變化數據庫的索引，研究也較多［9-10］。但對于格網和四叉樹而言，就必須解決靜態與動態之間的平衡。為此本文對格網和四叉樹索引算法進行了改進，提出了一種支持多版本空間數據的索引方法——固定網格大小空間索引。

三、固定網格大小空間索引

1.索引的基本思想

固定網格大小空間索引方法的基本思想是：根據原始數據大小來確定網格大小，并記錄數據的中心點或質心的坐標;然后根據由里向外“螺旋形編碼”的原則對每一個空間數據進行映射編碼(如圖4所示)。

圖4 固定網格大小索引方法

對于格網索引，因為編碼是由里向外的，并且中心點或質心固定，所以對數據庫中的空間數據來說，只要其位置不變，索引號也就永遠不變且唯一;如果其位置發生改變則可以重新計算得到一個新的索引編碼，這種編碼在其生命周期中也是不變的。除空間數據本身的修改外，還存在另一應用環境，就是新增加一個地理實體。依據“固定網格大小索引”的思路，該新增加的數據在整個空間區域的劃分中也唯一對應一個索引編碼，索引的關鍵就是每個格網及對應編碼的解算。因此對格網索引來說，采用該方法能有效解決目標動態變化的索引問題，較好地滿足了數據庫中多版本空間數據索引維護要求。

對于四叉樹索引，傳統四叉樹編碼是遞歸地把空間區域分成四等分。但固定網格大小索引思想是空間區域大小可以任意變化，因此必須采用反向區域劃分方法(如圖5所示)。

圖5 四叉樹反向區域劃分

圖中顯示了兩層和三層的四叉樹反向區域劃分方法，反向區域劃分是從四叉樹的最低層進行區域劃分，最低層劃分的基準格子大小為“固定格網大小”，逐步向上，每向上一層基準格子大小乘以2，并且每一層都采用固定網格大小索引的編碼方式。四叉樹的根結點編碼永遠為0，其他層每個結點的編碼算法描述如下。

假設某個結點位于四叉樹的第n層，其固定網格大小索引計算的編碼為num，那它的編碼Index為：Index=n*para+num，其中para是常量，取值不小于四叉樹最低層最大的編碼值。通過編碼算法就可計算出數據庫中每個空間數據所對應的編碼或索引號，計算的方向是從下到上、由里向外。

2.方法的實現過程

通過上面內容的分析可知，固定網格大小空間索引方法的實現主要是數據庫中空間數據索引號的建立、更新和刪除3個主要部分。

(1)數據庫中索引原理

與文件空間索引不同，基于數據庫的空間索引不能直接操縱磁盤，很難對數據庫內核中索引算法進行改進，只能通過映射的索引號間接實現對空間數據的索引(如圖6所示)。

圖6 數據庫中空間索引建立示意圖

圖中空間數據庫中的土地利用數據表(假設表名為soil)通過空間數據到索引號的映射算法計算出每塊土地數據所對應的索引號，并記錄在表中的SDI字段中。如果GIS客戶端計算出所查詢空間范圍所對應的SDI值(假設為66)，那么在GIS平臺就可以通過SQL語句“select* from soil where SDI=66”來檢索數據庫中所需地塊數據。

由此可見，在數據庫中，空間數據索引的關鍵就是設置某一列索引號的值，

(2)數據庫中索引號的建立與更新

對于格網和四叉樹索引來說，該方法使得索引號的計算只與空間目標本身有關，而與地理數據庫中數據量無關，依據該索引方法可以直接計算出空間目標的索引號。假設空間目標的MBR為B=(W，H)，空間區域更新后的 MBR 為R=(Rw，Rh)，固定格網大小為b=(w，h)。以四叉樹索引為例，計算索引號的步驟為：

(1)計算四叉樹索引的層次L

(2)計算目標對應的索引號I

利用反向區域劃分的方法，計算目標對應的最小四叉樹層次l為

然后利用“從下到上、由里向外”的原則，從l到L層計算當前層次所對應的格網大小及對應的編碼值，并判斷目標的MBR是否完全落入所計算的格網中，如果落入則算法終止，此時格網對應的編碼值，即為目標所對應的索引號。

算法的流程圖如圖7所示。

圖7 計算目標索引號算法流程圖

在數據庫中索引號的建立和更新相對比較簡單。假設存儲的表為T1，空間目標的唯一標識為f1，計算的索引號為i1，那么就可以通過SQL語句“update T1set sdi=i1where fid=f1”建立和更新目標的索引號。

(3)數據庫中索引號的刪除

對于采用固定網格大小的空間索引的數據庫來說，空間目標的刪除與其他目標索引號沒有任何關系，因此直接刪除目標即可，不需要附加任何其他的索引號更新操作。

3.方法的適用度

固定網格大小的空間索引方法是在空間目標不斷更新的需求下提出的，因此比較適合于隨時間不斷變化的空間數據庫索引的構建。不管空間數據庫的目標的增加，還是歷史數據的保留，都能夠很好地適應空間目標對數據庫索引的要求。

對于格網索引，為了使目標索引號保持唯一，對于點狀目標比較適用。四叉樹對于線狀和面狀目標適用度更好。

四、效率分析

在基于數據庫的海量空間數據更新應用中，通過固定網格大小的空間索引方法，本文采用MySQL5.0數據庫，對全國城鎮、交通、政區和水系4類數據進行試驗，其數據特征如表1所示。

表1 試驗數據的特征

試驗的功能是3種更新操作，即增加、刪除和平移某個空間目標，前置條件為3種操作都會引起整個空間區域的變化，與常用格網、四叉樹索引維護所消耗時間對比如表2所示。

表2 索引維護所消耗時間對比

從表2可以看出，采用固定網格索引方法明顯要比不采用要快得多。

對于固定網格大小空間索引方法，同一種數據采用不同索引方式，在數據處理效率上存在一定的差異。在上面試驗條件的基礎上，以交通數據為例，試驗結果如表3所示(時間單位為秒)。

表3 同種數據采用不同索引效率對比

從表3可以看出，對于同種數據采用不同的索引方法，對檢索空間數據的效率影響不大，但對索引的構建，索引的更新效率影響明顯，最大相差可達數十倍之多。

五、結 論

針對版本管理中空間數據庫動態性的特點，提出了固定網格大小空間索引方法，并對該方法的執行效率做了試驗，得出以下幾個方面的結論：

1)該索引算法針對的是空間數據庫動態更新時索引的構建，因此適合對多版本空間數據的索引。

2)索引算法的選擇對多版本空間數據的訪問效率影響不大，但對于索引的建立和維護影響較深。

3)索引編碼的選擇對訪問效率沒有影響，只影響構建檢索語句(SQL語句)的長度。

試驗結論表明該方法提高了GIS系統對空間數據庫中多版本空間數據處理能力和獲取效率，達到快速響應用戶空間查詢的目的。

［1］ESRI.Modelling Our World［M］.USA：ESRI Press，1999.

［2］萬波，周順平，陳波，等.基于 DBMS的MAPGIS7.0版本管理的設計與實現［J］.地球科學：中國地質大學學報，2006，31(5)：600-604.

［3］張亞軍，趙軍喜，丁昊.空間數據版本管理的體系結構研究［J］.測繪科學，2011，36(6)：155-157.

［4］PAUL A L，MICHAEL FG，DAVID J M，et al.地理信息系統科學［M］.北京：機械工業出版社，2007：205.

［5］SHASHI S，SANJAY C，謝昆青，等.空間數據庫［M］.北京：機械工業出版社，2003：114.

［6］顧軍.R-Tree空間索引的優化研究［D］.南京：南京師范大學，2002.

［7］吳敏君，郭永洪，陳天滋.一種有效的混合空間索引機制［J］.計算機工程與應用，2006(29)：193-197.

［8］郭菁，郭薇，胡志勇.大型GIS空間數據庫的有效索引結構 QR樹［J］.武漢大學學報：信息科學版，2003，28(3)：306-310.

［9］尹章才，李霖.基于快照-增量的時空索引機制研究［J］.測繪學報，2005，34(3)：257-261.

［10］尹章才，李霖，王琤.基于HR-樹擴展的時空索引機制研究［J］.武漢大學學報：信息科學版，2007，32(12)：1131-1134.