KNN (K-Nearest-Neighbors) search has been widely used in LiDAR-related applications. As LiDAR's point clouds become more massive, it is a great challenge to implement a fast and energy-efficient KNN implementation. Previous works consume much time in either building an efficient data structure or searching in the data structure. To solve this issue, we propose a high-locality data structure RPS (range-projection-structure) and an ultra-fast FPGA accelerator of the building and searching process. First, we propose a novel data structure RPS which ensures the points with similar projection locations and range scales are stored in the continuous locations of a memory. Second, we propose a highly-parallel method to build the RPS by projecting the points into a point cloud matrix and parallelly processing the points in a column. Third, based on RPS, we propose a highly-parallel KNN search algorithm, which can quickly narrow the search region and select the KNN from neighboring points in parallel. Experimental results show that our method achieves 13.7 times faster than other FPGA implementations. Moreover, energy efficiency results show that our proposed method is 27.4 times and 50.7 times higher than the state-of-the-art implementations on FPGA and GPU platforms, respectively.