Eight of the site's other Spatial entries — KD-tree, Quadtree,
R-tree, Range
Tree, Ball Tree, VP-Tree, Interval Tree, and BSP Tree — every one of them answers its query by building an
explicit tree: nodes, pointers, a recursive split rule. (Hilbert Curve, added later, shares this page's own
tree-free approach — a different curve, sorted order instead of a pointer structure either way. Spatial Hash Grid, added later still, is tree-free
too, but by a third mechanism again — fixed-size buckets keyed by coordinate division, no sorted order
or curve of any kind.) A
Z-order curve answers the
same "which points fall inside this rectangle" question that KD-tree, Quadtree,
and Range Tree already compete for, but builds no tree at
all. Instead, it interleaves the bits of each point's x and y
coordinate into one number — a Morton code — and sorts points by that number. The
result is a plain flat array (or, in a real database, an ordinary indexed column) with no pointers, no
recursive build step, and no bespoke tree code to write: a 2D indexing problem turned into a 1D sorting
problem, at the cost of a real, measurable amount of wasted scanning this page's Pitfalls section
quantifies directly.
Ten points, each labeled with its grid coordinate. Press Step or Run to watch the build phase draw the Z-order curve itself — the zigzag line connecting every point in sorted-by-Morton-code order, the literal "Z" the curve is named for repeating at every scale — then switch to a range query for the dashed rectangle. The query rectangle deliberately straddles this domain's own halfway line on both axes (drawn dotted): watch the scan step through every point whose Morton code falls between the rectangle's two corners, and pay attention to which of those get accepted (inside the rectangle) versus rejected (inside the numeric code range, but not actually inside the rectangle) — that gap is the whole story below.
Interleaving takes each coordinate's bits and shuffles them together, alternating
between the two: bit 0 of x becomes bit 0 of the result, bit 0 of y becomes bit
1, bit 1 of x becomes bit 2, and so on. A point (x, y) becomes one integer, its
Morton code, and sorting points by that single number gives a total order over 2D space
that keeps spatially-close points numerically close most of the time — recursively, because the
top two bits of the code split the whole domain into four quadrants (low-y/low-x, low-y/high-x,
high-y/low-x, high-y/high-x, in that numeric order), and every deeper bit pair repeats the same split one
level finer inside whichever quadrant a point already landed in. That's the recursive "Z" shape the demo
draws: within any single quadrant, the curve visits its own four sub-quadrants in the same low-low,
low-high, high-low, high-high order, at every scale.
A range query for rectangle [xlo,xhi] × [ylo,yhi] computes just two
Morton codes — zmin from the rectangle's low corner (xlo,ylo) and
zmax from its high corner (xhi,yhi) — and binary-searches the sorted array for
the slice between them. That slice is guaranteed to contain every point actually inside the
rectangle: any point with x between xlo and xhi and
y between ylo and yhi always has a Morton code between
zmin and zmax, a property confirmed below by exhaustively checking every
point/rectangle pair over a whole domain, not just assumed from how the bits look. What it isn't
guaranteed to be is tight: the numeric range between two corners' codes can also contain points
far outside the rectangle whose codes just happen to fall between them, because the curve has to leave
the rectangle and come back to cover other quadrants along the way. Each candidate in the scanned slice
still gets a real two-coordinate check against the actual rectangle — correct either way, just not
free.
function interleave(x, y) {
// Traded for clarity over speed: a real implementation typically uses a handful of
// magic-bitmask shifts to interleave in O(1), not a bit-by-bit loop.
let z = 0;
for (let i = 0; i < 16; i++) {
z |= ((x >> i) & 1) << (2 * i);
z |= ((y >> i) & 1) << (2 * i + 1);
}
return z;
}
function buildIndex(points) {
// No tree, no pointers -- just a Morton code per point and a sort.
return points
.map(p => ({ ...p, z: interleave(p.x, p.y) }))
.sort((a, b) => a.z - b.z);
}
function lowerBound(sorted, z) {
let lo = 0, hi = sorted.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (sorted[mid].z < z) lo = mid + 1; else hi = mid;
}
return lo;
}
function rangeQuery(sorted, xlo, xhi, ylo, yhi) {
const zmin = interleave(xlo, ylo);
const zmax = interleave(xhi, yhi);
const results = [];
let i = lowerBound(sorted, zmin);
while (i < sorted.length && sorted[i].z <= zmax) {
const p = sorted[i];
if (p.x >= xlo && p.x <= xhi && p.y >= ylo && p.y <= yhi) results.push(p);
i++;
}
return results;
}A query rectangle that straddles a power-of-2 boundary pays a real, measured scanning
penalty — an identically-sized rectangle that happens to line up with the grid doesn't. Built a
Morton index over 5,000 points scattered uniformly across a 1024×1024 domain, then ran 2,000 range
queries with a fixed 32×32 window: placed at a random offset (so it straddles power-of-2 boundaries most
of the time), the scan touched 34.36× as many candidates as it actually matched, on
average (169.86 scanned per query against 4.94 real matches). The exact same window size, placed only at
offsets that are themselves multiples of 32 (so it always lines up with a boundary the curve already
splits on), touched exactly as many candidates as matches — a 1.00× ratio, zero waste,
over the same 2,000-trial count. Nothing about the point data changed between the two runs; the entire
difference is where the rectangle happens to sit relative to the domain's own quadrant grid. The small
demo above reproduces the same effect at a scale small enough to read by hand: its query rectangle
straddles both of the 16-unit domain's own halfway lines, and 3 of the 6 points whose Morton code falls
in [zmin,zmax] — a full half — turn out to sit outside the actual rectangle once checked.
It's tempting to assume a straddling rectangle can also silently miss real matches,
the same way a naive split on raw coordinate ranges might — it can't, but that guarantee is worth
confirming rather than trusting. Exhaustively checked every rectangle against every point it
actually contains across a full 32×32 domain (34,848 distinct rectangles, 4,344,384 point/rectangle
pairs): zero cases where a point genuinely inside the rectangle had a Morton code outside
[zmin,zmax]. The waste measured above is real, but it's only wasted scanning, never
a wrong answer — the two are different failure modes, and this page's numbers above only checked the
first one until this exhaustive pass checked the second.
The interleave loop's fixed bit width is a silent ceiling, not a safety check. This
reference implementation only reads each coordinate's lowest 16 bits — fine for any coordinate under
65,536, but a coordinate that exceeds it doesn't error or clamp, it just wraps: interleave(5,
9) and interleave(5 + 65536, 9) both return 147, an exact collision,
confirmed directly. Two genuinely different points become indistinguishable in the sorted index,
silently merged as far as any query is concerned. The fix is choosing a bit width that actually covers
the real coordinate domain up front, not a fixed constant copied from an example.
The reason to reach for this over a bespoke tree is almost never raw query speed — the waste measured
above shows it can lose that comparison outright. It's that a Morton code turns a 2D (or higher-dimensional,
by interleaving more coordinates' bits together the same way) indexing problem into an ordinary 1D
sorting problem, which means it can piggyback on infrastructure that already exists rather than requiring
new pointer-based tree code: a plain sorted array, a skip list, a hash table, or — most commonly in
practice — an ordinary B-tree column index inside a database that was never built with spatial queries in
mind. Geohash, the base-32 string encoding behind location sharing and proximity search
in many web APIs, is a Z-order variant under a text encoding. MongoDB's legacy 2d index
buckets and sorts geospatial points with a Z-order curve for exactly this reason, and Oracle Spatial's
Z-ordering scheme is described as a linear quadtree built the same way. DynamoDB and Bigtable both use
Z-order-style spatial keys to let range queries over multi-dimensional data ride on a single-dimension
key-value store's existing indexing, with no separate spatial engine at all.
Production systems frequently swap in a Hilbert curve instead of Z-order for the same bit-interleaving role: it visits every cell via only single-step moves (never the diagonal "jump" a Z-order curve makes between some quadrants), which measurably improves locality along the curve itself. That better locality is not a free upgrade for this page's own range-query trick, though — the Hilbert Curve page ports this exact query technique onto this exact demo's points and rectangle and measures a real false negative, not just extra scanning, then measures where the locality win does pay off instead (tighter R-tree bulk-load bounding boxes).
Against the site's other point-indexing entries: reach for KD-tree, Quadtree, or Range Tree when the query performance itself has to be good on typical or worst-case data and a bespoke tree is an acceptable amount of code to own. Reach for a Z-order curve when the actual constraint is infrastructural — an existing sorted store, a database column that only offers range queries on plain values, or a distributed key-value store with no concept of 2D space at all — and some measured scan waste on awkwardly-placed queries is an acceptable trade for not building or maintaining a spatial tree.
Build: O(n log n) — compute one Morton code per point in
O(1) (or O(bits) for this reference implementation's bit-by-bit loop), then
sort. Space: O(n) — one Morton code stored alongside each point, no
duplication and no pointers, unlike Range Tree's
O(n log n).
Query: O(log n) to binary-search the starting position, plus
O(scanned) to walk and filter the candidate slice — scanned is at least
k (the real match count) but, as the first Pitfall measures directly, can run past
30× higher for an unluckily-placed query rectangle, with no guarantee in between the way Range Tree's O(log² n + k) bound offers. This
site's guide, Choosing a Spatial Structure,
compares this entry against the other seven Spatial entries that share the same "index points, query
later" question side by side.