论文部分内容阅读
空间索引在地理信息系统中具有重要的地位,是整个系统效率的核心。随着“数字地球”和WEB GIS的兴起,要求地理信息系统的效率核心——空间索引变的更为强劲。 R-tree类空间索引是空间索引发展的主要方向。它具有较强的灵活性,能够满足数据的动态要求;与传统关系型数据库兼容性强,能够更好地支持事务、回滚和并发等功能。 R-tree类索引自1984提出后,一直是研究的热点。人们对其不断改进,提出了多种R-tree变形,形成了一个R-tree类索引体系。其中代表性的有R~*-tree、Hilbert R-Tree和Shift-Optimal R-tree。 本文针对R-tree优化所面临的问题(结点分裂算法复杂度较高,制约了R-tree的整体效率),提出了一个复杂度接近线性的结点分裂算法——快速最优分裂算法。该算法充分利用矩形集的数据特征,将不可能为最优分裂的情况直接剔除,显著降低了结点分裂的时间花费,分裂耗时即为原有的十分之一,甚至百分之一。 同时,本文还改进了结点分裂约束条件的合理性,提出了一个更为合理的约束条件DS,从另一方面提高了结点分裂的合理性。