K nearest neighbor query algorithm is one of the commonly used algorithms in massive spatial data query. First

it construct an index of large-scale spatial data by Kd-Tree

and hierarchical division of the search space. Then

it used the k nearest neighbor query to ensure the efficiency of the search. However

the traditional Kd-Tree construction has two drawbacks: the use of test data points are required for each k nearest neighbor query back to the root

thus affecting the efficiency of the query; Kd-Tree uses the split-level domain for the space division of space into cubes (two-dimensional data are rectangular)

extra space appears in polygonal space at the intersection of judgment

making the comparison of data unnecessary

thus affecting the efficiency of the query. Regarding these two shortcomings

it proposed the corresponding improved algorithm-RB algorithm. Experimental results show that the algorithm has a higher query efficiency than the traditional KD algorithm.There are two main contribution from this paper: (1) This paper construct a quickly create Kd-Tree indexes to support queries KNN akgorithm to classify large-scale data. (2) RB algorithm is proposed to improve the traditional Kd-Tree index construction method

and improving query efficiency for KNN algorithm.