Z-order curve

A Z-order curve (also called the Morton order or Morton curve) is a space-filling curve that maps multi-dimensional coordinates to a one-dimensional index by interleaving the bits of each coordinate. The Z-order index of a point is formed by interleaving the binary representations of its coordinates, producing a single integer that preserves some spatial locality.

The Z-order curve is less locality-preserving than the Hilbert curve but computationally cheaper, requiring only bit manipulation rather than the recursive geometric construction of the Hilbert curve. This tradeoff makes it the preferred index in many spatial database and geographic information system implementations, where the cost of computing the curve must be weighed against the benefit of better spatial clustering.

The curve is named for its Z-shaped pattern at each level of recursion: each quadrant is visited in a Z pattern, and the overall curve is the recursive refinement of that pattern. It is used in quadtree-based spatial indexing, N-body simulation load balancing, and GPU texture memory layouts.

Practical Performance Characteristics

The theoretical locality advantage of the Hilbert curve — it minimizes cluster count for rectangular range queries — assumes uniform access patterns and ignores the memory hierarchy. In production systems, Z-order often outperforms Hilbert not despite its worse asymptotic bound but because of properties excluded from the theoretical model:

Index computation cost: The Z-order index is computed by bit interleaving, a sequence of shifts and masks that compiles to a handful of CPU instructions with no branches. The Hilbert curve requires either recursive geometric construction or table-driven state-machine traversal, both of which introduce branch mispredictions and cache misses. On modern CPUs, the cost of computing the Hilbert index can exceed the cost of the spatial query itself for small result sets.

Range query decomposition: A rectangular query in Z-order space decomposes into O(log n) contiguous intervals on the one-dimensional index. Each interval resolves with a single B-tree or LSM-tree range scan. The Hilbert curve's more complex adjacency produces intervals with irregular boundaries that complicate index traversal. The "better locality" of Hilbert becomes irrelevant if the index structure cannot exploit it efficiently.

Parallel and vectorized execution: Z-order indexing maps trivially to SIMD instructions and GPU threads. The bit-interleaving operation is data-parallel and requires no recursion or state. Hilbert's state-machine-based construction serializes across dimensions and maps poorly to vector units. In GPU texture layouts and N-body simulations — both primary Z-order applications — this parallelizability dominates the theoretical locality gap.

Cache behavior: Z-order indices for nearby spatial points share high-order bits, producing cache-friendly access patterns when traversing the index in sorted order. Hilbert indices also exhibit locality, but the state-machine traversal that produces them is itself cache-unfriendly. The constant-factor advantage of Z-order computation compounds with the cache advantage of simpler code, producing higher throughput in practice even for workloads where Hilbert's theoretical bound would predict otherwise.

The choice between Z-order and Hilbert is therefore not a simple quality-cost tradeoff but a systems decision that depends on the target architecture, query patterns, and index structure. For B-tree-backed spatial databases on commodity CPUs, Z-order's computational simplicity and predictable cache behavior often produce higher aggregate throughput than Hilbert's superior asymptotic locality. For specialized architectures or query-heavy workloads with large result sets, Hilbert may still win. The article's framing of Z-order as a cheaper compromise understates the cases where Z-order is the better engineering choice.