基于惰性聚类分裂的动态R树实现方法

R*树是目前公认查询效果很好的R树变体,但是其构造代价较原始R树增加数倍,对于插入删除和更新频繁的空间数据效果不好。为此,本文提出一种基于惰性聚类分裂技术的R树动态实现方法(LR树)。惰性聚类分裂技术是在对象插入节点导致溢出时不立即进行分裂,而是尝试将其插入到邻近的未满节点中,直到邻近节点均已满时,再利用聚类技术进行节点分裂,在邻近节点和分裂节点之间重组入口项。LR树在确保查询性能的前提下,大大降低了构造代价,并且大幅提高了索引结构的空间利用率。最后的分析和实验证明了LR树的高效性。