zcurve

Z-curve, also known as Morton order or Morton code, is a space-filling curve used to map multi-dimensional data to one dimension while preserving locality. It was introduced by G. H. Morton in 1966 as a method for sorting two-dimensional locations for efficient storage and retrieval. The curve is constructed by recursively subdividing a d-dimensional space into 2^d hypercubes and visiting them in a Z-shaped order, which translates into interleaving the binary digits of each coordinate.

In practice, the Morton code for a d-dimensional point is obtained by interleaving the bits of its coordinates. For example, in 2D, the bits of x and y are interleaved to form a single integer. In 3D, bits from x, y, and z are interleaved. This yields a linear ordering that tends to keep nearby points near each other in the 1D key space, which is useful for building simple, cache-friendly indexes.

Variations: the concept extends to any number of dimensions. In computing and databases, the Morton order is used for spatial indexing, texture mapping, image processing, and memory layouts. It is computationally efficient to encode, often through bit masks and shifts, though decoding is likewise straightforward.

Limitations and comparisons: while Z-curve preserves locality to some extent, it is generally less locality-preserving than the Hilbert curve and can produce fragmented ranges for two-dimensional queries. It is best suited for simple, fast lookups and for enabling linear scans or range decompositions in multi-dimensional data.