張亞軍，華一新

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

一、引 言

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

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

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

二、現(xiàn)狀分析

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

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

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

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

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

1.索引的基本思想

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2)計(jì)算目標(biāo)對(duì)應(yīng)的索引號(hào)I

利用反向區(qū)域劃分的方法，計(jì)算目標(biāo)對(duì)應(yīng)的最小四叉樹層次l為

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

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

圖7 計(jì)算目標(biāo)索引號(hào)算法流程圖

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

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

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

3.方法的適用度

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

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

四、效率分析

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

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

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

表2 索引維護(hù)所消耗時(shí)間對(duì)比

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

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

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

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

五、結(jié) 論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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