大型空间数据库的并发索引策略 CQR树

R 树是目前最流行的动态空间索引结构之一。多用户并发环境下 ,现有的 R 树并发控制算法 ,如 R2link 树[1 ] 及其改进算法[2 ] ,改变了 R 树存储结构 ,在原始 R 树的基础上添加控制信息 ,不易与现有系统的 R 树结合 ;纯粹基于加锁的控制算法[3 ] ,使得并发处理更为复杂 , 而且容易出现死锁。这些算法都不适合海量空间数据的并发操作。本文提出了适用于客户端方式空间数据库引擎并发控制的空间索引结构 ———CQR 树。将静态 R 树与四叉树相结合 ,四叉树编码与空间对象绑定管理被编辑过的对象 ,仅在删除叶子结点包中的对象时对索引包加锁 ,缩短系统响应时间。

1 　空间数据引擎与空间索引

目前的空间数据库扩展大多采用 R 树及其变种建立数据集的空间索引。从提供方来看 ,可以把空间数据引擎或空间扩展分为数据库平台和GIS 平台两类。或者不局限于 GIS 平台 ,分为数据库方和非数据库方。空间索引与空间数据引擎或空间扩展的结合也可以据此分为内嵌式和外挂式两类[4 ] 。

内嵌式空间索引内置于数据库内核 ,直接操

纵空间数据类型。由数据库方提供的空间扩展多提供内嵌式空间索引 ,如 Oracle Spatial 的 R 树 , IBM DB2 和 Informix 的网格索引和 R 树 , Po st2 GIS 的 GIST R 树等。外挂式空间索引的创建和维护都独立于数据库管理系统而自行管理。由GIS 平台提供的空间数据引擎多提供外挂式空间索引 ,如 ESRI ArcSDE 的三级格网索引 , Super2 Map SDX + 提供的混合索引等 , GRASS 平台提供的是外挂文件式的 R 树索引。外挂式索引灵活可控 ,能够选择各种类型的空间索引加以实现 ,但却无法借助数据库的先进功能 ,对于数据的频繁更新和并发操作均有不利影响。

1. 1 　空间数据引擎的外挂 R 树索引

在 RDBMS 中对空间数据的访问主要有 3 种方式 :服务器方式、客户端方式和混合方式[ 5 ] 。本文主要针对客户端方式 ,空间数据引擎作为客户端接口 ,直接把空间请求转换成标准 SQL 命令发送到 RDBMS 上 ,并解释所返回的数据 ,见图 1。

在客户端对数据进行编辑更新的同时 ,空间数据引擎需要对空间索引进行维护。对 R 树索引而言 ,R 树的叶子节点即索引包通常以二进制方式存储在数据库中 ,更新时 ,首先确定需要更新的索引包 ,然后将索引包取到客户端内存 ,在内存中更新后 ,由空间数据引擎提交到数据库服务器端。如图 2 所示。

1. 2 　R 树存在的问题

由于多用户并发编辑同一索引包里的对象时 ,都是在客户端内存操作然后提交到数据库服务器 ,因此 ,多客户端对索引包的修改会被最后一个提交的结果覆盖 ,从而导致并发编辑对象“丢失”(实际上数据已经被更新 ,但由于在索引包中丢失信息导致索引不到该对象) 或结果不正确。例如 ,客户端 A 和客户端 B 同时向索引包 R i 中添加对象 A k 、B k , 后更新的 B k 将覆盖先更新的A k 在索引包中的数据 ,导致 A k“丢失”。

这种情况虽然可以通过对索引表 (见图 2) 加行级锁来解决 ,但在 R 树中 ,由于关键字是非排序的甚至可能是相互重叠的 ,而且每个更新操作还需要频繁地进行数据的向上回溯 ,因此仅仅采用加锁机制将使得并发处理更为复杂而且容易出现死锁。R2link 树是为解决 R 树的并发控制问题而提出的 ,它在 R 树的基础上增加相关控制辅助信息 ,从而允许各种操作并发执行而不会出现死锁 ,但它的数据结构复杂 ,且仍然存在海量数据R 树维护困难的问题。

外挂模式下海量数据的 R 树更新操作还存在操作费时及索引边界外对象难以维护的问题。对海量空间数据而言 ,其他参数一定的条件下 ,R树的深度剧增 ,确定需要更新的叶子节点以及节点分裂等操作都比较复杂费时 ,尽管可以通过增加 R 树叶子节点的容量来降低 R 树的高度 ,但是 ,叶子节点容量的增加会导致索引包增大 ,加大了客户端访问数据时的通信量。R 树索引根结点的范围一定 ,当编辑的对象在此范围之外时 ,涉及R 树的一系列复杂操作 ,尤其当 R 树深度较深时 ,这种操作更加难以维护。因此 ,单纯的 R 树索引并不能满足海量数据并发编辑的要求。

更多内容请查看pdf