一種支持多版本空間數(shù)據(jù)的索引方法

張亞軍，華一新

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

一、引 言

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

圖1 多版本空間數(shù)據(jù)示意圖

為了實現(xiàn)對不同版本空間數(shù)據(jù)的快速檢索，建立其空間數(shù)據(jù)庫索引是關鍵。

二、現(xiàn)狀分析

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

圖2 區(qū)域劃分示意圖

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

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

三、固定網(wǎng)格大小空間索引

1.索引的基本思想

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

圖4 固定網(wǎng)格大小索引方法

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

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

圖5 四叉樹反向區(qū)域劃分

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

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

2.方法的實現(xiàn)過程

通過上面內(nèi)容的分析可知，固定網(wǎng)格大小空間索引方法的實現(xiàn)主要是數(shù)據(jù)庫中空間數(shù)據(jù)索引號的建立、更新和刪除3個主要部分。

(1)數(shù)據(jù)庫中索引原理

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

圖6 數(shù)據(jù)庫中空間索引建立示意圖

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

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

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

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

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

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

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

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

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

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

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

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

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

3.方法的適用度

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

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

四、效率分析

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

表1 試驗數(shù)據(jù)的特征

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

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

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

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

表3 同種數(shù)據(jù)采用不同索引效率對比

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

五、結 論

針對版本管理中空間數(shù)據(jù)庫動態(tài)性的特點，提出了固定網(wǎng)格大小空間索引方法，并對該方法的執(zhí)行效率做了試驗，得出以下幾個方面的結論：

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

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

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

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

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

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

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

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

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

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

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

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

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

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