#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

#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.

#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.

# 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}

#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.

# 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.

#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.

#Related

• Space-Filling Curves for Spatial Partitioning — parent topic: the full ordering workflow and production writer
• Quadtree vs R-Tree Index Build Time — when curve ordering is not enough and you need a tree index
• Row Group Sizing Strategies for Parquet — how group size compounds with curve choice
• Spatial Partitioning with Quadtree Indexes — hierarchical partitioning that layers on top of curve order
• ZSTD Compression Levels for Geospatial Data — codec tuning for the groups a query does read

← Back to Space-Filling Curves for Spatial Partitioning