H3 vs geohash cell indexing for zone lookups

A cell index turns a position into a short key that any store can look up — a string in a dictionary, a row in SQLite, a topic segment in a message. That property is why it survives on gateways even though a packed R-tree is faster in-process: the key can leave the process. This guide compares the two schemes a field deployment realistically uses, within the envelope described in spatial indexing on constrained devices and the wider Local Spatial Processing Patterns guide.

The two schemes, and what actually differs #

Geohash interleaves the bits of latitude and longitude and base-32 encodes the result. Each character adds five bits, alternating between the two axes, so cells are rectangles whose aspect ratio flips with every character and whose ground size shrinks toward the poles. The encoder is thirty lines of arithmetic with no tables and no dependencies.

H3 tiles the sphere with hexagons on an icosahedral projection, indexed by a 64-bit integer that encodes resolution and a path down the hierarchy. Hexagons have one property that matters operationally: every neighbour is the same distance away, which removes the diagonal-versus-orthogonal asymmetry that makes geohash proximity logic awkward. The cost is a real library — the reference implementation is several thousand lines of C — and twelve pentagons on the globe where the neighbour count is five rather than six.

The choice on a gateway usually comes down to three questions: does the index key have to cross a process or a wire; is proximity logic (rings, neighbours, distance-bounded searches) part of the workload; and can the image carry a compiled dependency.

A dependency-free geohash encoder #

If the deployment can live with rectangles, the whole scheme fits on one screen and adds nothing to the image:

# geohash.py — encode/decode with no dependencies, no tables beyond the alphabet.
# Pure integer and float arithmetic; safe to call from a hot loop.
_B32 = "0123456789bcdefghjkmnpqrstuvwxyz"


def encode(lat: float, lon: float, precision: int = 6) -> str:
    lat_lo, lat_hi = -90.0, 90.0
    lon_lo, lon_hi = -180.0, 180.0
    out = []
    bits = 0
    bit_count = 0
    even = True                       # even bits split longitude
    while len(out) < precision:
        if even:
            mid = (lon_lo + lon_hi) / 2
            if lon > mid:
                bits = (bits << 1) | 1
                lon_lo = mid
            else:
                bits <<= 1
                lon_hi = mid
        else:
            mid = (lat_lo + lat_hi) / 2
            if lat > mid:
                bits = (bits << 1) | 1
                lat_lo = mid
            else:
                bits <<= 1
                lat_hi = mid
        even = not even
        bit_count += 1
        if bit_count == 5:
            out.append(_B32[bits])
            bits = 0
            bit_count = 0
    return "".join(out)


def neighbours(gh: str) -> list[str]:
    """The eight surrounding cells, computed by re-encoding offset centres.
    Slower than bit manipulation and immune to the prefix-boundary bugs that
    hand-rolled neighbour tables are famous for."""
    lat, lon, dlat, dlon = decode_with_error(gh)
    out = []
    for dy in (1, 0, -1):
        for dx in (-1, 0, 1):
            if dx == 0 and dy == 0:
                continue
            out.append(encode(lat + dy * dlat * 2, lon + dx * dlon * 2, len(gh)))
    return out


def decode_with_error(gh: str):
    """Cell centre and half-extents — the inverse of encode."""
    lat_lo, lat_hi = -90.0, 90.0
    lon_lo, lon_hi = -180.0, 180.0
    even = True
    for ch in gh:
        idx = _B32.index(ch)
        for shift in (4, 3, 2, 1, 0):
            bit = (idx >> shift) & 1
            if even:
                mid = (lon_lo + lon_hi) / 2
                if bit:
                    lon_lo = mid
                else:
                    lon_hi = mid
            else:
                mid = (lat_lo + lat_hi) / 2
                if bit:
                    lat_lo = mid
                else:
                    lat_hi = mid
            even = not even
    return ((lat_lo + lat_hi) / 2, (lon_lo + lon_hi) / 2,
            (lat_hi - lat_lo) / 2, (lon_hi - lon_lo) / 2)

