动态编辑环境下绘制对象R*-树空间索引维护的优化方法

《Computer Aided Geometric Design》：An Optimization Method for R*-tree Spatial Index Maintenance in Dynamic Editing Environments for Drawing Objects

　　摘要：为应对CAD和矢量图形编辑环境中对象频繁修改所带来的空间索引维护难题，本研究分析了R*-树在动态更新过程中的结构响应特性。现有方法采用统一的删除-重新插入机制，未考虑几何变化的幅度，从而导致在高频、小规模更新情况下出现不必要的结构调整、累积干扰以及性能下降。为克服这一局限，我们提出了一种以稳定性为导向的动态索引维护方法。该方法引入与对象大小相对应的稳定区域，将连续的微小几何变化转化为基于阈值的结构调整。此外，还设计了一种分层控制机制，结合延迟更新、软删除和局部重建策略来调控更新过程，从而降低结构修改的频率和传播范围。实验结果表明，与传统R*-树相比，所提方法可将更新时间减少60%–72%（随着数据规模增大，该比例可稳定在70%左右），节点重新插入次数减少14%–18%，节点重叠率降低2%–5%，同时查询性能仍保持在±5%以内。另外，稳定区域机制还将结构重组触发的次数减少了85%–92%。这些结果表明，所提方法能有效减轻结构干扰，提升高频动态编辑环境中的索引维护效率。

引言：随着GIS、CAD和空间数据库的发展，多维空间数据的有效组织和检索已成为重要课题（Guttman，1984）。R树利用最小边界矩形对几何对象进行分层组织，在空间查询方面表现优异（Guttman，1984）。R*-树通过引入强制重新插入和优化分割策略进一步降低了节点重叠度（Beckmann等人，1990），而STR方法则从批量加载的角度提升了构建质量（Leutenegger等人，1997）。Gaede等人对多维访问方法进行了系统综述（Gaede和Günther，1998），张明波等人则回顾了R树家族的发展历程（Zhang等人，2005）。近期研究还拓展到了分布式、并行和机器学习方向：Samet系统阐述了多维数据结构（Samet，2006）；牛磊等人将希尔伯特曲线引入R*-树以优化室内疏散路径查询（Niu等人，2018）；Eldawy等人提出了SpatialHadoop，用于在MapReduce框架中实现空间索引功能（Eldawy和SpatialHadoop，2015）；Men等人研究了并行动态空间索引（Men，2021）；Kraska等人率先提出了机器学习索引的概念（Kraska等人，2018）；王一坦等人和蔡攀等人分别对机器学习索引结构进行了系统研究（Wang等人，2023）。这些研究为静态场景下的空间索引性能建立了基准。至于动态场景下的索引维护，现有研究主要涵盖三个层面：结构优化、更新机制改进以及存储架构发展。在结构方面，Hilbert R树利用空间填充曲线提升聚类效果（Kamel和Faloutsos，1994），X树优化了高维分割方式（Berchtold等人，1996），PR树则实现了最坏情况下的最优查询性能（Arge等人，2008）。在更新机制方面，LUR树通过延迟更新降低了移动对象的更新成本（Kwon等人，2002），LUMR*-树则通过延迟处理支持对象位置的频繁变化（Peng等人，2017），RUM树则通过周期性垃圾回收将更新转换为插入操作（Xiong和Aref，2006）。从存储架构角度来看，LSM树为写密集型场景提供了高效模型（O'Neil等人，1996），由此衍生出了如LSM-R树之类的变体，进一步提升写入吞吐量（Chen等人，2022）；陶涛等人提出了适用于高速公路环境的高效更新的时空索引（Tao和Liu，2015）。在自适应索引领域，AQWA框架能够根据工作负载情况动态调整分区策略（Aly等人，2015），AIR树则为具有空间范围的对象提供了自适应索引功能（Al-Mamun等人，2023）。在时空索引方面，MV3R树支持基于时间戳的查询（Tao和Papadias，2001），丁志明提出了DSTR-Tree，用于管理受网络限制的移动物体轨迹（Ding，2012）。在机器学习索引方面，Al-Mamun等人总结了多维机器学习索引结构的最新进展（Al-Mamun等人，2024）。值得注意的是，机器学习技术日益渗透到空间数据管理中。徐等人将深度强化学习应用于双操纵器路径规划中的碰撞检测（Xu等人，2025）；王等人提出了一种基于数据驱动的分支定界框架，用于电缆线束组装中的空间路由规划（Wang等人，2025）。这些研究表明，将学习机制融入空间优化中，能够更好地平衡适应性与效率，为未来将动态索引维护与基于学习的策略相结合提供了依据。然而，现有方法大多假设任何更新都会引发结构调整，未能根据变化幅度进行区分。在CAD编辑中，对象修改多为局部且规模较小，其空间影响远小于节点粒度，但R*-树仍通过删除-重新插入的方式统一处理这些修改（Beckmann等人，1990），从而导致过度的结构响应。连续的小规模更新可能引发“性能波动波”——突然的节点分裂会导致性能出现严重波动（Xing等人，2021）；CondenseTree算法还会进一步加剧这种扰动（Beckmann和Seeger，2009）。问题的核心在于“几何变化”与“结构响应”之间缺乏尺度匹配和缓冲机制。现有的延迟更新方法（Kwon等人，2002）主要针对移动对象的位置更新，未能有效处理CAD中常见的形状变化。本文提出了一种以结构稳定性为导向的R*-树动态维护方法，其核心思想是在不改变底层索引结构的前提下重构更新机制，建立变化幅度与结构响应之间的层级映射关系。主要贡献包括：（1）提出了一种以结构稳定性为导向的动态维护框架，构建了“局部吸收-结构重组”的两级响应模型。该模型根据几何变化的幅度将其引导至不同的处理路径，弥补了现有方法在更新尺度区分上的不足。（2）引入了与对象大小相对应的稳定区域以及相应的延迟更新机制。该机制将轻微扰动限制在叶节点内部，在那里进行局部吸收，仅进行必要的最小边界矩形传播调整，从而大幅降低“删除-重新插入”过程的触发频率。（3）提出了一种基于统计阈值的软删除和局部重建策略。通过延迟处理删除带来的扰动，该机制可抑制流量不足现象的传播，稳定节点利用率的变化趋势。

