A Novel Implementation of Dynamic R-tree Based on Lazy Splitting and Clustering
基于惰性聚类分裂的动态R树实现方法

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.