第３４卷第７期２００９年７月
武汉大学学报·信息科学版ＧｅｏｍａｔｉｃｓａｎｄＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅｏｆＷｕｈａｎＵｎｉｖｅｒｓｉｔｙ
Ｖｏｌ．３４Ｎｏ．７Ｊｕｌｙ２００９
文章编号：１６７１８８６０（２００９）０７０８５６０３
文献标志码：Ａ
大型空间数据库的并发索引策略犆犙犚树
周 芹１，２ 钟耳顺１ 黄耀欢３ 郭 会１，２
（１ 中国科学院地理科学与资源研究所，北京市大屯路甲１１号，１００１０１）（２ 中国科学院研究生院，北京市玉泉路甲１９号，１０００３９）
（３ 中国水利水电科学研究院水资源研究所，北京市车公庄西路２０号，１０００４４）
摘 要：提出了适用于客户端模式空间数据库引擎并发控制的空间索引结构———ＣＱＲ树，将静态Ｒ树与四叉树相结合，采用四叉树编码与空间对象绑定的方式管理被编辑过的对象，仅在删除叶子结点包中的对象时对相关索引包加锁，缩短系统响应时间。
算法简单易实现，在保证空间查询效率的前提下解决多客户端并发操作的问题，同时降低了索引的维护难度。
关键词：空间数据库；空间索引；并发控制；Ｒ树；四叉树中图法分类号：Ｐ２０８ Ｒ树是目前最流行的动态空间索引结构之
一。
多用户并发环境下，现有的Ｒ树并发控制算法，如Ｒｌｉｎｋ树［１］及其改进算法［２］，改变了Ｒ树存储结构，在原始Ｒ树的基础上添加控制信息，不易与现有系统的Ｒ树结合；纯粹基于加锁的控制算法［３］，使得并发处理更为复杂，而且容易出现死锁。
这些算法都不适合海量空间数据的并发操作。
本文提出了适用于客户端方式空间数据库引擎并发控制的空间索引结构———ＣＱＲ树。
将静态Ｒ树与四叉树相结合，四叉树编码与空间对象绑定管理被编辑过的对象，仅在删除叶子结点包中的对象时对索引包加锁，缩短系统响应时间。
１ 空间数据引擎与空间索引 目前的空间数据库扩展大多采用Ｒ树及其变种建立数据集的空间索引。
从提供方来看，可以把空间数据引擎或空间扩展分为数据库平台和ＧＩＳ平台两类。
或者不局限于ＧＩＳ平台，分为数据库方和非数据库方。
空间索引与空间数据引擎或空间扩展的结合也可以据此分为内嵌式和外挂式两类［４］。
内嵌式空间索引内置于数据库内核，直接操纵空间数据类型。
由数据库方提供的空间扩展多 提供内嵌式空间索引，如ＯｒａｃｌｅＳｐａｔｉａｌ的Ｒ树，ＩＢＭＤＢ２和Ｉｎｆｏｒｍｉｘ的网格索引和Ｒ树，ＰｏｓｔＧＩＳ的ＧＩＳＴＲ树等。
外挂式空间索引的创建和维护都独立于数据库管理系统而自行管理。
由ＧＩＳ平台提供的空间数据引擎多提供外挂式空间索引，如ＥＳＲＩＡｒｃＳＤＥ的三级格网索引，ＳｕｐｅｒＭａｐＳＤＸ＋提供的混合索引等，ＧＲＡＳＳ平台提供的是外挂文件式的Ｒ树索引。
外挂式索引灵活可控，能够选择各种类型的空间索引加以实现，但却无法借助数据库的先进功能，对于数据的频繁更新和并发操作均有不利影响。
１．１ 空间数据引擎的外挂Ｒ树索引 在ＲＤＢＭＳ中对空间数据的访问主要有３种方式：服务器方式、客户端方式和混合方式［５］。
本文主要针对客户端方式，空间数据引擎作为客户端接口，直接把空间请求转换成标准ＳＱＬ命令发送到ＲＤＢＭＳ上，并解释所返回的数据，见图１。
在客户端对数据进行编辑更新的同时，空间数据引擎需要对空间索引进行维护。
对Ｒ树索引而言，Ｒ树的叶子节点即索引包通常以二进制方式存储在数据库中，更新时，首先确定需要更新的索引包，然后将索引包取到客户端内存，在内存中更新后，由空间数据引擎提交到数据库服务器端。
如图２所示。
收稿日期：２００９０５０５。
项目来源：国家８６３计划资助项目（２００１ＡＡ１３５１９０）。
第３４卷第７期 周 芹等：大型空间数据库的并发索引策略ＣＱＲ树 ８５７ 图１ 空间数据引擎的外挂Ｒ树索引Ｆｉｇ．１ ＥｘｔｅｒｎＲｔｒｅｅｉｎＳｐａｔｉａｌＤａｔａｂａｓｅＥｎｇｉｎｅ 题而提出的，它在Ｒ树的基础上增加相关控制辅助信息，从而允许各种操作并发执行而不会出现死锁，但它的数据结构复杂，且仍然存在海量数据Ｒ树维护困难的问题。
外挂模式下海量数据的Ｒ树更新操作还存在操作费时及索引边界外对象难以维护的问题。
对海量空间数据而言，其他参数一定的条件下，Ｒ树的深度剧增，确定需要更新的叶子节点以及节点分裂等操作都比较复杂费时，尽管可以通过增加Ｒ树叶子节点的容量来降低Ｒ树的高度，但是，叶子节点容量的增加会导致索引包增大，加大了客户端访问数据时的通信量。
Ｒ树索引根结点的范围一定，当编辑的对象在此范围之外时，涉及Ｒ树的一系列复杂操作，尤其当Ｒ树深度较深时，这种操作更加难以维护。
因此，单纯的Ｒ树索引并不能满足海量数据并发编辑的要求。
２ 犆犙犚树 图２ 多客户端并发编辑时Ｒ树索引包更新过程Ｆｉｇ．２ ＵｐｄａｔｉｎｇＰｒｏｃｅｄｕｒｅｏｆＲｔｒｅｅＮｏｄｅｓｉｎ ＣｏｎｃｕｒｒｅｎｔＥｄｉｔｉｎｇＥｎｖｉｒｏｎｍｅｎｔ １．２ Ｒ树存在的问题由于多用户并发编辑同一索引包里的对象 时，都是在客户端内存操作然后提交到数据库服务器，因此，多客户端对索引包的修改会被最后一个提交的结果覆盖，从而导致并发编辑对象“丢失”（实际上数据已经被更新，但由于在索引包中丢失信息导致索引不到该对象）或结果不正确。
例如，客户端犃和客户端犅同时向索引包犚犻中添加对象犃犽、犅犽，后更新的犅犽将覆盖先更新的犃犽在索引包中的数据，导致犃犽“丢失”。
这种情况虽然可以通过对索引表（见图２）加行级锁来解决，但在Ｒ树中，由于关键字是非排序的甚至可能是相互重叠的，而且每个更新操作还需要频繁地进行数据的向上回溯，因此仅仅采用加锁机制将使得并发处理更为复杂而且容易出现死锁。
Ｒｌｉｎｋ树是为解决Ｒ树的并发控制问 ２．１ 犆犙犚策略在ＣＱＲ索引策略中，Ｒ树仅作为只读索引 结构，由四叉树维护编辑对象，且满足： １）犗＝犗ＲＴｒｅｅ∪犗ＱＴｒｅｅ；２）犗ＲＴｒｅｅ∩犗ＱＴｒｅｅ＝。
式中，犗ＲＴｒｅｅ为犚树管理的对象集合；犗ＱＴｒｅｅ为四叉树管理的对象集合，犗为对象空间。
极端情况下，如犗ＱＴｒｅｅ＝，即没有对数据进行编辑操作时，ＣＱＲ为一棵纯Ｒ树；当犗ＲＴｒｅｅ＝，即所有数据都被编辑过，ＣＱＲ为纯四叉树。
２．２ 算法描述ＣＱＲ策略中，由Ｒ树和四叉树共同完成索引的管理，Ｒ树为近似只读的索引结构，同时将对象的四叉树编码与对象在数据库中的记录绑定， 从而保证并发编辑的正确性。
首先，对静态数据建Ｒ树，编辑操作时，Ｒ树只负责将被编辑（包括插入、删除、更新）对象从索引 中删除，再计算编辑对象的四叉树编码，即编辑过 的对象均由四叉树负责管理，具体过程如下所示。
１）四叉树编码。
２）对象插入：①保持Ｒ树结构不变，对新对象犗犻计算编码；②锁定对象犗犻，更新其编码值。
３）对象更新：①在Ｒ树中查找对象犗犻所在的叶子节点犔犽；②锁定犔犽所在记录，从犔犽中删除对象犗犻，再写回数据库；③对对象犗犻计算编码；④锁定对象犗犻，更新其编码值。
４）对象删除：①在Ｒ树中查找对象犗犻所在 ８５８ 武汉大学学报·信息科学版 ２００９年７月 的叶子节点犔犽；②锁定犔犽所在记录，从犔犽中删除对象犗犻，再写回数据库。
２．３ 犆犙犚的空间查询策略 ＣＱＲ树实际上是由Ｒ树与四叉树共同管理空间数据，且保证各对象在Ｒ树和四叉树之间不重复、不丢失。
因此，ＣＱＲ的查询分为两个部分：Ｒ树查询犙ＲＴｒｅｅ和四叉树查询犙ＱＴｒｅｅ。
最终结果为两部分查询的并集犙＝犙ＲＴｒｅｅ∪犙ＱＴｒｅｅ。
３ 犆犙犚树性能分析 由于是Ｒ树和四叉树的混合查询，海量数据的ＣＱＲ树的空间查询效率介于Ｒ树与四叉树之 间，相比纯Ｒ树而言，ＣＱＲ的空间查询效率较慢；而相比四叉树而言，由于在数据量超大时，
四 叉树层数增加，构造ＳＱＬ语句将比较复杂而影响查询性能，因此，ＣＱＲ的查询将比纯四叉树查询快。
为测试ＣＱＲ树的查询性能，本文进行了实验性测试。
实验分别采用１００万个对象的规则分布面数据和１５０万个对象的全国道路图，在编辑数据占总数据的０％，０．５％，１％，１．５％，２％，２．５％，３％的情况下，对数据进行２００次随机查询，查询窗口为数据范围的１％～１０％。
规则数据的平均查询时间和查询总Ｉ／Ｏ对比见图３和图４。
全国道路数据的平均查询时间和查询总Ｉ／Ｏ对比见图５和图６。
图３ 规则数据 图４ 规则数据 图５ 实际数据 图６ 实际数据 查询时间对比 查询总Ｉ／Ｏ对比 查询时间对比 查询总Ｉ／Ｏ对比 Ｆｉｇ．３ ＣｏｍｐａｒｉｓｏｎｏｆＱｕ Ｆｉｇ．４ ＣｏｍｐａｒｉｓｏｎｏｆＩ／Ｏ Ｆｉｇ．５ ＣｏｍｐａｒｉｓｏｎｏｆＱｕ Ｆｉｇ．６ ＣｏｍｐａｒｉｓｏｎｏｆＩ／Ｏ ｅｒｙＴｉｍｅｓｏｎＲｅｇｕｌａｒＤａｔａＴｉｍｅｓｏｎＲｅｇｕｌａｒＤａｔａｅｒｙＴｉｍｅｓｏｎＲｅａｌｉｓｔｉｃＤａｔａＴｉｍｅｓｏｎＲｅａｌｉｓｔｉｃＤａｔａ 从测试结果来看，对均匀分布的数据，ＣＱＲ树的空间查询性能与纯Ｒ树相当，查询耗费的时间和磁盘Ｉ／Ｏ并没有随编辑数据的增加而迅速增加；但对于全国道路数据，当编辑的数据占总数据量的１％左右时，空间查询效率有所降低，尤其当查询窗口较大时，查询时间和磁盘Ｉ／Ｏ迅速增加。
因此，在不断对数据进行编辑之后，ＣＱＲ的空间查询效率会低于纯Ｒ树。
对经常需要编辑的数据，可以定期进行ＣＱＲ索引的重建，将由四叉树管理的对象委托给Ｒ树，同时将四叉树清空，即变成纯Ｒ树，以提高空间查询效率。
４ 结 语 ＣＱＲ树结合了Ｒ树和四叉树的优点，由Ｒ树管理静态数据，保证查询效率；由四叉树管理动态数据，对动态数据计算四叉树编码易于实现，编码与对象绑定解决并发编辑问题。
ＣＱＲ树不需要修改Ｒ树的数据结构，也不需要对Ｒ树进行频繁的加锁控制，能够很好地解决海量数据多客户端并发编辑的问题，空间查询效率介于纯Ｒ树与 纯四叉树之间。
当编辑的数据量达到一定比例时，可以将由四叉树管理的对象重新插入Ｒ树以提高查询效率。
参 考 文 献 ［１］ ＫｏｍａｃｋｅｒＭ，ＢａｎｋｓＤ．ＨｉｇｈＣｏｎｃｕｒｒｅｎｃｙｉｎＲｔｒｅｅｓ［Ｃ］．Ｔｈｅ２１ｓｔＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＶＬＤＢ，Ｚｕｒｉｃｈ，Ｓｗｉｔｚｅｒｌａｎｄ，１９９５ ［２］ 夏英．多维空间数据索引结构的并发控制方案［Ｊ］．重庆邮电学院学报，２００２，１４（１）：７３７７ ［３］ ＣｈｅｎＪＫ，ＨｕａｎｇＹＦ，ＣｈｉｎＹＨ．ＡＳｔｕｄｙｏｆＣｏｎｃｕｒｒｅｎｔＯｐｅｒａｔｉｏｎｓｏｎＲＴｒｅｅｓ［Ｊ］．ＩｎｆｒｏｍａｔｉｏｎＳｃｉｅｎｃｅ，１９９７，９８：２６３３００ ［４］ 张明波，陆锋，申排伟，等．Ｒ树家族的演变和发展［Ｊ］．计算机学报，２００５，２８（３）：２８９３００ ［５］ 陈俊华，宋关福，李绍俊．基于ＲＤＢＭＳ的空间数据库的设计与实现［Ｃ］．２００１年中国ＧＩＳ年会，成都，２００５ 第一作者简介：周芹，博士生。
主要研究方向为ＧＩＳ软件技术、空间数据库、空间索引。
Ｅｍａｉｌ：ｚｈｏｕｑ．０６ｂ＠ｉｇｓｎｒｒ．ａｃ．ｃｎ （下转第８６３页）
算法简单易实现，在保证空间查询效率的前提下解决多客户端并发操作的问题，同时降低了索引的维护难度。
关键词：空间数据库；空间索引；并发控制；Ｒ树；四叉树中图法分类号：Ｐ２０８ Ｒ树是目前最流行的动态空间索引结构之
一。
多用户并发环境下，现有的Ｒ树并发控制算法，如Ｒｌｉｎｋ树［１］及其改进算法［２］，改变了Ｒ树存储结构，在原始Ｒ树的基础上添加控制信息，不易与现有系统的Ｒ树结合；纯粹基于加锁的控制算法［３］，使得并发处理更为复杂，而且容易出现死锁。
这些算法都不适合海量空间数据的并发操作。
本文提出了适用于客户端方式空间数据库引擎并发控制的空间索引结构———ＣＱＲ树。
将静态Ｒ树与四叉树相结合，四叉树编码与空间对象绑定管理被编辑过的对象，仅在删除叶子结点包中的对象时对索引包加锁，缩短系统响应时间。
１ 空间数据引擎与空间索引 目前的空间数据库扩展大多采用Ｒ树及其变种建立数据集的空间索引。
从提供方来看，可以把空间数据引擎或空间扩展分为数据库平台和ＧＩＳ平台两类。
或者不局限于ＧＩＳ平台，分为数据库方和非数据库方。
空间索引与空间数据引擎或空间扩展的结合也可以据此分为内嵌式和外挂式两类［４］。
内嵌式空间索引内置于数据库内核，直接操纵空间数据类型。
由数据库方提供的空间扩展多 提供内嵌式空间索引，如ＯｒａｃｌｅＳｐａｔｉａｌ的Ｒ树，ＩＢＭＤＢ２和Ｉｎｆｏｒｍｉｘ的网格索引和Ｒ树，ＰｏｓｔＧＩＳ的ＧＩＳＴＲ树等。
外挂式空间索引的创建和维护都独立于数据库管理系统而自行管理。
由ＧＩＳ平台提供的空间数据引擎多提供外挂式空间索引，如ＥＳＲＩＡｒｃＳＤＥ的三级格网索引，ＳｕｐｅｒＭａｐＳＤＸ＋提供的混合索引等，ＧＲＡＳＳ平台提供的是外挂文件式的Ｒ树索引。
外挂式索引灵活可控，能够选择各种类型的空间索引加以实现，但却无法借助数据库的先进功能，对于数据的频繁更新和并发操作均有不利影响。
１．１ 空间数据引擎的外挂Ｒ树索引 在ＲＤＢＭＳ中对空间数据的访问主要有３种方式：服务器方式、客户端方式和混合方式［５］。
本文主要针对客户端方式，空间数据引擎作为客户端接口，直接把空间请求转换成标准ＳＱＬ命令发送到ＲＤＢＭＳ上，并解释所返回的数据，见图１。
在客户端对数据进行编辑更新的同时，空间数据引擎需要对空间索引进行维护。
对Ｒ树索引而言，Ｒ树的叶子节点即索引包通常以二进制方式存储在数据库中，更新时，首先确定需要更新的索引包，然后将索引包取到客户端内存，在内存中更新后，由空间数据引擎提交到数据库服务器端。
如图２所示。
收稿日期：２００９０５０５。
项目来源：国家８６３计划资助项目（２００１ＡＡ１３５１９０）。
第３４卷第７期 周 芹等：大型空间数据库的并发索引策略ＣＱＲ树 ８５７ 图１ 空间数据引擎的外挂Ｒ树索引Ｆｉｇ．１ ＥｘｔｅｒｎＲｔｒｅｅｉｎＳｐａｔｉａｌＤａｔａｂａｓｅＥｎｇｉｎｅ 题而提出的，它在Ｒ树的基础上增加相关控制辅助信息，从而允许各种操作并发执行而不会出现死锁，但它的数据结构复杂，且仍然存在海量数据Ｒ树维护困难的问题。
外挂模式下海量数据的Ｒ树更新操作还存在操作费时及索引边界外对象难以维护的问题。
对海量空间数据而言，其他参数一定的条件下，Ｒ树的深度剧增，确定需要更新的叶子节点以及节点分裂等操作都比较复杂费时，尽管可以通过增加Ｒ树叶子节点的容量来降低Ｒ树的高度，但是，叶子节点容量的增加会导致索引包增大，加大了客户端访问数据时的通信量。
Ｒ树索引根结点的范围一定，当编辑的对象在此范围之外时，涉及Ｒ树的一系列复杂操作，尤其当Ｒ树深度较深时，这种操作更加难以维护。
因此，单纯的Ｒ树索引并不能满足海量数据并发编辑的要求。
２ 犆犙犚树 图２ 多客户端并发编辑时Ｒ树索引包更新过程Ｆｉｇ．２ ＵｐｄａｔｉｎｇＰｒｏｃｅｄｕｒｅｏｆＲｔｒｅｅＮｏｄｅｓｉｎ ＣｏｎｃｕｒｒｅｎｔＥｄｉｔｉｎｇＥｎｖｉｒｏｎｍｅｎｔ １．２ Ｒ树存在的问题由于多用户并发编辑同一索引包里的对象 时，都是在客户端内存操作然后提交到数据库服务器，因此，多客户端对索引包的修改会被最后一个提交的结果覆盖，从而导致并发编辑对象“丢失”（实际上数据已经被更新，但由于在索引包中丢失信息导致索引不到该对象）或结果不正确。
例如，客户端犃和客户端犅同时向索引包犚犻中添加对象犃犽、犅犽，后更新的犅犽将覆盖先更新的犃犽在索引包中的数据，导致犃犽“丢失”。
这种情况虽然可以通过对索引表（见图２）加行级锁来解决，但在Ｒ树中，由于关键字是非排序的甚至可能是相互重叠的，而且每个更新操作还需要频繁地进行数据的向上回溯，因此仅仅采用加锁机制将使得并发处理更为复杂而且容易出现死锁。
Ｒｌｉｎｋ树是为解决Ｒ树的并发控制问 ２．１ 犆犙犚策略在ＣＱＲ索引策略中，Ｒ树仅作为只读索引 结构，由四叉树维护编辑对象，且满足： １）犗＝犗ＲＴｒｅｅ∪犗ＱＴｒｅｅ；２）犗ＲＴｒｅｅ∩犗ＱＴｒｅｅ＝。
式中，犗ＲＴｒｅｅ为犚树管理的对象集合；犗ＱＴｒｅｅ为四叉树管理的对象集合，犗为对象空间。
极端情况下，如犗ＱＴｒｅｅ＝，即没有对数据进行编辑操作时，ＣＱＲ为一棵纯Ｒ树；当犗ＲＴｒｅｅ＝，即所有数据都被编辑过，ＣＱＲ为纯四叉树。
２．２ 算法描述ＣＱＲ策略中，由Ｒ树和四叉树共同完成索引的管理，Ｒ树为近似只读的索引结构，同时将对象的四叉树编码与对象在数据库中的记录绑定， 从而保证并发编辑的正确性。
首先，对静态数据建Ｒ树，编辑操作时，Ｒ树只负责将被编辑（包括插入、删除、更新）对象从索引 中删除，再计算编辑对象的四叉树编码，即编辑过 的对象均由四叉树负责管理，具体过程如下所示。
１）四叉树编码。
２）对象插入：①保持Ｒ树结构不变，对新对象犗犻计算编码；②锁定对象犗犻，更新其编码值。
３）对象更新：①在Ｒ树中查找对象犗犻所在的叶子节点犔犽；②锁定犔犽所在记录，从犔犽中删除对象犗犻，再写回数据库；③对对象犗犻计算编码；④锁定对象犗犻，更新其编码值。
４）对象删除：①在Ｒ树中查找对象犗犻所在 ８５８ 武汉大学学报·信息科学版 ２００９年７月 的叶子节点犔犽；②锁定犔犽所在记录，从犔犽中删除对象犗犻，再写回数据库。
２．３ 犆犙犚的空间查询策略 ＣＱＲ树实际上是由Ｒ树与四叉树共同管理空间数据，且保证各对象在Ｒ树和四叉树之间不重复、不丢失。
因此，ＣＱＲ的查询分为两个部分：Ｒ树查询犙ＲＴｒｅｅ和四叉树查询犙ＱＴｒｅｅ。
最终结果为两部分查询的并集犙＝犙ＲＴｒｅｅ∪犙ＱＴｒｅｅ。
３ 犆犙犚树性能分析 由于是Ｒ树和四叉树的混合查询，海量数据的ＣＱＲ树的空间查询效率介于Ｒ树与四叉树之 间，相比纯Ｒ树而言，ＣＱＲ的空间查询效率较慢；而相比四叉树而言，由于在数据量超大时，
四 叉树层数增加，构造ＳＱＬ语句将比较复杂而影响查询性能，因此，ＣＱＲ的查询将比纯四叉树查询快。
为测试ＣＱＲ树的查询性能，本文进行了实验性测试。
实验分别采用１００万个对象的规则分布面数据和１５０万个对象的全国道路图，在编辑数据占总数据的０％，０．５％，１％，１．５％，２％，２．５％，３％的情况下，对数据进行２００次随机查询，查询窗口为数据范围的１％～１０％。
规则数据的平均查询时间和查询总Ｉ／Ｏ对比见图３和图４。
全国道路数据的平均查询时间和查询总Ｉ／Ｏ对比见图５和图６。
图３ 规则数据 图４ 规则数据 图５ 实际数据 图６ 实际数据 查询时间对比 查询总Ｉ／Ｏ对比 查询时间对比 查询总Ｉ／Ｏ对比 Ｆｉｇ．３ ＣｏｍｐａｒｉｓｏｎｏｆＱｕ Ｆｉｇ．４ ＣｏｍｐａｒｉｓｏｎｏｆＩ／Ｏ Ｆｉｇ．５ ＣｏｍｐａｒｉｓｏｎｏｆＱｕ Ｆｉｇ．６ ＣｏｍｐａｒｉｓｏｎｏｆＩ／Ｏ ｅｒｙＴｉｍｅｓｏｎＲｅｇｕｌａｒＤａｔａＴｉｍｅｓｏｎＲｅｇｕｌａｒＤａｔａｅｒｙＴｉｍｅｓｏｎＲｅａｌｉｓｔｉｃＤａｔａＴｉｍｅｓｏｎＲｅａｌｉｓｔｉｃＤａｔａ 从测试结果来看，对均匀分布的数据，ＣＱＲ树的空间查询性能与纯Ｒ树相当，查询耗费的时间和磁盘Ｉ／Ｏ并没有随编辑数据的增加而迅速增加；但对于全国道路数据，当编辑的数据占总数据量的１％左右时，空间查询效率有所降低，尤其当查询窗口较大时，查询时间和磁盘Ｉ／Ｏ迅速增加。
因此，在不断对数据进行编辑之后，ＣＱＲ的空间查询效率会低于纯Ｒ树。
对经常需要编辑的数据，可以定期进行ＣＱＲ索引的重建，将由四叉树管理的对象委托给Ｒ树，同时将四叉树清空，即变成纯Ｒ树，以提高空间查询效率。
４ 结 语 ＣＱＲ树结合了Ｒ树和四叉树的优点，由Ｒ树管理静态数据，保证查询效率；由四叉树管理动态数据，对动态数据计算四叉树编码易于实现，编码与对象绑定解决并发编辑问题。
ＣＱＲ树不需要修改Ｒ树的数据结构，也不需要对Ｒ树进行频繁的加锁控制，能够很好地解决海量数据多客户端并发编辑的问题，空间查询效率介于纯Ｒ树与 纯四叉树之间。
当编辑的数据量达到一定比例时，可以将由四叉树管理的对象重新插入Ｒ树以提高查询效率。
参 考 文 献 ［１］ ＫｏｍａｃｋｅｒＭ，ＢａｎｋｓＤ．ＨｉｇｈＣｏｎｃｕｒｒｅｎｃｙｉｎＲｔｒｅｅｓ［Ｃ］．Ｔｈｅ２１ｓｔＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＶＬＤＢ，Ｚｕｒｉｃｈ，Ｓｗｉｔｚｅｒｌａｎｄ，１９９５ ［２］ 夏英．多维空间数据索引结构的并发控制方案［Ｊ］．重庆邮电学院学报，２００２，１４（１）：７３７７ ［３］ ＣｈｅｎＪＫ，ＨｕａｎｇＹＦ，ＣｈｉｎＹＨ．ＡＳｔｕｄｙｏｆＣｏｎｃｕｒｒｅｎｔＯｐｅｒａｔｉｏｎｓｏｎＲＴｒｅｅｓ［Ｊ］．ＩｎｆｒｏｍａｔｉｏｎＳｃｉｅｎｃｅ，１９９７，９８：２６３３００ ［４］ 张明波，陆锋，申排伟，等．Ｒ树家族的演变和发展［Ｊ］．计算机学报，２００５，２８（３）：２８９３００ ［５］ 陈俊华，宋关福，李绍俊．基于ＲＤＢＭＳ的空间数据库的设计与实现［Ｃ］．２００１年中国ＧＩＳ年会，成都，２００５ 第一作者简介：周芹，博士生。
主要研究方向为ＧＩＳ软件技术、空间数据库、空间索引。
Ｅｍａｉｌ：ｚｈｏｕｑ．０６ｂ＠ｉｇｓｎｒｒ．ａｃ．ｃｎ （下转第８６３页）
声明：
该资讯来自于互联网网友发布，如有侵犯您的权益请联系我们。
