k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches) and creating point clouds. k-d trees are a special case of binary space partitioning trees — Wikipedia
It’s really like a binary tree that assign each layer of node to a dimension. When insert points to the tree. It should split the space into two for optimize the search time. It also need to memorize those box as well.
When we looking for the closest neighbor, we need to traverse all the tree with a pruning cast that is if the current smallest distance is smaller than the distance of the sub-node box, that mean the points in that box will not contain the closest neighbor.