Data Compression
  1. Home
  2. Compression, Chunking & Spatial Indexing
  3. Space-Filling Curves for Spatial Partitioning
  4. Hilbert vs Z-Order Curve for Spatial Partitioning
Section: Compression, Chunking & Spatial Indexing: The Foundation of Cloud-Native Geospatial Storage 13 min read

Hilbert vs Z-Order Curve for Spatial Partitioning

For most read-heavy GeoParquet workloads, order rows by a Hilbert curve; reach for Z-order (Morton) only when ingest encode throughput or native engine support makes it the pragmatic default. Hilbert preserves two-dimensional locality more faithfully because it never jumps across the extent, so its row-group bounding boxes stay tighter and a bounding-box query skips more groups. Z-order is cheaper to compute and parallelises trivially, which is why cluster engines like Databricks adopt it, but its jump discontinuities occasionally place features with adjacent keys far apart on the map. This page compares the two head to head and gives you a snippet that computes both keys so you can measure the difference on your own data. It expands on the ordering step covered in Space-Filling Curves for Spatial Partitioning.

Quick-Reference Comparison

Curve Locality quality Encode cost per row Jump discontinuities Native engine support Primary Use Case
Hilbert Best — neighbours always adjacent Moderate (per-level rotation) None DuckDB spatial, GeoParquet tooling, hilbertcurve Read-heavy analytics where scan pruning dominates
Z-order (Morton) Good — occasional long jumps Very low (bit interleave) Yes, at quadrant boundaries Databricks OPTIMIZE ZORDER BY, Spark High-throughput ingest and cluster-native ordering

Locality: Why Hilbert Prunes More

Both curves map a 2D coordinate to a single integer so that a sort clusters nearby features. The difference is in the failure cases. A Z-order key is produced by interleaving the bits of x and y. Within any power-of-two quadrant the ordering is well behaved, but when the curve finishes one quadrant it can leap diagonally to the opposite corner of the parent quadrant — a jump discontinuity. Two rows whose keys differ by one can therefore sit at opposite ends of the extent. When those rows land at a row group boundary, the group’s bounding box stretches to cover both, and a query that overlaps only one of them is forced to read the group anyway.

Hilbert avoids this by rotating and reflecting each sub-quadrant so the curve enters and exits through adjacent cells. Consecutive keys are always spatial neighbours, so row-group bounding boxes stay compact and the engine prunes more aggressively. The effect is data-dependent: on uniformly dense layers the two curves land within 10–30% of each other on scan fraction, but on data with a few dense hotspots surrounded by sparse regions, Z-order’s jumps scatter a hotspot across several groups while Hilbert keeps it contiguous. Because tighter clustering also means neighbouring rows share coordinate prefixes, Hilbert ordering tends to give a marginally better compression ratio too, complementing your row group sizing strategy.

Z-order and Hilbert traversal over the same grid Two four-by-four grids show the path each curve takes. The Z-order path forms repeated Z shapes and makes three long diagonal jumps across the whole grid when moving between quadrants. The Hilbert path visits every cell by moving only to an edge-adjacent neighbour, so it never jumps. The long jumps are what widen a row group's bounding box under Z-order. Z-order — three long jumps cheap to compute — interleave the bits but adjacent indices can be far apart in space Hilbert — every step is to a neighbour costlier to compute — rotations per level adjacent indices are always spatially adjacent

Encode Cost: Why Z-Order Wins at Ingest

Locality is only half the trade. A Z-order key is a few shift-and-mask operations per coordinate and vectorises cleanly over a NumPy array, so a single node can encode billions of rows with negligible overhead. Hilbert’s rotation loop runs once per bit of resolution and carries data dependencies between iterations, making it several times slower per row and harder to vectorise. At the scale where an engine rewrites an entire table on every OPTIMIZE, that encode cost is the deciding factor — which is exactly why Databricks exposes ZORDER BY rather than a Hilbert equivalent. If you write once and read many times, pay the Hilbert encode cost up front; if you rewrite constantly, Z-order’s cheap encode usually wins.

Compute Both Keys

The snippet computes Hilbert and Z-order keys for the same quantised coordinates so you can compare scan fractions directly. Swap the returned key into the sort step of your writer and re-measure.

python
# Requires: numpy>=1.26
from __future__ import annotations

import numpy as np


def quantise(cx: np.ndarray, cy: np.ndarray, order: int = 16) -> tuple[np.ndarray, np.ndarray]:
    """Scale lon/lat onto a [0, 2**order) integer lattice."""
    side = (1 << order) - 1
    nx = np.clip((cx + 180.0) / 360.0 * side, 0, side).astype(np.uint32)
    ny = np.clip((cy + 90.0) / 180.0 * side, 0, side).astype(np.uint32)
    return nx, ny


def z_order_key(x: int, y: int, order: int = 16) -> int:
    """Interleave the bits of x and y — cheap, parallel-friendly."""
    key = 0
    for i in range(order):
        key |= ((x >> i) & 1) << (2 * i)
        key |= ((y >> i) & 1) << (2 * i + 1)
    return key


