kd-tree
A binary tree that partitions k-dimensional space by cycling the splitting axis at each level.
Invented by Jon Bentley in 1975. At the root the points are split along x, at the next level along y, then z, and round again — splitting at the median point gives a balanced tree. That turns nearest-neighbour searches and range queries logarithmic rather than linear.
kd-trees are used for point clouds, photon mapping and as an acceleration structure in ray tracing of static scenes. For moving game worlds a BVH is preferred, since kd-trees are expensive to rebuild every frame.