Skip to content

Z-Order Curve

Linearize a quantized multidimensional grid by interleaving coordinate bits into a Morton code, making every quadtree or octree cell a contiguous one-dimensional key interval while preserving locality imperfectly.

Version
v3 · 2026-09-06 · History
Domain-specific #
3136
Origin domain
computer science
Subdomain
spatial data structures
Aliases
Morton order, Morton code, Z-curve, Lebesgue curve, Bit-interleaved order

Core Idea

The Z-order curve maps a quantized point \((x_0,\ldots,x_{d-1})\) to one scalar key by interleaving the coordinates' binary digits from most to least significant. In two dimensions, alternating (x)- and (y)-bits produces a Morton code; sorting these codes visits recursively nested quadrants in a Z-shaped order.[1]

The decisive invariant is hierarchical: all points inside an aligned quadtree or octree cell share a bit prefix and therefore occupy a contiguous Morton-code interval. This lets ordinary one-dimensional arrays, B-trees, or hash partitions carry multidimensional hierarchy. Locality is useful but not perfect: nearby points are often close in order, while some cell boundaries create large key jumps.

Structural Signature

  • A bounded or quantized (d)-dimensional coordinate domain.
  • Fixed coordinate precision and signed-value convention.
  • Binary representation of each coordinate.
  • Deterministic interleaving of equal-significance bits.
  • One scalar Morton key.
  • Recursive quadrant, octant, or hyperoctant visitation.
  • Prefix correspondence between tree cells and key intervals.
  • Equivalence to depth-first traversal of a linear quadtree/octree.
  • Cheap encode and decode operations.
  • One-dimensional sorting or indexing backend.
  • Range-query interval skipping such as BIGMIN/LITMAX.
  • Explicit acknowledgment of locality discontinuities.

What It Is Not

It is not a guarantee that Euclidean neighbors remain adjacent in key order. It is not the Hilbert curve, whose orientation changes recursively and usually preserves locality better at greater algorithmic cost. It is not Geohash, though geohash-like systems also interleave or hierarchically encode coordinates.

The finite Morton order used in databases is also distinct from claims about a continuous surjection onto a region; implementations operate on discrete coordinate words.

Scope of Application

Morton order supports spatial databases, tiled maps, linear quadtrees and octrees, GPU texture swizzling, N-body partitioning, mesh ordering, sparse matrices, cache-aware matrix traversal, and distributed spatial decomposition. Morton's original file-sequencing proposal targeted geodetic data.[1]

Its usefulness depends on coordinate scaling, dimension, query shape, precision, and workload. High dimensions dilute locality, and arbitrary range queries may fragment into many key intervals.

Clarity

State dimension, bit width, coordinate normalization, interleave order, endianness, signed encoding, and whether keys are truncated. Distinguish ordering from the drawn curve. For query claims, report interval-generation and false-positive behavior rather than saying only that locality is “preserved.”

Manages Complexity

Z-order compiles multidimensional hierarchy into a sortable scalar. Existing one-dimensional storage systems can then perform prefix scans, partitioning, merge, predecessor search, and bulk loading without pointer-rich tree nodes. The representation trades exact metric neighborhood for cheap hierarchy-aware locality.

Abstract Reasoning

  1. Normalize every coordinate to a fixed nonnegative integer range.
  2. write each coordinate in equal-width binary.
  3. Interleave bits by significance and dimension.
  4. Interpret the result as a scalar key.
  5. Sort or index records by that key.
  6. Translate hierarchical cells to prefix intervals.
  7. Decompose range queries or jump to the next admissible key.[2]
  8. Measure locality and interval fragmentation against alternatives.

Knowledge Transfer

The portable pattern is encode several coordinates by interleaving their hierarchical address digits so common coarse location becomes a common scalar prefix. It transfers to sharding, cache layout, hierarchical identifiers, and multiresolution storage. The proposed immediate parent is Space-Filling Curve.

Examples

In two dimensions, interleaving three-bit coordinates yields a six-bit key whose first two bits choose the top-level quadrant, the next two choose its child, and so on. Sorting points by these keys directly yields a linear quadtree.[3]

For rectangular range search, BIGMIN/LITMAX jumps over key intervals that cannot intersect the query instead of scanning every code between its scalar endpoints.[2]

Structural Tensions

  • Simple bit operations versus imperfect locality.
  • Scalar ordering versus multidimensional distance.
  • Fixed precision versus dynamic spatial extent.
  • Prefix-contiguous cells versus fragmented arbitrary ranges.
  • Fast linear storage versus dimension-driven key growth.
  • Stable representation versus coordinate-normalization dependence.

Structural–Framed Character

Hierarchical digit interleaving, prefix containment, and dimensional linearization are structural. Machine-word coordinates, quadtrees, range queries, cache lines, and spatial indexes are constitutive computational machinery. The identity is domain-specific.

Structural Core vs. Domain Accent

The portable core is interleave hierarchical address digits -> common prefix -> sortable scalar. The domain accent is binary spatial coordinates and Morton-indexed data structures.

Space-Filling Curve is the proposed immediate parent. Locality of Reference, Encoding, Sequencing, Partition, and Hierarchy are related. Hilbert Curve is a sibling with a different recursive orientation rule.

The prospective queue contains one strict edge to domain_specific:space_filling_curve. No live DAG mutation is authorized.

Relationships to Other Abstractions

Local relationship map for Z-Order CurveParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Z-Order CurveDOMAINDomain-specific abstraction: Space-Filling Curve — is a kind ofSpace-FillingCurveDOMAIN

Current abstraction Z-Order Curve Domain-specific

Parents (1) — more general patterns this builds on

  • Z-Order Curve is a kind of Space-Filling Curve Domain-specific

    Space-Filling Curve is the proposed immediate parent.

Hierarchy paths (3) — routes to 3 parentless roots

Neighborhood in Abstraction Space

Z-Order Curve sits in a sparse region of the domain-specific corpus (92nd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With

  • Hilbert curve.
  • Row-major or column-major order.
  • Geohash.
  • Quadtree itself.
  • R-tree.
  • Arbitrary locality-preserving hash.
  • Exact nearest-neighbor ordering.

References

[1] G. M. Morton, A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing, IBM Ltd., Ottawa (1966), https://dominoweb.draco.res.ibm.com/0dabf9473b9c86d48525779800566a39.html. registry ↩a ↩b

[2] Hermann Tropf and Helmut Herzog, “Multidimensional Range Search in Dynamically Balanced Trees,” Angewandte Informatik 23, no. 2 (1981): 71–77. registry ↩a ↩b

[3] Irene Gargantini, “An Effective Way to Represent Quadtrees,” Communications of the ACM 25, no. 12 (1982): 905–910, doi:10.1145/358728.358741. registry ↩

[4] Volker Gaede and Oliver Günther, “Multidimensional Access Methods,” ACM Computing Surveys 30, no. 2 (1998): 170–231, doi:10.1145/280277.280279. registry ↩