Abstract: This paper presents a quick speed spatial indexing structure which is based on R-link tree. And we introduced K-Means algorithm into the structure. In K-Means algorithm, we adopted valuestandard deviation to ascertain the initial clustering centres to improve convergence speed and we ascertained ultimate K value by distance criterion function to make K value most suitable. The structure sometimes consumes more storage than R-Link but gains better performance. The more the data quantity, the better the overall performance of the structure.

Key words: spatial database, R-Link tree, quadtree, spatial clustering, spatial index