Two and three dimensions: the first real loss

Why can no ordering preserve proximity in two dimensions, and what does each spatial escape break?

This is where the pruning criterion starts costing something, and the reason is a theorem-like fact, not an engineering limitation.

The argument in short: an ordering is a one-to-one mapping from points onto a line. Take a query region in the unit square. Under any such mapping its image on the line is some set of intervals. If it were always a single interval, the mapping would have to send every planar neighborhood to one contiguous segment. That is impossible, because a point in the plane has neighbors in all directions while a point on a line has two. Some near pairs must land far apart. (This is a sketch of the argument rather than a proof; the conclusion is standard.)

So there are exactly two families of escape, and each breaks something different.

Escape 1: linearize

Interleave or otherwise fold the coordinates into a single ordered key. Examples: Morton / Z-order, Hilbert curves, and their packaged forms geohash, S2 and H3. You keep a one-dimensional index and all its machinery. What you lose is single-run queries: a query rectangle maps to many intervals, and the query becomes "compute a covering set of cells, then do one range seek per cell".

The quantity that matters: the number of runs scales with the perimeter of the query region, not its area. That is the practical cost model for every cell-based spatial index. Intuition: only the border of the region cuts across cell boundaries, so only the border produces extra fragments.

This explains the tuning behavior. Coarser cells mean fewer runs but more false positives to filter out. Finer cells mean precise coverage but more seeks. You are choosing a point on the same seek-count versus scan-volume curve as the sparse index of Index anatomy.

It also explains the ranking among the schemes.

• Z-order has long jumps: adjacent cells on the curve can be far apart in space where bit boundaries are crossed, so coverings are more fragmented.
• Hilbert has no jumps, which is why S2 is built on it.
• H3 uses hexagons, which gives uniform adjacency (six neighbors, all at the same distance, versus a square's four edge neighbors and four corner neighbors at different distances). It pays by giving up exact hierarchical nesting: hexagons do not subdivide into hexagons, so H3's parent-child containment is approximate.

That is a clean instance of the theme: you cannot have uniform adjacency and exact hierarchy, so pick.

The same curves are also used to order the base data. Here the same construction is used to key an index, and the cost model (perimeter-many runs) is specific to this use. The mechanism is shared; the purpose is not.

Escape 2: partition

Build a tree over regions instead of points: the R-tree and its relatives keep proximity exactly but give up disjointness (bounding boxes overlap, so a query may descend several subtrees), and quadtrees keep a disjoint fixed subdivision but give up balance whenever the data is not uniform. How each behaves, and the duplicate-or-overlap trade for objects with extent, are on filter and refine.

This earns a law: