彭 成

（中國石油化工股份有限公司石油勘探開發(fā)研究院，北京 100083）

0 引言

地理信息技術(shù)的發(fā)展產(chǎn)生了大量的空間數(shù)據(jù)，其存儲和查詢效率是地理信息發(fā)展的瓶頸之一［1］。圖元數(shù)據(jù)的修改及數(shù)據(jù)版本的變更是地理信息數(shù)據(jù)處理領(lǐng)域最常見的場景［2］，如何設(shè)計高效的版本管理方法，也是地理信息系統(tǒng)發(fā)展需要解決的問題［3］。

目前成熟的地理信息系統(tǒng)商業(yè)軟件以關(guān)系型數(shù)據(jù)庫作為主要的存儲手段［4-5］。通過設(shè)計適用于地理信息空間數(shù)據(jù)模式的庫表結(jié)構(gòu)，來管理空間數(shù)據(jù)的復(fù)雜關(guān)系。一是數(shù)據(jù)庫企業(yè)在其各自的數(shù)據(jù)庫產(chǎn)品中增加了支持空間數(shù)據(jù)類型的專用軟件，如Oracle的Spatial Cartridge［6］；二是地理信息系統(tǒng)軟件企業(yè)在傳統(tǒng)的關(guān)系數(shù)據(jù)庫管理系統(tǒng)之上進(jìn)行功能和數(shù)據(jù)類型的擴(kuò)張，外加空間數(shù)據(jù)管理引擎，如ESRI的ArcSDE，Map-Info與Oracle公司的Oracle Spatial等［7］。在這一時期成熟的系統(tǒng)有加州大學(xué)Berkeley分校研制，后續(xù)開源的postgres［8］。

現(xiàn)有的空間數(shù)據(jù)存儲根據(jù)位置建立索引，當(dāng)查詢范圍較大時涉及的區(qū)域過多；范圍較小時又不需要比較索引區(qū)域中所有對象?，F(xiàn)有的版本管理，對于圖元的增刪改操作，也需要具有增量或整體替換等備份和恢復(fù)方式。針對上述問題，需要建立具有更加靈活索引，支持編輯備份及增量恢復(fù)的版本管理方法。

1 導(dǎo)入空間數(shù)據(jù)

1.1 數(shù)據(jù)庫表創(chuàng)建

導(dǎo)入空間數(shù)據(jù)文件時，創(chuàng)建以下用于空間數(shù)據(jù)存儲的數(shù)據(jù)庫表：版本樹表，主表，版本表，數(shù)據(jù)變更表，這些庫表的關(guān)系如圖1所示，主表與版本樹表關(guān)聯(lián)，版本表與主表關(guān)聯(lián)，數(shù)據(jù)變更表與主表關(guān)聯(lián)。

圖1 空間數(shù)據(jù)管理表結(jié)構(gòu)

1.2 索引及緩沖隊列創(chuàng)建

建立不同級別的索引分別用于支持查詢和渲染，默認(rèn)的渲染索引劃分方式為10乘10，渲染時根據(jù)屏幕范圍加載需要顯示的區(qū)域內(nèi)的空間數(shù)據(jù)。默認(rèn)的查詢索引劃分為20乘20，相比于渲染，查詢通常涉及的區(qū)域范圍要更小，所以設(shè)置更細(xì)索引以減少加載數(shù)據(jù)量。

緩沖隊列是將一部分空間圖元數(shù)據(jù)及索引放入內(nèi)存，以減少顯示和查詢時的數(shù)據(jù)庫讀取。其中每個圖元對應(yīng)一條數(shù)據(jù)庫記錄，以圖元為單位放入緩沖；對于索引，以劃分的格子為單位，每次放入緩沖是放入這個格子所包含的所有索引。

對每個空間數(shù)據(jù)圖元外包矩形范圍，找到對應(yīng)索引格子區(qū)域。其中索引格子分為渲染索引和查詢索引兩套，為每個圖元生成這兩套格子的索引記錄，并將部分?jǐn)?shù)據(jù)和索引保留作為初始的內(nèi)存緩沖隊列。

1.3 初始版本建立