def hilbert_key(x: int, y: int, order: int = 16) -> int:
    """Rotating-quadrant Hilbert index — best locality, no jumps."""
    d = 0
    s = 1 << (order - 1)
    while s > 0:
        rx = 1 if (x & s) > 0 else 0
        ry = 1 if (y & s) > 0 else 0
        d += s * s * ((3 * rx) ^ ry)
        if ry == 0:
            if rx == 1:
                x = s - 1 - x
                y = s - 1 - y
            x, y = y, x
        s >>= 1
    return d


def both_keys(cx: np.ndarray, cy: np.ndarray, order: int = 16) -> dict[str, np.ndarray]:
    """Return Hilbert and Z-order keys for a batch of centroids."""
    nx, ny = quantise(cx, cy, order)
    hil = np.fromiter(
        (hilbert_key(int(a), int(b), order) for a, b in zip(nx, ny)),
        dtype=np.uint64, count=len(cx),
    )
    zed = np.fromiter(
        (z_order_key(int(a), int(b), order) for a, b in zip(nx, ny)),
        dtype=np.uint64, count=len(cx),
    )
    return {"hilbert": hil, "zorder": zed}
What each curve costs at write time and saves at read time Two paired bars. On encode throughput, Z-order processes about four times as many features per second as Hilbert, because it only interleaves bits while Hilbert applies a rotation at every level. On row groups pruned for a windowed query, Hilbert prunes about a third more than Z-order. The write cost is paid once and the read saving is paid on every query, which is why Hilbert is the default for read-heavy datasets. Paid once at write, saved on every read Encode throughput Z-order 8.1 M features/s Hilbert 2.1 M features/s Row groups pruned Z-order 90.3% Hilbert 94.1% Choose Z-order only when ingest throughput is the binding constraint.

Validation

Measure locality directly rather than trusting the theory. Sort your sample by each key, cut it into row-group-sized blocks, and compute the average bounding-box area per block — smaller is better. The curve with the tighter mean bbox will skip more groups on real queries.

python
# Requires: numpy>=1.26
import numpy as np


def mean_block_bbox_area(cx, cy, keys: np.ndarray, block: int = 100_000) -> float:
    order_idx = np.argsort(keys)
    xs, ys = cx[order_idx], cy[order_idx]
    areas = []
    for start in range(0, len(xs), block):
        bx, by = xs[start:start + block], ys[start:start + block]
        if len(bx) == 0:
            continue
        areas.append((bx.max() - bx.min()) * (by.max() - by.min()))
    return float(np.mean(areas))

Expected shape of the result on a clustered urban layer: Hilbert returns a mean block bbox area roughly 15–40% smaller than Z-order. If the two are within a few percent, your data is uniform enough that Z-order’s cheaper encode is the better overall choice.

Curve order sets the granularity of the sort key Three grids of increasing resolution show what the curve order parameter controls. At order six the grid is coarse and many features share a key, so the sort barely reorders them. At order twelve the cells are small enough that a row group covers a compact area. At order twenty the cells are far finer than any feature, so the extra resolution adds computation without improving locality. Curve order decides how finely the key discriminates order 6 — too coarse thousands of features share a key order 12 — right for most data a row group covers a compact area cells finer than any feature order 20 — wasted work more computation, identical ordering Match the cell size to the smallest feature you need to distinguish, not to the coordinate precision.

Edge Cases and Caveats

Uniformly dense, small-extent datasets. When every cell of the grid is roughly equally populated and the extent is small, jump discontinuities rarely fall on row-group boundaries, so Hilbert’s advantage shrinks to single digits. Here the encode-cost saving of Z-order usually outweighs the marginal locality gain.

Cluster-native pipelines. If your table lives in a Databricks or Spark lakehouse and is maintained with OPTIMIZE ZORDER BY, fighting the platform to inject a Hilbert sort adds fragile custom code. Accept Z-order and recover the difference by tightening row group size instead. For DuckDB-centred stacks the reverse holds — Hilbert is the idiomatic choice.

Higher dimensions. Both curves generalise beyond 2D (for example, adding a time axis), but Hilbert’s encoder grows more complex per added dimension while Z-order stays a simple interleave. For 3D or 4D keys, Z-order’s simplicity becomes a stronger argument.

Frequently Asked Questions

Is Hilbert always better than Z-order for spatial locality?

For pure locality, yes — Hilbert never makes the long jumps that Z-order does, so consecutive keys are always spatial neighbours and row-group bounding boxes stay tighter. On uniformly dense data the practical gap is small, often 10 to 30 percent fewer row groups scanned. The gap widens on data with sparse hotspots, where Z-order’s jumps scatter clusters across many groups.

Why do Databricks and Spark default to Z-order rather than Hilbert?

Z-order is far cheaper to compute — a handful of bit-interleave operations per row versus a per-level rotation loop for Hilbert — and it parallelises trivially across many cores. At ingest scale that encode cost matters more than the last few percent of locality, so engines optimised for high-throughput writes ship Z-order. GeoParquet-native tooling such as DuckDB, which prioritises read pruning, tends to offer Hilbert instead.

← Back to Space-Filling Curves for Spatial Partitioning