基于多層索引的空間數據版本管理系統

彭 成

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

0 引言

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

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

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

1 導入空間數據

1.1 數據庫表創建

導入空間數據文件時，創建以下用于空間數據存儲的數據庫表：版本樹表，主表，版本表，數據變更表，這些庫表的關系如圖1所示，主表與版本樹表關聯，版本表與主表關聯，數據變更表與主表關聯。

圖1 空間數據管理表結構

1.2 索引及緩沖隊列創建

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

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

對每個空間數據圖元外包矩形范圍，找到對應索引格子區域。其中索引格子分為渲染索引和查詢索引兩套，為每個圖元生成這兩套格子的索引記錄，并將部分數據和索引保留作為初始的內存緩沖隊列。

1.3 初始版本建立

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

2 空間數據渲染、查詢和修改

2.1 空間數據渲染

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

2.2 空間數據查詢

根據查詢所指定的區域，通過查詢索引得到其對應哪些查詢格子作為初步結果；接下來查詢區域是多邊形形狀的情況，獲取查詢所指定區域的內切矩形，對于內切矩形內的格子，其所有圖元都在查詢結果中；最后對于初步結果內的其他格子中的圖元，依次與查詢區域對比，保留有交集的對象，得到最終查詢結果。

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

圖2 空間數據查詢效果

2.3 空間數據修改

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

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

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

3 主版本演進

空間數據的主版本演進涉及表級版本和索引級版本，主要包含的操作有空間數據的再次導入、索引配置變更、選擇表級版本進行恢復。

3.1 空間數據的再次導入

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

3.2 索引配置變更

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

3.3 選擇表級版本恢復

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

4 分支版本演進

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

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

增加圖元或屬性時，會在內存的待新增圖元及屬性集合中添加所增加的圖元或屬性記錄，并計算圖元對應的索引，添加到內存的圖元及索引緩存中；修改圖元或屬性時，會在內存的待修改圖元及屬性集合中添加所增加的圖元或屬性記錄，并修改緩存中對應的圖元記錄，刪除圖元原有的索引緩存重新計算索引并添加到索引緩存；刪除圖元或屬性時，會在內存的待刪除圖元及屬性集合中添加所增加的圖元或屬性記錄，并在內存圖元及索引緩存中刪掉相應記錄。

4.2 記錄級變更的合并

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

圖3 記錄級變更規則流程

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

4.3 記錄級變更的提交

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

4.4 記錄級版本的創建

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

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

圖4 記錄級變更軟件效果

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

圖5 圖元版本表變更

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

圖6 屬性版本表變更

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

圖7 索引版本表變更

5 空間數據版本樹應用

空間數據的版本樹應用包括版本前進、版本回溯、版本融合、版本刷新。

5.1 前進方法

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

5.2 回溯方法

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

5.3 融合方法

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

5.4 刷新方法

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

6 結語

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

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