導(dǎo)入空間數(shù)據(jù)時，在版本樹表中新增一條記錄表示當(dāng)前版本，然后將圖元形狀數(shù)據(jù)和屬性數(shù)據(jù)分別插入到主圖元表和主屬性表中。每個落在索引網(wǎng)格中或與其相交的圖元生成一條索引，添加到主索引表，索引表的建立可以使得查詢和顯示更加快速。

2 空間數(shù)據(jù)渲染、查詢和修改

2.1 空間數(shù)據(jù)渲染

根據(jù)屏幕所要渲染的范圍，獲取對應(yīng)的渲染索引格子，根據(jù)格子中索引獲取對應(yīng)的圖元數(shù)據(jù)并繪制。獲取圖元數(shù)據(jù)首先從緩沖隊列中查找，如果不存在，再從數(shù)據(jù)庫中加載。

2.2 空間數(shù)據(jù)查詢

根據(jù)查詢所指定的區(qū)域，通過查詢索引得到其對應(yīng)哪些查詢格子作為初步結(jié)果；接下來查詢區(qū)域是多邊形形狀的情況，獲取查詢所指定區(qū)域的內(nèi)切矩形，對于內(nèi)切矩形內(nèi)的格子，其所有圖元都在查詢結(jié)果中；最后對于初步結(jié)果內(nèi)的其他格子中的圖元，依次與查詢區(qū)域?qū)Ρ?，保留有交集的對象，得到最終查詢結(jié)果。

在本文例子中，給出一個多邊形的查詢范圍，查詢結(jié)果如圖2所示，左側(cè)為查詢結(jié)果列表，可以查看每個結(jié)果的屬性信息，當(dāng)前選中的對象在圖中以高亮顯示，如圖中選中的空間數(shù)據(jù)對象的名稱為“Niger”，空間數(shù)據(jù)對象編號為13，人口密度值為7.0。

圖2 空間數(shù)據(jù)查詢效果

2.3 空間數(shù)據(jù)修改

空間數(shù)據(jù)圖元的修改分為增刪改三種，存放到三個集合中，在提交時將這三個集合存放到數(shù)據(jù)庫中。

對于新增圖元，計算相應(yīng)的渲染和查詢索引，將圖元數(shù)據(jù)和兩套索引放入新增集合。對于刪除圖元，先找到其在內(nèi)存中的圖元記錄和兩套索引的記錄進(jìn)行刪除，然后將刪除的記錄存放于刪除集合。對于修改圖元，先找到其在內(nèi)存中的圖元記錄和兩套索引的記錄進(jìn)行修改，然后將修改前后的數(shù)據(jù)放入修改集合。

在提交時，對于新增集合，將其中的圖元和索引記錄直接提交到數(shù)據(jù)庫；對于刪除集合，將其中的圖元和索引記錄在數(shù)據(jù)庫中找到對應(yīng)記錄進(jìn)行刪除；對于修改集合，將其中的圖元和索引記錄在數(shù)據(jù)庫中找到對應(yīng)記錄進(jìn)行替換。

3 主版本演進(jìn)

空間數(shù)據(jù)的主版本演進(jìn)涉及表級版本和索引級版本，主要包含的操作有空間數(shù)據(jù)的再次導(dǎo)入、索引配置變更、選擇表級版本進(jìn)行恢復(fù)。

3.1 空間數(shù)據(jù)的再次導(dǎo)入

空間數(shù)據(jù)的再次導(dǎo)入是將當(dāng)前空間數(shù)據(jù)先進(jìn)行備份，然后導(dǎo)入另一版本的空間數(shù)據(jù)作為當(dāng)前的空間數(shù)據(jù)版本。具體的操作方法為，首先查詢版本表中是否有當(dāng)前空間數(shù)據(jù)的備份，如果沒有備份，則將三個主表所有記錄復(fù)制到版本表，操作類型字段賦值為“無操作”，版本類型字段賦值為“表級版本”，版本號為當(dāng)前空間數(shù)據(jù)版本號；然后刪除主表中所有記錄，生成一條新的版本記錄添加到版本樹中，其中父級版本號的值為當(dāng)前版本號，并將此版本作為當(dāng)前版本。然后將另一版本的空間數(shù)據(jù)寫入主表，寫入的方式與1.3中向三個主表導(dǎo)入方式相同。

3.2 索引配置變更

