基于多層索引的空間數(shù)據(jù)版本管理系統(tǒng)

彭 成

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

0 引言

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

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

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

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

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

導(dǎo)入空間數(shù)據(jù)文件時(shí)，創(chuàng)建以下用于空間數(shù)據(jù)存儲(chǔ)的數(shù)據(jù)庫(kù)表：版本樹表，主表，版本表，數(shù)據(jù)變更表，這些庫(kù)表的關(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 索引及緩沖隊(duì)列創(chuàng)建

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

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

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

1.3 初始版本建立

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

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

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

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

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

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

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

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

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

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

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

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

3 主版本演進(jìn)

空間數(shù)據(jù)的主版本演進(jìn)涉及表級(jí)版本和索引級(jí)版本，主要包含的操作有空間數(shù)據(jù)的再次導(dǎo)入、索引配置變更、選擇表級(jí)版本進(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ù)的備份，如果沒(méi)有備份，則將三個(gè)主表所有記錄復(fù)制到版本表，操作類型字段賦值為“無(wú)操作”，版本類型字段賦值為“表級(jí)版本”，版本號(hào)為當(dāng)前空間數(shù)據(jù)版本號(hào)；然后刪除主表中所有記錄，生成一條新的版本記錄添加到版本樹中，其中父級(jí)版本號(hào)的值為當(dāng)前版本號(hào)，并將此版本作為當(dāng)前版本。然后將另一版本的空間數(shù)據(jù)寫入主表，寫入的方式與1.3中向三個(gè)主表導(dǎo)入方式相同。

3.2 索引配置變更

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

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

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

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

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

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

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

4.2 記錄級(jí)變更的合并

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

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

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

4.3 記錄級(jí)變更的提交

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

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

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

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

圖4 記錄級(jí)變更軟件效果

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

圖5 圖元版本表變更

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

圖6 屬性版本表變更

索引版本表中新增了多條記錄，如圖7所示，“圖元ID”（圖元編號(hào)）為146的記錄表示刪除的南極洲圖元，對(duì)于刪除的圖元，將這個(gè)圖元對(duì)應(yīng)的每條索引生成一條表示索引刪除的記錄添加到索引版本表中，“opttype”（操作類型）值為8，表示刪除；“圖元ID”（圖元編號(hào)）為147的記錄表示新增的多邊形圖元，對(duì)于新增的圖元，計(jì)算其所對(duì)應(yīng)的索引添加到索引版本表中，“opttype”（操作類型）值為2，表示新增；“圖元ID”（圖元編號(hào)）為106的記錄表示移動(dòng)的澳大利亞圖元，索引版本表中記錄的變化相當(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é)點(diǎn)，則先找出從A到B的路徑所經(jīng)歷的所有版本。①路徑上沒(méi)有主版本：在版本表中找到這些版本所對(duì)應(yīng)的記錄，然后按照版本樹的順序，從A的第一個(gè)子節(jié)點(diǎn)開始，依次合并下一個(gè)子節(jié)點(diǎn)的增加、修改、刪除記錄集合，最終得到從A到B的增加、修改、刪除記錄集合，然后對(duì)當(dāng)前主表中的數(shù)據(jù)按照這個(gè)增加、修改、刪除集合做變更。②路徑上有主版本：先恢復(fù)到離B最近的主版本，然后按之前步驟進(jìn)行相同操作。

5.2 回溯方法

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

5.3 融合方法

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

5.4 刷新方法

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

6 結(jié)語(yǔ)

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

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