基于多层索引的空间数据版本管理系统

2022-03-02彭成

现代计算机 2022年23期

彭成

（中国石油化工股份有限公司石油勘探开发研究院，北京 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的子节点。②某条或两条路径上有主版本，无法融合。