索引配置變更是修改索引網(wǎng)格的配置，然后重新計算并生成索引，同時備份原有索引。具體方法為用戶提交了新的索引網(wǎng)格配置后，將主索引表的所有記錄復(fù)制到索引版本表，操作字段類型為“無操作”，版本類型字段賦值為“索引級版本”，版本號為當(dāng)前空間數(shù)據(jù)版本號；然后刪除主索引表中所有記錄，生成一條新的版本記錄添加到版本樹中，其中父級版本號的值為當(dāng)前版本號，并將此版本作為當(dāng)前版本。然后計算新的索引并寫入索引表，計算和寫入方式與1.3中向主索引表導(dǎo)入方式相同。

3.3 選擇表級版本恢復(fù)

選擇表級版本恢復(fù)是將空間數(shù)據(jù)當(dāng)前版本恢復(fù)到用戶所選的版本，具體方法為，首先判斷當(dāng)前版本是否已經(jīng)備份過，如果沒有備份，則先備份當(dāng)前版本，方法與上面空間數(shù)據(jù)再次導(dǎo)入中備份當(dāng)前版本相同；接下來，更改版本樹表的“是否為當(dāng)前版本”字段，將用戶所選版本對應(yīng)的記錄更改為真，然后刪除主表所有記錄，將版本表中版本號為用戶所選版本的所有記錄復(fù)制到主表中。

4 分支版本演進(jìn)

分支版本演進(jìn)涉及記錄級版本，主要包含的操作有圖元和屬性的增加、修改、刪除，記錄級變更的合并，記錄級變更的提交，記錄級版本的創(chuàng)建。

4.1 圖元和屬性的增加、修改、刪除

增加圖元或?qū)傩詴r，會在內(nèi)存的待新增圖元及屬性集合中添加所增加的圖元或?qū)傩杂涗?，并計算圖元對應(yīng)的索引，添加到內(nèi)存的圖元及索引緩存中；修改圖元或?qū)傩詴r，會在內(nèi)存的待修改圖元及屬性集合中添加所增加的圖元或?qū)傩杂涗洠⑿薷木彺嬷袑?yīng)的圖元記錄，刪除圖元原有的索引緩存重新計算索引并添加到索引緩存；刪除圖元或?qū)傩詴r，會在內(nèi)存的待刪除圖元及屬性集合中添加所增加的圖元或?qū)傩杂涗?，并在?nèi)存圖元及索引緩存中刪掉相應(yīng)記錄。

4.2 記錄級變更的合并

記錄級變更的合并是將現(xiàn)有的增加、修改、刪除操作與之前的增加、修改、刪除操作進(jìn)行合并，在內(nèi)存的待新增圖元及屬性、待修改圖元及屬性，待刪除圖元三個集合以及數(shù)據(jù)變更表中都涉及到記錄級變更的合并。記錄級變更合并遵循的規(guī)則如圖3所示。

圖3 記錄級變更規(guī)則流程

其中“DELETE”“UPDATE”“ADD”分別表示刪除、修改、增加操作，“A/U/D表”表示增加/修改/刪除對應(yīng)的內(nèi)存中的集合或數(shù)據(jù)變更表，“刪A/U/D”表示在增加/修改/刪除對應(yīng)的內(nèi)存中的集合或數(shù)據(jù)變更表刪除對應(yīng)記錄，“添A/U/D”表示在增加/修改/刪除對應(yīng)的內(nèi)存中的集合或數(shù)據(jù)變更表添加對應(yīng)記錄，“改A/U/D”表示在增加/修改/刪除對應(yīng)的內(nèi)存中的集合或數(shù)據(jù)變更表修改對應(yīng)記錄。“有”和“無”表示是否在表中找到相同圖元編號的記錄。

4.3 記錄級變更的提交

記錄級變更的提交是將內(nèi)存中待新增圖元及屬性、待修改圖元及屬性，待刪除圖元及屬性集合提交到數(shù)據(jù)變更表中，提交時也遵循記錄級變更合并規(guī)則，其中操作版本字段賦值為當(dāng)前空間數(shù)據(jù)的版本號。同時對每個待新增、待修改、待刪除的圖元，計算相應(yīng)的索引，并提交到索引增加表和索引刪除表中。對于待新增圖元，根據(jù)圖元形狀位置生成相應(yīng)的索引提交到索引增加表中，對于待刪除圖元，根據(jù)圖元形狀位置生成相應(yīng)的索引提交到索引刪除表中，對于待修改圖元，根據(jù)修改前圖元形狀位置生成相應(yīng)的索引提交到索引刪除表中，再根據(jù)修改后圖元形狀位置生成相應(yīng)的索引提交到索引增加表中。記錄級變更提交時只合并當(dāng)前用戶的增加、修改、刪除操作。

