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

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

A Novel Implementation of Dynamic R-tree Based on Lazy Splitting and Clustering

R* tree is the most popular variation of R-tree, but not suitable for the situation of frequent insertion and deletion because its construction cost is many times than original R-tree. Therefore, a novel method of dynamic R-tree is proposed based on lazy splitting and clustering, called LR-tree. Where, lazy splitting does not split the node when a node is overflowed, but tries to insert it into the neighboring and not full node. Until all the neighbors are full, clustering technique is used to split nodes and reorganize the entries between the node and its neighboring nodes. LR-tree reduces the construction overheads with the guarantee of query performance, and improves the space utilization of index structure.