System Design Cases
Geospatial Indexing: Geohash, Quadtree, H3
Spatial partitioning patterns: geohash (string prefix), quadtree (recursive subdivision), H3 (Uber hexagonal grid). Use cases: nearby search, ride dispatch, surge pricing, geo-fences.
Geohash, quadtree, and H3
Spatial indexes generate candidates. Exact geometry or geography predicates decide the answer. Treating a cell match as the final radius or polygon result creates boundary errors.
Coordinate contract
GeoJSON uses WGS 84 longitude, latitude coordinates in decimal degrees. Distance APIs must say whether inputs are planar geometry units or geography meters and whether they use a sphere or spheroid. Validate axis order, CRS, longitude wrapping, and antimeridian behavior.
Geohash
A geohash prefix identifies a latitude/longitude rectangle. Longer prefixes refine the rectangle, but a nearby point can lie across a cell boundary with no shared long prefix. Radius search therefore covers the center cell plus every neighboring/intersecting cell required by the query, unions candidates, and applies an exact distance test.
Rectangle size and physical area vary with latitude. Select precision from measured density and candidate fanout, not one universal "meters per character" claim.
Quadtree
A quadtree recursively splits a region into four children. Adaptive trees refine dense or geometrically complex regions and stop in sparse regions. Complexity depends on distribution, maximum depth, query shape, and output size. Polygon/radius queries visit every intersecting leaf, then run an exact predicate.
H3
H3 partitions the globe hierarchically, mostly into hexagons, with 12 pentagons and distortion. Cells at one resolution do not have exactly equal area. Parent-child relationships are exact logically, while geometric containment can be approximate.
H3 polygon conversion APIs have documented containment modes. A centroid-contained set is not automatically a conservative polygon cover. Grid traversal must handle pentagon distortion and possible API failure modes.
Exact verification and updates
Use the cell index for candidate generation and a database geography predicate such as ST_DWithin for authoritative distance. Keep versioned memberships for moving objects, atomically publish the new version, and deduplicate candidates before filtering.
Diagram scenarios
The animation covers geohash neighbor expansion, adaptive quadtree traversal, H3 containment/pentagon boundaries, antimeridian handling, and versioned moving-object updates.