4.4 記錄級版本的創(chuàng)建

記錄級版本的創(chuàng)建是將用戶所做的記錄及更改作為一個新的版本進(jìn)行存儲，具體的方法為：首先判斷內(nèi)存中待新增圖元及屬性、待修改圖元及屬性，待刪除圖元三個集合中是否有數(shù)據(jù)，如果有，則先進(jìn)行記錄級變更的提交。接下來，如果當(dāng)前空間數(shù)據(jù)版本在版本表中沒有備份，則將三個主表所有記錄復(fù)制到版本表。然后將數(shù)據(jù)變更表中的數(shù)據(jù)提交到主表和版本表中，提交到主表的方法為：對于圖元/屬性/索引增加表，將所有記錄增加到主圖元/屬性/索引表中；對于圖元/屬性修改表，將所有記錄在主圖元/屬性表中找到相應(yīng)記錄并進(jìn)行修改；對于圖元/屬性/索引刪除表，將所有記錄在主圖元/屬性/索引表中找到相應(yīng)記錄并進(jìn)行刪除。提交到版本表中的方法為：對于圖元/屬性/索引增加表，將所有記錄增加到圖元/屬性/索引版本表中，操作類型字段值為“增加”，版本類型字段值為“記錄級版本”；對于圖元/屬性修改表，將所有記錄增加到圖元/屬性版本表中，操作類型字段值為“修改”，版本類型字段值為“記錄級版本”；對于圖元/屬性/索引刪除表，將所有記錄增加到圖元/屬性/索引版本表中，操作類型字段值為“刪除”，版本類型字段值為“記錄級版本”。

在本文例子中，新增加了一個多邊形圖元，移動了澳大利亞的位置，刪除了南極洲，如圖4所示。將所做的修改提交并創(chuàng)建記錄級版本，版本號為1。

圖4 記錄級變更軟件效果

圖元版本表中新增了三條記錄，如圖5所示，其中“圖元ID”（圖元編號）為106的記錄表示移動的澳大利亞圖元，“version”（版本號）值1為新生成的記錄級版本版本號，“opttype”（操作類型）值為4表示移動，“versiontype”（版本類型）為0表示記錄級版本；“圖元ID”（圖元編號）為146的記錄表示刪除的南極洲圖元，對于刪除的圖元，只需記錄“version”（版本號）、“opttype”（操作類型）、“versiontype”（版本類型），其中“opttype”（操作類型）值為2表示刪除；“圖元ID”（圖元編號）為147的記錄表示新加的多邊形圖元，值為現(xiàn)有最大圖元編號146加1，“version”（版本號）值1為新生成的記錄級版本版本號，“opttype”（操作類型）值為1，表示新增，“versiontype”（版本類型）為0，表示記錄級版本。

圖5 圖元版本表變更

屬性版本表中新增了2條記錄，如圖6所示，“圖元ID”（圖元編號）為146的記錄表示刪除的南極洲圖元，對于刪除的圖元，只需記錄“version”（版本號）、“opttype”（操作類型）、“versiontype”（版本類型），其中“opttype”（操作類型）值為2表示刪除；“圖元ID”（圖元編號）為147的記錄表示新加的多邊形圖元，值為現(xiàn)有最大圖元編號146加1，“version”（版本號）值1為新生成的記錄級版本版本號，“opttype”（操作類型）值為1，表示新增，“versiontype”（版本類型）為0，表示記錄級版本，新加的圖元屬性字段也為空；對于修改的澳大利亞圖元，其屬性數(shù)據(jù)沒有變化所以沒有生成記錄。

圖6 屬性版本表變更

