Introduction

Every database, search engine, or video game that stores two-dimensional data faces the same awkward question: how do you sort points on a flat surface into a single list? Latitude and longitude, pixel coordinates, map tiles — they live in 2D, but storage on disk or in memory is 1D.

The naive answer is row-major order: scan left to right, row by row. Simple — but disastrous for spatial queries. When you ask "give me all points within this rectangle," you end up jumping wildly back and forth across the list, because two cells that are neighbours on the grid might be hundreds of entries apart in the flat sequence.

The Z-order curve, invented independently by G. M. Morton in 1966 for IBM and later formalised in computer science, solves this with a beautiful bit trick. To compute the Z-index (also called the Morton code) of a point (x, y), you simply interleave the binary representations of x and y — alternating one bit from y, one from x, one from y, one from x, and so on. The resulting number traces a Z-shaped (or ⊓-shaped) path through the grid, and nearby points on the grid end up with Morton codes that are numerically close.

The algorithm runs in O(log⁡N)O(\log N) bit operations per coordinate, or in O(1)O(1) with modern CPU instructions like PDEP. And crucially, sorting points by their Morton code is exactly as easy as sorting any list of integers — standard algorithms apply unchanged.

Try It: The 4×4 Grid

Below is a 4×4 grid of 16 cells. Each cell shows its (x, y) coordinate (column, row). Hover over or click any cell to highlight it and see:

  • Its Morton code — computed by interleaving the bits of x and y.
  • Its Z-order rank (position in the sorted Z-order sequence, 0–15).
  • Its row-major rank (position in the naive left-to-right, top-to-bottom sequence).

Then click Show Z-path to draw the full Z-order traversal, and Show row-major path to compare it with the simple scan. Notice how cells that are spatially adjacent tend to have nearby Z-ranks — but row-major can separate them by many positions.

<div class="controls">
  <button id="btnZ" type="button" class="active">Show Z-path</button>
  <button id="btnRow" type="button">Show row-major path</button>
  <button id="btnClear" type="button" class="ghost">Clear path</button>
