（江苏大学计算机科学与通信工程学院，江苏镇江 212013）

0 引言

随着移动互联网的迅猛发展，推动了基于地理位置信息服务（Location-Based Service，LBS）的大量普及。最典型的例子就是地图类的服务，比如百度地图、高德地图、外卖平台等，伴随着的还有空间数据的极速增长。由于空间数据的多维性以及位置关系的多样性，空间数据的处理与存储问题已经成为了亟待解决的问题。大多数空间数据索引的构建是通过R-树来完成的，R-树是B-树在高维上的扩展［1］，R-树结构简明、动态性高、适用范围广［2］。在进行R-树树空间区域检索时，从根节点出发，由顶向下逐层缩小范围直到叶子节点满足搜索条件。

目前，学术界对R-树的研究主要有两个方面：一种是针对空间聚类算法方面的研究；另一种是针对R-树结构相关算法调整方面的研究。聚类算法构建R-树中，将R-树操作中的分裂算法改进为聚类算法中的多路分裂，对R-树的研究转向为聚类构建。2016 年胡昱璞［2］提出动态确定k值的空间聚类算法（Dynamical K-Value spatial Clustering algorithm，DKSC），该算法通过聚类划分空间数据，把同一子空间的数据组织在同一个子树下，从根节点到叶子节点逐层构建R-树，形成高效的R-树空间索引。2017 年彭召军等［3］针对传统的k-means聚类算法对初始值非常敏感，聚类过程较为复杂的问题，在R*-树的构建过程中引入聚类技术，对R*-树的基本结构加以改进，提高索引树的空间利用率。R-树相关算法的调整研究，一般是对R-树插入算法中的分裂算法重构或是改变插入节点模式。2017 年……