索引版本表中新增了多條記錄，如圖7所示，“圖元ID”（圖元編號）為146的記錄表示刪除的南極洲圖元，對于刪除的圖元，將這個圖元對應(yīng)的每條索引生成一條表示索引刪除的記錄添加到索引版本表中，“opttype”（操作類型）值為8，表示刪除；“圖元ID”（圖元編號）為147的記錄表示新增的多邊形圖元，對于新增的圖元，計算其所對應(yīng)的索引添加到索引版本表中，“opttype”（操作類型）值為2，表示新增；“圖元ID”（圖元編號）為106的記錄表示移動的澳大利亞圖元，索引版本表中記錄的變化相當(dāng)于執(zhí)行了刪除原有圖元然后在新位置新增同樣圖元兩步操作，所以生成了索引刪除的記錄及索引新增的記錄。

圖7 索引版本表變更

5 空間數(shù)據(jù)版本樹應(yīng)用

空間數(shù)據(jù)的版本樹應(yīng)用包括版本前進(jìn)、版本回溯、版本融合、版本刷新。

5.1 前進(jìn)方法

假設(shè)現(xiàn)有版本為A，要變成版本B，其中B在版本樹中為A的子孫節(jié)點，則先找出從A到B的路徑所經(jīng)歷的所有版本。①路徑上沒有主版本：在版本表中找到這些版本所對應(yīng)的記錄，然后按照版本樹的順序，從A的第一個子節(jié)點開始，依次合并下一個子節(jié)點的增加、修改、刪除記錄集合，最終得到從A到B的增加、修改、刪除記錄集合，然后對當(dāng)前主表中的數(shù)據(jù)按照這個增加、修改、刪除集合做變更。②路徑上有主版本：先恢復(fù)到離B最近的主版本，然后按之前步驟進(jìn)行相同操作。

5.2 回溯方法

假設(shè)現(xiàn)有版本為A，要變成版本B，其中B在版本樹中為A的祖先節(jié)點，則先找出從B到A的路徑所經(jīng)歷的所有版本。①路徑上沒有主版本：在版本表中找到這些版本所對應(yīng)的記錄，然后按照版本樹的順序，從B的第一個子節(jié)點開始，依次合并下一個子節(jié)點的增加、修改、刪除記錄集合，最終得到從B到A的增加、修改、刪除記錄集合。然后對增加集合中的元素，在主表中刪除對應(yīng)記錄，對于修改和刪除集合中的元素，在版本表中先找版本B對應(yīng)的記錄中是否有相應(yīng)元素，如果找到，則用找到的記錄更新/添加到主表，如果找不到，繼續(xù)找B的父節(jié)點版本，直到全部找到為止。②路徑上有主版本：先恢復(fù)到離B最近的主版本，然后按之前步驟進(jìn)行相同操作。

5.3 融合方法

假設(shè)現(xiàn)有版本為A，要與另一個版本B融合，形成新的版本，先找到A和B的共同祖先節(jié)點C。①兩條路徑上都沒有主版本：計算出從C到A和從C到B的增加、修改、刪除記錄集合。合并這兩個集合，圖元編號重復(fù)的讓用戶決定選擇哪一個為有效的，最后得到融合的增加、修改、刪除記錄集合。然后將A回溯到版本C，再按融合后的增加、修改、刪除記錄集合進(jìn)行變更，得到融合版本D，其中D為C的子節(jié)點。②某條或兩條路徑上有主版本，無法融合。

5.4 刷新方法

假如其他用戶對空間數(shù)據(jù)進(jìn)行了更改并提交，當(dāng)前用戶想要獲取其他用戶修改后的空間數(shù)據(jù)，則可以使用版本刷新功能，具體的方法為清空當(dāng)前用戶在內(nèi)存中的待新增圖元及屬性、待修改圖元及屬性，待刪除圖元及屬性以及主表的緩存記錄，然后重新讀取主表中的數(shù)據(jù)加到緩存中。

6 結(jié)語

建立了多層索引，針對不同的渲染和查詢要求使用合適的索引級別；建立了內(nèi)存緩沖策略，對經(jīng)常使用的空間數(shù)據(jù)對象直接從內(nèi)存中給出，提升了效率。

實現(xiàn)空間記錄表級和記錄級版本的演進(jìn)，融合及回滾，支持圖元編輯的合并以及沖突處理；建立了版本的記錄級增量備份及恢復(fù)，版本樹的應(yīng)用為空間數(shù)據(jù)管理提供靈活支持。