A map contains two coordinates for every location. A three-dimensional scan contains three. Yet many storage structures and file systems are happiest when keys lie on one ordered line. How can a computer place multidimensional points into a one-dimensional sequence without throwing away all neighbourhood structure? A Z-order curve, also called Morton order, offers an ingenious answer: write each coordinate in binary and interleave the bits. The resulting Morton code creates an order that repeatedly visits nearby spatial cells in a Z-shaped pattern.
This topic explains why mathematics is important in databases, graphics, geographic information systems, simulations and high-performance computing. Binary place value, coordinate geometry, recursion, inequalities and data structures work together. Z-order does not preserve every distance, and a rectangular query may split into several code intervals. Its usefulness comes from a practical compromise: a simple, reversible mapping that often keeps nearby cells near enough for efficient grouping. G. M. Morton’s 1966 report introduced the technique for geodetic data and file sequencing; its bibliographic record is available through WorldCat’s catalogue.
Choose Your Reading Route
- Student: begin with the four-by-four grid and interleave the bits by hand.
- Parent: focus on the everyday analogy, limits and learning projects.
- Educator: use the grid activities to connect binary numbers with coordinates.
- Computing learner: continue through range decomposition, quadtrees and bit operations.
- Data or engineering explorer: study locality, quantisation, false positives and benchmarking.
The Dimensionality Mismatch
Imagine a library shelving system that accepts one call number per book, while each book is described by two numeric properties: subject position (x) and reading level (y). We could sort by (x) first and then (y), but two books on opposite sides of an (x)-boundary might be physically close in the two-dimensional description and far apart in the list. Sorting only by distance from an origin also mixes directions and loses a simple inverse mapping.
Computers face a similar mismatch. A B-tree or sorted array stores one-dimensional keys efficiently. Spatial data live in two or more dimensions. A space-filling order assigns each grid cell a scalar key, making ordinary ordered storage available. A good order should be quick to compute, reversible for fixed precision, and reasonably local: many nearby points should receive nearby keys.
No one-dimensional order can preserve all neighbourhoods of a higher-dimensional space perfectly. Cutting a plane into a line inevitably separates some adjacent cells. Z-order accepts this mathematical limitation and chooses a recursive pattern that is exceptionally simple to calculate with bits.
Binary Coordinates Make the Pattern
Take a (4\times4) grid. Each coordinate ranges from 0 to 3 and therefore needs two binary bits:
- (0=00_2)
- (1=01_2)
- (2=10_2)
- (3=11_2)
Let (x=x_1x_0) and (y=y_1y_0), where the subscript 1 is the more significant bit. One convention forms the Morton code (z=y_1x_1y_0x_0). Another convention starts with (x); both are valid if encoding and decoding agree. The interleaving gives two bits to each level of spatial subdivision.
For point ((x,y)=(2,1)), (x=10_2) and (y=01_2). Interleaving as (y_1x_1y_0x_0) gives (0,1,1,0=0110_2=6). For ((3,2)), (x=11_2), (y=10_2), and the code is (1,1,0,1=1101_2=13). Decoding simply removes alternating bits: the (x)-bits and (y)-bits return to their coordinate positions.
A Complete Four-by-Four Walk
Using the convention above, the sixteen cells receive codes from 0 to 15. The lowest two code bits decide position inside a (2\times2) block. The highest two decide which large quadrant contains that block. Reading codes in numerical order visits the lower-left (2\times2) area, then the lower-right, upper-left and upper-right quadrants according to the selected axis orientation. Within each quadrant, the same little Z pattern repeats.
The important structure is recursion. A (2\times2) grid has one Z. A (4\times4) grid contains four scaled copies of that pattern. An (8\times8) grid contains four (4\times4) copies. Every added coordinate bit creates another level. This is why prefixes of Morton codes identify nested square regions.
If two points share the first (k) pairs of interleaved bits, they lie in the same cell at depth (k) of a quadtree. Their common code prefix is therefore a compact statement about shared spatial region. Longer common prefixes indicate finer shared cells. This prefix property supports grouping and hierarchical traversal.
Deriving the Interleaving Formula
Suppose coordinates have (b) bits. Write
(x=\sum_{i=0}^{b-1}x_i2^i) and (y=\sum_{i=0}^{b-1}y_i2^i),
where every (x_i,y_i\in\{0,1\}). If (x)-bits occupy even code positions and (y)-bits occupy odd positions, then
(z=\sum_{i=0}^{b-1}(x_i2^{2i}+y_i2^{2i+1}).)
This equation says exactly what bit interleaving does. An (x)-bit that represented (2^i) now contributes at (2^{2i}); a (y)-bit contributes at the neighbouring position (2^{2i+1}). Decoding applies masks and shifts to gather even and odd positions.
The formula generalises to three dimensions. Bits from (x,y,z) occupy positions (3i,3i+1,3i+2). Each additional bit level divides a cube into eight octants. A code prefix identifies an octree cell. The price is that a fixed-width machine word supports fewer bits per coordinate as dimensions increase.
Bit Spreading and Compacting
A straightforward encoder loops through bit positions and appends one bit from each coordinate. Faster implementations use masks and shifts to “spread” bits apart. For a two-dimensional 32-bit code, a 16-bit coordinate can be transformed so zeros occupy the gaps between its bits; the two spread values are then combined with one shifted by a single position.
These operations depend on word size and unsigned behaviour. Overflow silently discards high bits. Signed integers can introduce surprising shifts. Portable code should specify coordinate range, output width and axis convention, then verify round trips: decode(encode((x,y))) must equal ((x,y)) for every supported input or a representative exhaustive range.
There are also hardware instructions on some processors for parallel bit deposit and extraction, but a portable algorithm remains important. A fast operation is not useful if its bit layout differs from stored data. Compatibility is part of the mathematics because the mapping is a contract.
From Continuous Coordinates to Integer Cells
Real locations are not naturally small non-negative integers. Longitude and latitude may be decimal values; a game world may include negative coordinates; measurements have physical units. Before interleaving, a system must quantise each dimension.
Suppose (x\in[x_{\min},x_{\max}]) and we want (b) bits. One mapping is
(q_x=\left\lfloor\dfrac{x-x_{\min}}{x_{\max}-x_{\min}}(2^b-1)\right\rfloor,)
with careful clamping at boundaries. Apply a similar formula to (y). The cell width is approximately ((x_{\max}-x_{\min})/(2^b-1)). More bits give finer spatial resolution but require longer keys.
Quantisation is lossy unless original coordinates are stored separately. All points within one cell share the same Morton code. A range query on codes should therefore be followed by an exact check on original coordinates if precise geometry matters. This “filter then refine” pattern is central to spatial indexing.
Locality: What Z-Order Preserves
Z-order has useful locality because a quadtree cell corresponds to a contiguous range of codes sharing a prefix. Points within the same small cell are grouped. Scanning a code interval often visits spatially related regions, improving cache and storage behaviour compared with an arbitrary order.
But locality is asymmetric. Nearby in space does not guarantee nearby in code. Two cells touching across a high-level quadrant boundary can have codes far apart. Conversely, consecutive codes are often spatially close, but the transition between quadrants can jump. Z-order preserves locality statistically and hierarchically, not perfectly.
This distinction should appear in every honest explanation. Saying “Z-order preserves spatial locality” is shorthand. A more precise statement is that it tends to cluster points sharing hierarchical grid prefixes, while some neighbours are separated at recursion boundaries.
A Boundary Counterexample
Consider two points on opposite sides of the vertical midpoint of a square. Their (x)-coordinates differ by one quantised unit, and their (y)-coordinates are equal. If crossing the midpoint changes the most significant (x)-bit, the interleaved code changes in a high position. The points may be close geometrically but separated by a large numeric gap.
Now consider two points with consecutive Morton codes at the end of one recursive block and start of another. Their positions can jump across part of the grid. Plotting these transitions is an excellent project because it replaces a vague promise with an empirical distribution of step lengths.
Alternative space-filling orders such as the Hilbert curve often have stronger locality properties but are more complex to compute and orient recursively. Z-order remains attractive when simplicity, prefix arithmetic and fast encoding matter.
Rectangular Range Queries
Suppose a user asks for every point inside rectangle (R=[x_a,x_b]\times[y_a,y_b]). The smallest and largest Morton codes of the rectangle do not generally define a clean answer. The numeric interval between them may include cells outside (R), and parts of (R) may be best represented by several disjoint code intervals.
A common approach recursively visits quadtree cells. If a cell lies completely outside the rectangle, skip it. If it lies completely inside, add the cell’s contiguous Morton interval. If it partially overlaps, subdivide it and test the children. The result is a set of intervals that can be scanned in a one-dimensional index. Exact coordinate checks remove false positives near boundaries.
This procedure connects geometry with interval arithmetic. The query is efficient when a modest number of hierarchical cells covers the rectangle. A thin diagonal or irregular shape may fragment into many intervals. Workload shape matters as much as point count.
Prefixes as Quadtree Addresses
At each two-dimensional level, the next pair of code bits selects one of four quadrants. Thus a Morton code can be read as a path in a quadtree: quadrant, subquadrant, sub-subquadrant and so on. Truncating low-order bit pairs moves to an ancestor cell. Appending pairs descends to finer cells.
This gives elegant operations. To group points at resolution (k), keep only the first (2k) bits. To find the parent, shift right by two bits. In three dimensions, shift by three. Prefix ranges have simple binary endpoints: all descendant codes share the prefix, while remaining suffix bits vary.
The quadtree view also explains why resolution should match the task. Grouping delivery locations by an extremely fine prefix produces many nearly empty cells; grouping by a coarse prefix merges distinct neighbourhoods. The correct level depends on density and query purpose.
Sorting and Cache Locality
Many computations visit nearby spatial points together: image tiles, particle interactions, terrain blocks and sparse matrix elements. Sorting by Morton code can make adjacent processing items more likely to occupy nearby memory. Better locality may reduce cache misses and improve block transfers.
Performance is not guaranteed by the curve alone. Data distribution, hardware cache, record size, query pattern and sorting cost all matter. A workload that repeatedly follows rows may prefer row-major order. A nearest-neighbour algorithm may need a specialised index. Benchmarking should compare realistic alternatives with the same data and correctness checks.
This is an important lesson in applied mathematics: structural reasoning generates a hypothesis—nearby data may be accessed together—but measurements decide whether the implementation benefits.
Application 1: Geospatial Data
Morton’s original context was geodetic data and file sequencing. Modern geospatial systems also face the need to place two-dimensional coordinates into ordered storage. Quantised longitude and latitude can be interleaved, and code prefixes can represent hierarchical map cells.
Earth is not a flat rectangle, so projection and coordinate-system choices come first. Distances near poles and the international date line require special care. A Morton index built on projected coordinates inherits the projection’s distortions and valid region. Geometry predicates must use appropriate spatial methods, not raw code differences.
The value of the index is organisational. It narrows candidate regions. It does not turn a Morton-code difference into kilometres or prove that the numerically closest code is the geographically nearest point.
Application 2: Databases
Database engines can use space-filling keys to map spatial values into ordered indexes. Amazon’s Aurora MySQL release documentation, for example, records a native spatial-index implementation using Z-order curves in specific engine versions; the Aurora MySQL 2.11.1 release notes provide an official example of the technique appearing in a production database.
Product documentation should not be generalised into a universal speed promise. The release note describes one implementation and workload claims associated with that product version. Different engines use different tessellations, trees and query planners. A student or engineer should verify current documentation and benchmark their own workload.
Conceptually, the mapping lets a conventional ordered index scan selected code intervals. Exact spatial predicates then confirm results. This division between coarse index and precise filter mirrors many database designs.
Application 3: Images and Tiled Arrays
An image is a two-dimensional array, but memory is linear. Row-major order places each row contiguously. Morton order instead groups small two-dimensional blocks recursively. Algorithms that repeatedly access neighbourhoods at multiple scales may benefit from that layout.
Consider a (1024\times1024) image split recursively. Pixels in the same small tile share a long Morton prefix. Downsampling, mipmap construction or recursive image processing can traverse those groups. Yet scanning a full horizontal row may touch separated Morton regions. Layout should reflect access pattern.
A practical experiment stores a small matrix in row-major and Morton order, then traces the indexes visited by a (3\times3) stencil. Counting cache lines in a simplified model turns an abstract locality claim into a measurable comparison.
Application 4: Simulations and Point Clouds
Particle simulations and point-cloud processing often partition space into cells. Encoding cell coordinates with Morton codes provides a sortable key. Points in the same cell share a code; nearby cells often form nearby ranges. Sorting can support batching, tree construction and parallel work assignment.
Three-dimensional encoding interleaves three coordinates. If a 64-bit key is used, only about 21 bits per axis fit with one spare bit, setting a finite grid resolution. Very large worlds may need offsets, multiple tiles or wider keys. The bit budget is a concrete engineering constraint derived from place value.
Our LiDAR and 3D point-cloud article explains how ranges become coordinates. Z-order addresses how those coordinates can be grouped and traversed after measurement.
Application 5: Distributed Data Partitioning
A sorted Morton key space can be divided into intervals assigned to workers. This gives a simple partition rule and can preserve some spatial grouping. However, uniformly sized code intervals do not imply equal numbers of records. Dense cities and empty seas produce severe load imbalance in geographic data.
Sampling the key distribution, building adaptive split points or combining spatial cells can improve balance. Moving boundaries affects data migration and query fan-out. The “best” partition therefore balances locality, load, stability and operational cost.
This connects spatial mathematics with systems design. One elegant key does not eliminate skew; it makes certain trade-offs easier to express.
Range Search Is Not Nearest-Neighbour Search
A rectangular range query can be decomposed into Morton intervals because grid cells have prefix ranges. Finding the true nearest point is different. The next code in sorted order is not necessarily the closest in Euclidean distance. A neighbour across a quadrant boundary may be numerically far away.
Nearest-neighbour search needs spatial bounds. An algorithm can inspect cells in increasing lower-bound distance from the query, stopping when no unseen cell could contain a closer point. Alternatively, use an R-tree, k-d tree, graph index or other structure suited to the dimension and workload.
The misconception arises because “locality preserving” sounds stronger than it is. Mathematics corrects the language: Z-order supplies useful clustering, not an isometry between multidimensional distance and integer difference.
Quantisation Error and Precision Budgets
With (b) bits across width (W), a cell width is about (W/2^b). If a map spans 40 kilometres and uses 16 bits, the cell width is roughly (40000/65536\approx0.61) metres. That may be adequate for one task and unacceptable for another. In three dimensions, storing 21 bits per axis across a 100-kilometre world gives roughly 4.8-centimetre cells, before considering coordinate projection and measurement error.
More precision increases key width or consumes bits needed for other dimensions. It also creates sparse fine cells. Precision should not exceed the meaningful accuracy of source data without reason. A GPS reading uncertain by several metres does not become centimetre-accurate because it receives a long code.
Report both quantisation resolution and original measurement uncertainty. They are different sources of error.
Comparing Z-Order with Row-Major and Hilbert Order
Row-major order stores every cell in one row before moving to the next. Its formula is simple: for width (W), index (i=yW+x). Horizontal neighbours are consecutive, but vertical neighbours are (W) positions apart. It is excellent when algorithms scan complete rows. Z-order breaks rows into recursive tiles, giving both axes some influence at every bit level.
Hilbert order also recursively visits grid cells, while rotating subpatterns so consecutive cells remain face-adjacent in the ideal grid traversal. It often provides better locality than Z-order, but encoding and range decomposition require more state. There is no winner independent of workload. A texture sampler, database range scan and matrix row operation value different neighbourhoods.
A fair comparison fixes the grid, record size and query trace. Measure number of storage blocks touched, cache-line transitions, interval count and encoding time. Include the cost of sorting or converting layout. Present median and tail behaviour, because a few large Z-order jumps may matter even when the average is good. This evaluation turns “locality” into several measurable properties instead of one slogan.
Signed Coordinates and Stable Conventions
Many worlds place the origin in the middle, so coordinates can be negative. Simply reinterpreting a signed two’s-complement integer as unsigned puts negative values after positive values in a way that creates a discontinuity near zero. One option adds a fixed bias: for a (b)-bit signed range, map (x) to (x+2^{b-1}). Another maps a declared bounding box to ([0,2^b-1]). The choice must be documented.
Axis order is equally important. Does the most significant pair hold (y) then (x), or (x) then (y)? Are bits read most-significant first? Are coordinates clamped, wrapped or rejected outside the box? Changing any convention changes persistent codes. A database migration that silently swaps axes can scramble spatial order while every value still looks like a valid integer.
Create a small conformance table containing corner points, origin, maximum values and several mixed-bit coordinates. Store the expected code and decoded coordinates. Every implementation language should pass the same table. This is especially important when one service writes keys and another reads them years later.
Query Planning with Multiple Intervals
After decomposing a rectangle into Morton intervals, a planner decides whether to scan them separately, merge neighbouring intervals or fall back to a broader scan. Merging reduces seek and query overhead but introduces false positives. Keeping intervals precise reduces filtering work but may create hundreds of tiny scans.
Suppose two intervals are separated by a gap of ten codes. Reading the gap may be cheaper than starting another storage request. If the gap contains dense unrelated records, it may be expensive. The optimal choice depends on latency, bandwidth, cache and density. A cost model can estimate
( ext{total cost}=a(\text{interval count})+b(\text{records scanned})+c(\text{exact tests}).)
The coefficients are measured system costs rather than universal constants. This simple expression shows how geometry feeds a database decision. The mathematical decomposition produces options; the cost model chooses among them. Learners can simulate sparse and dense datasets and watch the preferred merge threshold change.
Data Skew and Adaptive Resolution
A uniform grid treats every region at the same resolution. Real data are often skewed. A city centre may contain millions of points while a rural cell contains a few. Fine global resolution creates many empty cells; coarse resolution overloads dense ones. Adaptive trees subdivide only populated or complex regions.
Morton prefixes still help because every adaptive cell has a prefix, but comparing cells of different depths requires care. One cell may contain another. Sorting solely by padded codes can intermix ancestors and descendants unless the representation includes depth or an unambiguous terminator. Range and containment queries must understand this hierarchy.
Adaptive partitioning also changes over time. If a cell splits, stored objects may move to new partitions. Systems balance better locality against migration and metadata churn. This is another reminder that a mathematical code operates inside a changing system rather than an empty grid.
Common Misconceptions
- “The curve visits every real point.” Implementations usually order a finite quantised grid; the mathematical limiting curve is a related concept.
- “Nearby coordinates always have nearby codes.” High-level boundaries create counterexamples.
- “Code difference measures physical distance.” It does not.
- “One minimum-to-maximum interval exactly covers a rectangle.” Many queries require multiple intervals and refinement.
- “More coordinate bits always improve the system.” They increase precision but consume key width and may worsen sparsity.
- “Z-order is always faster.” Performance depends on access pattern, data distribution, hardware and comparison baseline.
Did You Know? A Prefix Is a Map Region
In an ordinary decimal ID, a shared prefix may have no geographic meaning. In a Morton code, every complete group of dimension bits selects a nested spatial cell. A prefix can therefore act like a compact region label.
This makes binary place value surprisingly visual. The most significant interleaved bits choose a large quadrant; the next bits zoom in; later bits refine the address. Students who find binary numbers abstract can see each bit pair literally move a point through a hierarchy of squares.
The same idea explains why prefix databases and tree structures fit the representation so naturally. Bit syntax mirrors spatial subdivision.
A Student Learning Progression
Begin with (2\times2) and (4\times4) grids. Label coordinates in binary, choose an axis convention and interleave by hand. Sort cells by code and draw arrows. Decode several values to verify the mapping.
Next, move to (8\times8). Colour cells sharing the first two or four code bits. Connect these groups to quadtree levels. Measure Euclidean distance between consecutive cells and find the largest jump.
Then implement encoding and decoding with loops before using bit masks. Add signed or real coordinates through an explicit quantisation step. Test boundaries and round trips. Finally, build a rectangular query that emits code intervals and performs exact filtering.
At every stage, keep coordinate units, bit width and axis order visible. Hidden conventions are the main source of confusion.
Practical Projects
Project 1: Human Morton Sort
Give learners cards containing grid coordinates. They convert each coordinate to binary, interleave the bits, and line up by code. Reconstruct the Z path on a floor grid. Swap axis convention and observe the rotation or reflection.
Project 2: Locality Histogram
For an (N\times N) grid, calculate Euclidean distance between consecutive Morton-ordered cells. Plot a histogram and compare with row-major order. Report median, maximum and the spatial locations of the largest jumps.
Project 3: Rectangle Decomposition
Choose a query rectangle on a (16\times16) grid. Recursively cover it with fully included quadtree cells, then list their code intervals. Count false positives if larger cells are used. Compare compactness with precision.
Project 4: Precision Budget
Select a real or fictional rectangular world and a target cell size. Calculate the bits required per axis and total key width in two and three dimensions. Discuss whether source measurements justify that resolution.
Guidance for Parents
The best starting question is simple: “How can we file map squares on one shelf?” Let the student invent an ordering before introducing bit interleaving. Comparing their scheme with Z-order makes the design problem memorable.
If binary conversion becomes mechanical, return to the grid. Ask which quadrant a prefix selects and why one neighbour may be far away in the list. The visual explanation matters more than fast bit tricks.
Celebrate counterexamples. Finding two adjacent cells with distant codes is not disproving the lesson; it is understanding the method’s limitation. That habit—testing the strongest-sounding claim—is excellent mathematical practice.
Guidance for Educators
Z-order links number representation with geometry without requiring advanced algebra. Specify the convention at the top of every worksheet. Use unsigned small coordinates first. Require encode–decode round trips so learners catch swapped axes and reversed bit significance.
Assessment can ask for more than a code. Have students draw the recursive regions, identify a locality failure and explain why a rectangle becomes several intervals. A strong answer separates the index filter from the exact geometric test.
For coding tasks, use property tests: decoding an encoding returns the input; every grid point receives a unique code at fixed precision; all descendants of a prefix occupy one numeric interval. These properties turn theory into verification.
Connections to Other Mathematics
Z-order connects binary place value, coordinate transformations, recursion and trees. Its range-query algorithm uses set containment and interval unions. Quantisation invokes floors, scaling and error bounds. Performance studies require statistics rather than anecdotes.
It also complements hashing and partitioning. A hash deliberately scatters nearby inputs to distribute keys; a Morton code deliberately retains some locality. Rendezvous hashing assigns keys to nodes with minimal movement under membership changes, while Z-order arranges space. Different key transformations optimise different relationships.
Our MinHash article offers another useful contrast: MinHash preserves set-similarity probability in compact signatures, not geometric locality.
Frequently Asked Questions
Is Z-order the same as a Z-shaped scan of one grid?
The visible Z repeats recursively at every scale. The recursive structure, produced by interleaved bits, is more important than one large letter shape.
Can negative coordinates be encoded?
Yes, after mapping a bounded signed range to non-negative integers or using a carefully defined signed encoding. The mapping must preserve the intended order and fit the bit budget.
Can decimal coordinates be interleaved directly?
Practical indexes normally quantise them to fixed-width integers first. Decimal digits are not a substitute for a defined binary spatial grid.
Does Z-order work beyond three dimensions?
The interleaving generalises to any fixed dimension, but each dimension receives fewer bits in a fixed-width key, and locality becomes harder in high dimensions.
Is the Morton code unique?
It is unique for each quantised grid coordinate tuple within the chosen precision and convention. Multiple real points in the same cell share the same code.
Why not always use a Hilbert curve?
Hilbert order often offers better locality, but encoding, decoding and range handling are more complex. The appropriate choice depends on workload and implementation goals.
Can I calculate distance from two Morton codes?
Decode the coordinates and use the correct geometric distance. Numeric code difference is not physical distance.
Useful Next Reading
- Use the WorldCat record for Morton’s 1966 report to identify the original work and publication details.
- See an official production example in the Amazon Aurora MySQL 2.11.1 release notes, while treating its product-specific claims as product-specific.
- Revisit LiDAR, Time of Flight and 3D Point Clouds before organising measured 3D coordinates.
- Compare locality-preserving order with similarity-preserving signatures in MinHash and Jaccard Similarity.
- Use School Commutes, Maps and Route Planning for a broader discussion of spatial decisions and routes.
Final Perspective
Z-order curves answer a practical question with a beautiful bit-level construction. Interleaving coordinate bits turns a multidimensional grid cell into one sortable integer. Common prefixes describe nested regions, ordered indexes become usable, and recursive range decomposition connects geometry to interval scans.
The method is valuable precisely because its compromises are understandable. It groups many neighbours but not all, quantises continuous space, and often needs exact refinement after a coarse search. Students can compute every step, draw every region and discover every boundary failure. That transparency is a strong answer to “Why Mathematics?” Mathematics lets us translate between dimensions while keeping track of what the translation preserves—and what it cannot.
That habit of checking preservation is useful far beyond spatial indexes: every representation simplifies reality, and every simplification deserves a stated error boundary.