Search tools and guides ⌘K
VII · Spatial structures

Z-order / Hilbert curve

Linearise space, preserve locality.

1966 / 1891 · G. M. Morton · 1966 (Z-order); David Hilbert · 1891 (curve)
The story

Morton encoded 2D coordinates by interleaving the bits of x and y — points near each other in 2D land near each other in 1D, with discontinuities at quadrant boundaries. The Hilbert curve does the same thing without the jumps. Both let you index multi-dimensional data with a single B-tree.

How it works

Z-order: interleave the bits of (x, y) → one integer. Sort by that integer; nearby points cluster. Hilbert: a continuous curve that visits every grid cell with no jumps; more expensive to compute but better locality.

Where it lives

Spatial keys in DynamoDB, Bigtable. Geohashes (a Z-order variant). NUMA-aware allocators. Database multi-dim index. PostGIS GiST when SP-GIST is faster.

The key insight

A space-filling curve turns multi-dimensional indexing into a single-key sort — every existing B-tree becomes a spatial index. Geohashes (used by every "nearby" query in social apps) are exactly this.

More in Spatial structures
KD-tree Binary search, in higher dimensions. 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.
Across the cabinet
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. II AVL tree Always height-balanced, to within one. II Red-black tree Almost balanced, much faster to maintain. II B-tree / B+ tree The shape of a database index. II Heap (binary heap) A priority queue you can grep.
← All data structures