</div>
<div id="grid" class="grid"></div>
<div id="info" class="info">Hover or click a cell to inspect it.</div>
<div id="legend" class="legend">
  <span class="dot z-dot"></span> Z-order &nbsp;
  <span class="dot r-dot"></span> Row-major
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 13px system-ui; padding: .38rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button.active { background: #e63946; border-color: #c92f3c; }
.grid { display: grid; grid-template-columns: repeat(4, 68px); gap: 5px; }
.cell {
  width: 68px; height: 68px; border-radius: 9px; border: 1.5px solid #c0cdd9;
  background: #e8eef3; display: flex; flex-direction: column;
  align-items: center; justify-content: center; cursor: pointer;
  position: relative; transition: background .12s, border-color .12s;
  font-size: 11px; color: #4a637a; user-select: none;
}
.cell .coord { font-weight: 700; font-size: 13px; color: #1d3557; }
.cell .morton { font-size: 10px; color: #6a8399; }
.cell:hover { background: #d4e3ef; border-color: #6a8399; }
.cell.selected { background: #ffeeba; border-color: #e6a817; }
.cell.z-hi { background: #e63946; border-color: #c92f3c; color: #fff; }
.cell.z-hi .coord, .cell.z-hi .morton { color: #fff; }
.cell.r-hi { background: #457b9d; border-color: #1d6080; color: #fff; }
.cell.r-hi .coord, .cell.r-hi .morton { color: #fff; }
.rank-badge {
  position: absolute; top: 3px; right: 4px; font-size: 9px; font-weight: 700;
  background: rgba(0,0,0,.15); border-radius: 4px; padding: 1px 3px;
}
.info { margin-top: .55rem; min-height: 2.6em; font-size: .88rem;
        background: #f0f5f9; border-radius: 8px; padding: .45rem .7rem; line-height: 1.5; }
.info strong { color: #1d3557; }
.legend { font-size: .8rem; color: #6a8399; margin-top: .4rem; display: flex; align-items: center; gap: .2rem; }
.dot { display: inline-block; width: 11px; height: 11px; border-radius: 50%; vertical-align: middle; }
.z-dot { background: #e63946; }
.r-dot { background: #457b9d; }
svg.path-overlay { position: absolute; top: 0; left: 0; pointer-events: none; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Morton (Z-order) encoding: interleave bits of x and y.
// For 2-bit coordinates (0-3), result is 4 bits: x1 y1 x0 y0 (lsb first: x0 y0 x1 y1).
// Layout: bit0=x0, bit1=y0, bit2=x1, bit3=y1  → x is even bits, y is odd bits.
function morton(x, y) {
  // Spread a 2-bit value into even bit positions: bit0 stays, bit1 moves to bit2.
  function spread(v) {
    v = v & 0x3;                  // keep 2 bits: b1 b0
    return (v & 1) | ((v & 2) << 1); // b0 at pos0, b1 at pos2
  }
  return spread(x) | (spread(y) << 1);
}

const N = 4;
// Build cells: for each (x,y) compute morton code and both ranks
const cells = [];
for (let y = 0; y < N; y++) {
  for (let x = 0; x < N; x++) {
    cells.push({ x, y, morton: morton(x, y), rowMajor: y * N + x });
  }
}
// Z-order rank = position in list sorted by morton code
const zSorted = [...cells].sort((a, b) => a.morton - b.morton);
cells.forEach(c => { c.zRank = zSorted.indexOf(c); });

// DOM
const grid = document.getElementById('grid');
const info = document.getElementById('info');
let mode = 'z'; // 'z' | 'row' | 'none'
let selected = null;

function renderCells() {
  grid.innerHTML = '';
  cells.forEach(c => {
    const div = document.createElement('div');
    div.className = 'cell';
    div.dataset.x = c.x; div.dataset.y = c.y;
    div.innerHTML =
      `<span class="coord">(${c.x},${c.y})</span>` +
      `<span class="morton">M=${c.morton.toString(2).padStart(4,'0')}<sub>2</sub>=${c.morton}</span>`;
    div.addEventListener('mouseenter', () => showInfo(c));
    div.addEventListener('click', () => { selected = c; showInfo(c); });
    grid.appendChild(div);
  });
}

function cellDiv(x, y) {
  return grid.querySelector(`[data-x="${x}"][data-y="${y}"]`);
}

function applyHighlight() {
  // clear all
  grid.querySelectorAll('.cell').forEach(d => {
    d.classList.remove('z-hi', 'r-hi');
    const b = d.querySelector('.rank-badge');
    if (b) b.remove();
  });
  if (mode === 'z') {
    zSorted.forEach((c, rank) => {
      const d = cellDiv(c.x, c.y);
      if (d) {
        d.classList.add('z-hi');
        const b = document.createElement('span');
        b.className = 'rank-badge'; b.textContent = rank;
        d.appendChild(b);
      }
    });
  } else if (mode === 'row') {
    const rowSorted = [...cells].sort((a, b) => a.rowMajor - b.rowMajor);
    rowSorted.forEach((c, rank) => {
      const d = cellDiv(c.x, c.y);
      if (d) {
        d.classList.add('r-hi');
        const b = document.createElement('span');
        b.className = 'rank-badge'; b.textContent = rank;
        d.appendChild(b);
      }
    });
  }
}

function showInfo(c) {
  const bitsX = c.x.toString(2).padStart(2, '0');
  const bitsY = c.y.toString(2).padStart(2, '0');
  const mortonBits = c.morton.toString(2).padStart(4, '0');
  info.innerHTML =
    fmt('Cell <strong>(x=%x%, y=%y%)</strong> &mdash; x bits: <strong>%bitsX%</strong>, y bits: <strong>%bitsY%</strong> &rarr; Morton bits (y₁x₁y₀x₀): <strong>%mortonBits%</strong> = <strong>%morton%</strong><br>Z-order rank: <strong>%zRank%</strong> &nbsp;|&nbsp; Row-major rank: <strong>%rowMajor%</strong>', { x: c.x, y: c.y, bitsX: bitsX, bitsY: bitsY, mortonBits: mortonBits, morton: c.morton, zRank: c.zRank, rowMajor: c.rowMajor });
}

document.getElementById('btnZ').addEventListener('click', function() {
  mode = 'z';
  document.getElementById('btnZ').classList.add('active');
  document.getElementById('btnRow').classList.remove('active');
  applyHighlight();
});
document.getElementById('btnRow').addEventListener('click', function() {
  mode = 'row';
  document.getElementById('btnRow').classList.add('active');
  document.getElementById('btnZ').classList.remove('active');
  applyHighlight();
});
document.getElementById('btnClear').addEventListener('click', function() {
  mode = 'none';
  document.getElementById('btnZ').classList.remove('active');
  document.getElementById('btnRow').classList.remove('active');
  applyHighlight();
});

renderCells();
applyHighlight(); // start with Z-path shown

// Log verification data to console for node testing
console.log('VERIFY:morton(0,0)=' + morton(0,0));
console.log('VERIFY:morton(1,0)=' + morton(1,0));
console.log('VERIFY:morton(0,1)=' + morton(0,1));
console.log('VERIFY:morton(1,1)=' + morton(1,1));
console.log('VERIFY:morton(3,3)=' + morton(3,3));
console.log('VERIFY:zRank(0,0)=' + cells.find(c=>c.x===0&&c.y===0).zRank);
console.log('VERIFY:zRank(1,0)=' + cells.find(c=>c.x===1&&c.y===0).zRank);
Result
Console

The key insight: checking whether two points are near each other in Z-order takes a single subtraction. Finding an entire neighborhood is a range query on sorted integers — exactly what B-trees and hash indexes are optimised for.

The Real Complexity

The Z-order curve is a solved, efficiently computable function — not a hard problem, but a clever encoding with a precise locality guarantee.

Status: solved (G. M. Morton, IBM, 1966). The Morton code of (x, y) is computed in O(1)O(1) time on modern hardware using the PDEP (parallel bits deposit) instruction, which interleaves bits in a single CPU clock.

The locality guarantee is the key theorem: if two points (x1x_{1}, y1y_{1}) and (x2x_{2}, y2y_{2}) both lie inside a 2k2^{k} × 2k2^{k} aligned square, their Morton codes differ by at most 22k2^{2k} − 1. In plain English: cells in the same small square are always within a bounded numeric distance in Z-order.

What Z-order cannot promise: the guarantee works in one direction. Small Morton-code difference does not guarantee spatial closeness. Two points can have adjacent Morton codes but be far apart on the grid — this happens at the "folds" of the Z-path where it jumps between quadrants. For a perfect locality guarantee in both directions, Hilbert curves do better — but they are harder to compute.

Complexity class: computing a Morton code is in P (in fact, O(1)O(1) with PDEP). Nearest-neighbor search using Morton-ordered indexes achieves O(log⁡N)O(\log N) per query, matching the information-theoretic lower bound for comparison-based search.

The Z-order curve sits comfortably in the "solved" column: a simple formula, a fast implementation, and a proven guarantee — with well-understood trade-offs compared to Hilbert and other space-filling curves.

Where It Matters

The Z-order curve is one of those ideas that quietly shows up everywhere spatial data needs to be stored or searched efficiently:

  • Spatial databases (PostGIS, BigQuery GIS): Morton codes let a standard B-tree index serve 2D range queries. Instead of building a specialised 2D tree, you index the Morton code of each point and query it like any integer range.
  • GPU texture memory: graphics cards store textures in Z-order (or similar tiled layouts) so that nearby pixels — which are frequently read together during texture sampling — map to nearby memory addresses, maximising cache hits.
  • Geographic information systems: map tile systems (Google Maps, OpenStreetMap) use Morton-like quadtree keys so that tiles covering adjacent areas have nearby keys, making bulk downloads and caches predictable.
  • Cloud key-value stores (Amazon DynamoDB, Google Bigtable): composite keys built from Morton codes let these systems do efficient geo-range scans without a dedicated geospatial index.
  • R-trees and k-d trees: many spatial index structures internally use Z-order to choose split points and to pack leaf nodes, improving cache performance.
  • Point cloud compression (LiDAR): 3D Morton codes (interleaving three coordinates) sort billions of LiDAR points so that nearby points compress together, shrinking file sizes dramatically.

Whenever you need to store multidimensional data in a flat structure and still answer "give me everything near this point" quickly, the Z-order curve is usually the first tool to reach for — it needs no special index, just a sort.

Conclusion

The Z-order curve is a reminder that a small, elegant idea can have enormous reach. Morton's 1966 insight — interleave the bits, turn 2D into 1D — requires no advanced mathematics, runs in a single CPU instruction on modern hardware, and yet it underlies the spatial indexes of major databases, the texture caches of every modern GPU, and the tile systems of the maps we use every day.

It is not perfect: the locality guarantee has a direction, and at quadrant boundaries the Z-path can jump. But for most practical workloads, the simplicity and speed of Morton codes outweigh these edge cases, and the trade-offs are well understood.

If you ever need to store a table of 2D points and later answer rectangle queries quickly, start here: compute the Morton code of each point, sort the table by that code, and use a standard range index. You will have built a spatial index that rivals dedicated tree structures — in a single afternoon, with no special libraries. That is the power of a well-chosen encoding.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/z-order-curve/Content licensed under CC BY-NC 4.0.