Geo Indexing#

Problem statement (interviewer prompt)

Pick the right spatial index for a 'find restaurants within 2km' query at city-block precision, globally, for 1M QPS. Compare Quadtree, Geohash, S2 and H3. Discuss neighbour math, sharding, and how to handle hot cells (Times Square).

flowchart LR
  P[Point or polygon]
  QT[Quadtree]
  GH[Geohash]
  S2[S2 cells]
  H3[H3 hexes]
  RT[R-tree]
  Q[Spatial query]
  P --> QT --> Q
  P --> GH --> Q
  P --> S2 --> Q
  P --> H3 --> Q
  P --> RT --> Q

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class P,QT,GH,S2,H3,RT,Q service;

Five spatial-index choices for "nearby" / "within radius" / "in this polygon" queries: Quadtree, Geohash, S2, H3, R-tree. Pick by data shape, query shape, and how sharded the world needs to be.

The five contenders#

flowchart TB
  subgraph QT[Quadtree]
    QT1[Recursive 4-way split]
    QT2[Adaptive density]
    QT3[Unbalanced if hot spots]
  end
  subgraph GH[Geohash]
    GH1[Z-order curve]
    GH2[String prefix = region]
    GH3[Edge cases at poles + 180 deg]
  end
  subgraph S2[S2 cells]
    S2A[Sphere-aware]
    S2B[Hilbert curve]
    S2C[Levels 0-30]
  end
  subgraph H3[H3 hexagons]
    H3A[Hexes - 6 equidistant neighbours]
    H3B[Resolutions 0-15]
    H3C[No pole edge cases]
  end
  subgraph RT[R-tree]
    RT1[Bounding boxes]
    RT2[Best for polygons]
    RT3[Hard to shard]
  end

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class QT1,QT2,QT3,GH1,GH2,GH3,S2A,S2B,S2C,H3A,H3B,H3C,RT1,RT2,RT3 service;

Cheat sheet#

	Shape	Sphere-aware	Neighbour math	Shard-friendly	Best for
Quadtree	square	no	trivial	yes	dynamic density (cities)
Geohash	square (approx)	no	string prefix	very (string range scan)	KV stores by prefix
S2	spherical square	yes	4-neighbours	yes (cell-id range)	global apps, Google
H3	hexagon	yes	6 equidistant	yes	uber-style indexes
R-tree	bounding rect	no	tree traversal	hard	polygon containment, Postgres GiST

"Find nearby" with cells#

flowchart LR
  Q[Query: point + radius]
  C[Cover with cells]
  S[Scan cells]
  F[Distance filter]
  R[Top-k]
  Q --> C --> S --> F --> R

  classDef p fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
  classDef s fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
  class Q,R p;
  class C,S,F s;

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class Q,C,S,F,R service;

Convert (lat, lng) to cell id at the right level (cell width ≈ radius).
Compute cells covering the search ring.
Range-scan posting list per cell.
Haversine-filter candidates to exact radius.
Sort by distance.

Geohash example#

9q8yyk (San Francisco). First chars = bigger region: - 9 - North-west quarter of the western hemisphere. - 9q - California-ish. - 9q8yyk - block-level.

KV store sharding by geohash prefix → all data for a city lands on adjacent shards.

S2 vs H3#

S2: Google. Hilbert curve preserves locality on integer cell ids → range scans cheap.
H3: Uber. Hexagons are great for "fair" neighbour distances + visualisation.

Many systems pick H3 for indexing + querying, S2 for static partitioning.

R-tree#

Bounding-box hierarchy.
Best for "does polygon contain point?" / "intersect rectangles?".
Postgres / PostGIS GiST index is an R-tree variant.
Hard to shard horizontally because boxes can cross node boundaries.

Polygon queries#

For "is point in polygon?" - bound polygon by an R-tree or cover-set of S2/H3 cells.
For "what polygons contain this point?" - same; cell-coverage filters candidates, exact point-in-polygon test confirms.

Where to start#

Scenario	Pick
New service, global, simple	S2 or H3
Polygon-heavy (geofences, regions)	R-tree + cell pre-filter
String-keyed KV (DynamoDB, Redis)	Geohash
Static dataset, in-memory	Quadtree

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag	Concept	What it is	Page
`HLD`	Sharding	horizontal partitioning across nodes	database-sharding
`HLD`	Geo indexing	Geohash, Quadtree, S2, H3, R-tree	geo-indexing

Quick reference#

Cell levels you'll actually use#

Provider	Level	Edge length
S2	12	~1.3 km
S2	16	~155 m
H3	8	~460 m edge
H3	10	~65 m edge
Geohash	6 chars	~1.2 km
Geohash	8 chars	~38 m

Choosing a level#

Pick a level whose cell edge ≈ your typical query radius.
For variable radius, store the centroid at the finest level and aggregate up at query time.

Sharding by cell#

Use the higher-order bits of the cell id as the shard key.
This co-locates a neighbourhood on one shard → range scans + writes are local.
Beware hot cells (Times Square, Tokyo Station). Add a sub-shard by user-id or time bucket.

Polygon containment math#

Ray casting (count edge crossings) - O(N) per polygon.
Winding number - same.
For high QPS, pre-tessellate complex polygons into convex pieces.

Production tips#

Pre-compute cell coverings for static polygons (country borders, delivery zones).
Re-index when the dataset density changes radically.
Cache the "nearby" results for popular query points (city centers).

Refs#

Google S2 docs (s2geometry.io).
Uber H3 docs + paper.
PostGIS book (Regina Obe).
Geohash.org (the original Niemeyer 2008 invention).

FAQ#

What is a geo index?#

A geo index is a data structure that maps points or shapes to discrete cells or tiles so proximity and bounding-box queries skip most of the dataset.

Geohash vs S2 vs H3, which should I pick?#

Geohash is simple and string-friendly. S2 uses square cells on a sphere with good locality. H3 uses hexagons, which give uniform neighbour distance for routing.

Why are hexagonal H3 cells useful?#

Every hexagon has six equidistant neighbours, so radius queries and movement modeling are smoother than the eight uneven neighbours that square cells produce.

How do you handle hot cells like Times Square?#

Split hot cells into finer cells, shard by composite key of cell plus business id, and add a second-level cache for the densest tiles to absorb spikes.

How do you do find-within-radius queries?#

Cover the radius with a small set of cells, fetch the candidates from each cell, and post-filter by exact haversine distance to drop false positives.

Consistent Hashing: geo-indexed data is distributed across nodes using hashing strategies similar to consistent hashing
Caching Strategies: caching geo-query results at edge locations reduces latency for location-aware applications
Load Balancer: geo-aware load balancing routes users to the nearest region, complementing geo-indexed data