章节摘录：

R树空间索引结构：R树是一种分层式空间索引结构，它利用最小边界矩形对几何对象进行近似表示，并以树状方式组织多维数据，从而支持高效的空间查询。对于任意对象oi，其最小边界矩形可表示为：Roi(t)=[xmin,xmax]×[ymin,ymax]，其中[xmin,xmax]和[ymin,ymax]分别表示该矩形在各个维度上的边界范围。通过这种表示方式，复杂的几何对象可以被统一映射到……

动态编辑环境中的索引性能问题分析：在动态绘图编辑环境中，空间对象集合会随时间持续发生变化，这就要求索引结构能够支持高频的插入、删除和修改操作。本节首先分析了R*-树在动态更新过程中的维护机制及复杂度特征，随后从结构统计演变的角度探讨了性能下降的机制。

基于稳定区域的动态更新优化方法：为应对动态编辑环境中R*-树日益增加的索引维护成本以及结构稳定性的下降问题，本文提出了一种基于稳定区域控制的动态索引维护方法。该方法根据几何变化的幅度实施分层处理。稳定区域是指通过将对象的原最小边界矩形向外扩展一定比例而形成的容忍区域。当被修改对象的最小边界矩形保持不变时……

数据集与参数配置：实验中使用的绘图对象为用最小边界矩形均匀表示的二维矩形。需要说明的是，之所以使用合成数据而非真实的工程图纸，是因为所提方法仅依赖于每个对象的最小边界矩形，边界框之外的内部几何细节不会影响索引的构建或查询处理。如图9(a)所示，现实世界中的绘图对象——如机械零件等……

结论：本文针对CAD和矢量图形编辑等高频动态更新场景，分析了在“删除-重新插入”机制下R*-树的结构响应特性。研究表明，连续的小规模修改容易引发过度的结构调整，从而导致结构扰动累积和性能下降。为解决这一问题，本文提出了一种以结构稳定性为导向的动态索引维护方法。该方法……

数据可用性：数据将应要求提供。

未引用参考文献：（Cai等人，2023；Al-Mamun等人，2023；Pfoser等人，2000；Liu等人，2021；Zhang等人，2022；Gao等人，2023；《Java中的R树实现》，TheDeathFar 2022；Java微基准测试工具包（JMH）；Landsat 7增强型主题制图仪第一级数据2017）

CRediT作者贡献说明：黄继伟：撰写——初稿、可视化、验证、软件、方法论、形式化分析。王金标：撰写——审稿与编辑、监督、项目管理、概念设计。王子瑞：资源支持、形式化分析。王瑞：资源支持、调研。严宝飞：资源支持、调研。董玉德：撰写——审稿与编辑、资源支持、资金获取。

黄继伟|王金标|王子瑞|王瑞|严宝飞|董玉德
中国合肥工业大学机械工程学院，合肥230009