Computing neighbours by re-encoding offset centres rather than by manipulating the base-32 string is a deliberate trade: it costs eight encodes instead of eight increments, and it is correct across every prefix boundary and at the antimeridian, which the string-manipulation version famously is not.

Constraint validation #

The third row deserves a caveat: the CPU figures only matter at rates above a few thousand fixes per second, which almost no gateway reaches. In practice both are free, and the row that decides the outcome is the first or the fourth.

Gotchas and edge cases #

• A cell is not a zone. Both schemes answer “which cell is this point in”, never “which zone contains it”. The cell is a bucket key; the exact predicate still has to run, exactly as in the funnel described in on-device geometry filtering.
• One lookup is a bug. A fix near a cell edge belongs to a zone indexed in the neighbouring cell. Probing the centre cell plus its ring is mandatory in both schemes; the difference is that H3’s ring is six cells and geohash’s is eight.
• Precision is not accuracy. A geohash 7 cell is about 153 m across; encoding a fix to precision 9 does not make the position better, it makes the bucket smaller and the neighbour probe more expensive.
• Geohash sorts lexicographically; H3 does not. If the design relies on range scans over a sorted key store — WHERE gh BETWEEN 'u33d' AND 'u33e' — geohash gives that for free and H3 does not, because its integer ordering follows the hierarchy rather than space.
• H3 pentagons break the uniform assumption. Twelve cells worldwide have five neighbours. Code that assumes six will index one neighbour short there, silently. The library exposes a predicate for it; call it once during ring construction rather than trusting the geometry.
• Do not mix resolutions in one index. A store keyed on cells at two resolutions cannot answer a lookup without probing both, which doubles the work and usually indicates that two separate indexes were wanted.

Integrating with the reference store #

Whichever scheme is chosen, the shape of the integration is the same — a dictionary from cell key to the feature ids whose envelope touches that cell, built once at load and treated as immutable:

def build_cell_index(features, encode_cell, precision):
    """cell key → feature ids. Built once; replaced wholesale on layer change."""
    index: dict[str, list[int]] = {}
    for fid, geom in enumerate(features):
        for lat, lon in geom.envelope_sample_points(precision):
            index.setdefault(encode_cell(lat, lon, precision), []).append(fid)
    return {k: tuple(sorted(set(v))) for k, v in index.items()}


def candidates(index, encode_cell, neighbour_fn, lat, lon, precision):
    """Centre cell plus its ring — never the centre cell alone."""
    keys = [encode_cell(lat, lon, precision)]
    keys.extend(neighbour_fn(keys[0]))
    seen = set()
    for k in keys:
        seen.update(index.get(k, ()))
    return seen

Feed the result into the exact predicate as usual. When the same keys are used to shard work across processes or to route messages, keep the resolution in the key’s metadata rather than inferring it from length — a consumer that guesses wrong produces an empty join with no error, which is the failure mode this whole section exists to avoid.

Picking a resolution from the zone size #

Resolution is the parameter that decides whether the scheme works, and it follows from the features rather than from the query. Choose the resolution whose cell is roughly the size of the median zone: larger cells put many zones in one bucket and turn a lookup into a scan, smaller cells spread one zone across many buckets and inflate the index without improving selectivity.

For geohash, precision 5 gives cells of about 4.9 by 4.9 km, precision 6 about 1.2 km by 610 m, and precision 7 about 153 m square. For H3, resolution 7 has an average edge length near 1.2 km, resolution 8 near 460 m and resolution 9 near 174 m. A yard-scale zone set — loading bays, parking areas, buildings — lands on geohash 7 or H3 9; a regional set of administrative or operational areas lands on geohash 5 or H3 7.

Where zone sizes span orders of magnitude, use two indexes at two resolutions rather than a compromise resolution, and query the one whose scale matches the question. A compromise resolution is worse than either for both.

Related #

• Spatial Indexing on Constrained Devices — where cell schemes sit among the alternatives.
• Geohash bucketing for point-in-zone joins — the bucket-skew problem that decides precision.
• Packed Hilbert R-tree in a static buffer — the in-process alternative when the key never leaves.