A binary search tree for points: each level splits the plane on x, then y. Insert, find the nearest neighbour with pruning, and search a rectangle.
This interactive visualization needs JavaScript.