Search tools and guides ⌘K
VII · Spatial structures

KD-tree

Binary search, in higher dimensions.

1975 · Jon Bentley · Stanford
The story

Bentley's structure splits points by a different coordinate at each level — first by x, then by y, then x again. Nearest-neighbour search uses bound-pruning to skip vast regions. Works beautifully up to ~10 dimensions; degrades to brute-force above that ("curse of dimensionality").

How it works

Recursively partition the point set: pick a splitting dimension (round-robin or max-variance), find the median, put smaller-coord points left, larger right. Search prunes branches whose minimum bound is farther than the current best.

Where it lives

Photo sphere finders. Point-cloud processing (LiDAR). 2D collision detection. Astronomy queries. scipy.spatial.KDTree. PostGIS spatial indexes.

The key insight

KD-trees are excellent up to ~10 dimensions, then collapse. For higher-dim nearest-neighbour (text/image embeddings), HNSW and IVF-PQ are the modern answer.

More in Spatial structures
R-tree A tree of bounding boxes. Quad-tree / Octree Recursive 4-way / 8-way subdivision. BVH · bounding volume hierarchy A tree of boxes for ray tracing. Z-order / Hilbert curve Linearise space, preserve locality.
Across the cabinet
I Array A row of equal-sized boxes. I Dynamic array (vector) An array that grows itself. I Linked list A chain you can splice. I Stack Last in, first out. I Queue First in, first out. I Deque Both ends, equally. I Ring buffer A fixed-size queue that never allocates. II Binary search tree Sorted, but with shortcuts.
← All data structures