Abstract: R*-tree spatial index manages nodes based on the idea of partial adjustment, but lacks time and efficiency. In order to overcome the shortages of R*-tree, the paper proposed a new storage structure, and the algorithms of insertion, overflow and split for the new storage structure. The merits of the storage structure were analyzed. Experiments verify the new storage structure is more efficient than R*-tree.

Key words: Geographic Information System (GIS), spatial index, spatial query, R-tree, R*-tree

摘要： R*-树基于局部调整的思想对节点进行管理，存在时间与效率上的不足。为克服R*-树的不足，给出了一种新型的存储结构，并给出新型存储结构的插入、溢出、分裂等空间索引常用操作的算法。分析新的存储结构的优点，并通过实验结果说明该方案比R*-树具有更高的效率。

关键词: 地理信息系统, 空间索引, 空间查询, R-树, R*-树