skip to content

Why might a proximity service index points with S2 or H3 cells instead of geohash rectangles when working on a spherical Earth?

level: seniorimportance: nice to knowfreq 30%

answer

  1. a flat grid on a round planet
  2. six faces of a cube
  3. a curve without long jumps
  4. six equidistant neighbours
  5. points versus shapes

basics

~20 s

Geohash cells come from a flat lat/lng grid, so they distort with latitude and jump along a Z-order curve. S2 cube-face cells with Hilbert ordering and hexagonal H3 cells keep sizes more uniform and neighbours more regular.

solid answer

~50 s

Geohash slices latitude and longitude as if the Earth were flat, so cells narrow toward the poles, even lengths are 2:1 rectangles and the Z-order curve makes jumps that split nearby areas into many key ranges. **S2** projects the sphere onto the six faces of a cube, subdivides each face as a quadtree and numbers cells along a **Hilbert curve** into 64-bit IDs; cells vary less in size, nest exactly, and a circle or polygon can be covered by a small set of cells of mixed levels, which becomes a handful of ID range scans. **H3** tiles the sphere with **hexagons** at many resolutions; every hexagon's six neighbours are the same distance away, so rings of cells approximate circles well and suit aggregation such as demand heatmaps. The costs: H3 needs a few pentagons and its child cells only approximately nest in their parents, and both need a library rather than a hand-written encoder.

go deeper

for a junior

Recall that geohash is a flat grid laid over a round Earth, and that other cell systems exist to reduce the distortion that causes.

for a middle

Explain the cube-face projection and Hilbert ordering behind S2 and the equal-distance neighbours of hexagons, and how each still reduces to range scans on IDs.

for a senior

Match the scheme to the workload: coverings and exact containment, rings and aggregation, or an R-tree for shapes, and name the pentagon and nesting caveats.

for a principal

Treat the cell system as a long-lived data contract: IDs end up in storage, analytics and caches, so weigh migration cost and library dependence against distortion gains.

## Where geohash falls short A **geohash** is a Z-order key over a flat grid of latitude and longitude. That simplicity has three consequences on a real sphere: - **Size distortion.** A degree of longitude spans less ground toward the poles, so cells of one length get narrower as latitude rises; at 60 degrees they are about half as wide as at the equator. - **Shape.** Even-length cells are 2:1 rectangles, so coverage rules must use the shorter side. - **Curve jumps.** The Z-order curve occasionally leaps across the map, so a small search area can straddle cells whose keys are far apart, needing several range scans. - **Uneven neighbours.** A square cell has four edge neighbours and four corner neighbours, and the corner ones are about 1.4 times farther away. For city-scale 'nearby' search none of this is fatal. It matters for global coverage, polar regions, analytics that compare cells, and polygon-heavy workloads. ## S2: a cube wrapped around the sphere **S2** is a hierarchical cell system: 1. Project the sphere onto the **six faces of a cube**, with a transform that reduces area distortion. 2. Subdivide each face as a **quadtree**, giving 31 levels from whole faces (level 0) down to cells around a square centimetre (level 30). 3. Number cells along a **Hilbert curve** and pack face, path and level into a **64-bit cell ID**. Properties that matter for indexing: - **Better locality.** The Hilbert curve has no long jumps between consecutive cells, so a compact region maps to fewer ID ranges than with Z-order. - **Exact nesting.** Every cell contains exactly four children, and a parent's ID range contains all its descendants' IDs, so containment is a range check. - **Region coverings.** A covering algorithm approximates a circle or polygon with a small set of cells of mixed levels, big cells in the interior and small ones along the edge. Each cell becomes one range scan on an ordinary sorted index of 64-bit integers. ## H3: hexagons on an icosahedron **H3** tiles the sphere with **hexagons**, built on an icosahedron, at 16 resolutions (0 to 15). - **Uniform neighbours.** Each hexagon has six neighbours, and all six centres are the same distance away. A **k-ring** (all cells within k steps) therefore approximates a circle much better than a square block does. - **Smooth aggregation.** Equal-distance neighbours make hexagons popular for heatmaps, demand and supply grids and smoothing across adjacent cells. - **Pentagons.** A sphere cannot be tiled with hexagons alone, so each resolution contains **12 pentagons**, which code must tolerate. - **Approximate nesting.** A hexagon's roughly seven children do not exactly fill their parent, so rolling data up the hierarchy is approximate rather than exact. ## Side-by-side | Property | Geohash | S2 | H3 | |---|---|---|---| | Cell shape | lat/lng rectangle | square-ish quadrilateral | hexagon (plus 12 pentagons) | | Ordering | Z-order string | Hilbert-curve 64-bit ID | hierarchical 64-bit index | | Exact parent-child nesting | yes | yes | approximate | | Neighbour distances | two different | two different | all equal | | Typical strength | simplest, any sorted store | precise coverings, containment | rings, aggregation | ## When a cell scheme is the wrong tool: R-trees All three schemes are best at **points**. Rectangles and polygons, such as delivery zones or geofences, are different: - A cell scheme must store each polygon under its **covering**, many cells for a large or irregular shape. - An **R-tree** stores each shape's **minimum bounding rectangle** in a balanced tree whose nodes' rectangles may overlap. A 'which zones contain this point?' query descends into every node whose rectangle contains the point, then runs an exact point-in-polygon test on the candidates. - R-trees also answer kNN with best-first search on rectangle distances. The trade-off is that an R-tree needs an engine or library that maintains it, whereas cell IDs fit any sorted key store. ## Choosing - City-scale nearby search over static points: geohash or quadtree keys are often enough. - Global coverage, polygon coverings or exact containment: a Hilbert-ordered cube-face system. - Rings, smoothing and per-cell analytics: hexagons. - Many overlapping shapes: an R-tree. Whatever the scheme, the query still ends with an **exact distance or containment check**; cells only narrow the candidates.

  • When is an R-tree a better fit than any cell scheme?
    When the indexed objects have extent: delivery zones, geofences, building footprints. An R-tree stores each shape's bounding rectangle once and answers 'which shapes contain this point' by descending into nodes whose rectangles contain it, then testing exact containment. A cell scheme would store every shape under many covering cells and still need the exact test.
  • Why does approximate parent-child nesting matter when rolling up hexagon data?
    If a parent hexagon does not exactly contain its children, summing child counts into the parent assigns some points to a parent whose area does not actually contain them. For heatmaps this error is usually acceptable; for billing, quotas or exact containment checks it is not, and a scheme with exact nesting or a direct recount at the coarser resolution is safer.

saying these in an interview costs you the question

  • S2 and H3 are renamed geohash with the same square cells
  • Geohash cells of one length are equal-area across the globe
  • Hexagon children nest exactly inside their parent hexagon
  • A point cell scheme indexes polygons as easily as points
  • Hexagonal cells remove the need for an exact distance check