Hilbert Curve & Space-Filling Curves: Locality & Indexing

Peano's paradox: a line that fills a square

In 1890, Giuseppe Peano constructed a continuous curve that passes through every single point of a 2D square. Georg Cantor had already shown that a line and a square contain the same cardinality of points, but Peano went further: the correspondence could be made continuous, traced without lifting the pen. Such space-filling curves are continuous but famously nowhere differentiable — they change direction infinitely often at every scale, like a fractal of dimension exactly 2 dressed up as a 1D curve.

Hilbert's recursive rule

David Hilbert refined Peano's construction in 1891 into a cleaner recursive rule, and it is Hilbert's version — not Peano's original zig-zag — used almost universally today. Start with a U-shaped path visiting the four quadrants of a square. At the next level, replace each quadrant with a smaller, rotated or reflected copy of the same U-shape, chosen so the exit of one sub-curve lines up exactly with the entry of the next.

Order n curve: 4ⁿ grid cells, a 2ⁿ × 2ⁿ grid fully traversed

Key guarantee: consecutive indices i, i+1
  → ALWAYS map to spatially adjacent grid cells

The rotations at each level are what make the curve special: wherever one sub-square's path ends, the next picks up right next to it in physical space, not just in the abstract 1D order — a guarantee that holds at every scale, everywhere on the grid.

Hilbert vs Morton (Z-order)

A simpler, faster alternative interleaves the bits of x and y directly — the Morton or Z-order curve. It shares the recursive quadrant idea but skips the rotation step, making it dramatically cheaper to compute at a real cost in locality: tracing consecutive Morton indices draws a Z-shape, and every quadrant crossing can leap clear across the grid because a high bit can flip while low bits reset. The Hilbert curve's rotations exist specifically to eliminate these jumps, at roughly 2-4× the computational cost.

Databases, caches, and compression

Spatial databases map 2D or 3D coordinates to a single Hilbert index and sort rows by it in a conventional B-tree, turning expensive multidimensional range queries into fast 1D scans. Traversing a texture or grid in Hilbert order instead of row-major order keeps small local neighbourhoods contiguous in memory, dramatically improving CPU and GPU cache hit rates for mipmap generation and tiled streaming. Some image compression and dithering algorithms traverse pixels in Hilbert order specifically because it keeps visually similar pixels adjacent in the resulting 1D stream, and open-world games use Hilbert or Morton ordering to keep spatially nearby terrain chunks nearby on disk.

Frequently asked questions

Try it live

Everything above runs in your browser — open Space-Filling Curves and watch Hilbert, Peano and Morton curves fill the plane, coloured by path position to see locality preservation live.