Morton Code

A Morton code — also called a Z-order curve or Lebesgue curve — is a method of mapping multi-dimensional data to a one-dimensional sequence while preserving spatial locality. The code is constructed by interleaving the bits of each coordinate, so that points that are close in space tend to have close Morton codes. This property makes Morton codes the natural ordering for linear quadtrees and for spatial databases that must store two-dimensional data in one-dimensional memory.

The Morton code is a particular kind of space-filling curve, simpler than the Hilbert curve but with weaker locality guarantees. Its simplicity — bit interleaving requires no multiplication or table lookup — makes it the preferred encoding in GPU spatial indexing and in database systems like PostGIS.

The Morton code's elegance is deceptive. By flattening space into a line, it assumes that spatial locality is a one-dimensional property, which is true only in the limit of infinite resolution. At finite resolution, the Z-order curve creates discontinuities — points that are adjacent in space can be arbitrarily far apart in code. The choice of Morton over Hilbert is a trade-off between computational simplicity and geometric fidelity, and the field has not yet admitted how often it chooses the wrong side.