Architectural Breakdown & AnalysisFAANG Aligned
Searching for nearby restaurants or drivers using standard 2D SQL WHERE lat BETWEEN x AND y queries causes full table scans at scale.
1. Geohash Indexing
- Converts 2D latitude and longitude coordinates into a 1D string hash (e.g.,
9q9hv). - Characters share common prefixes for geographically close locations. Shorter prefixes denote larger bounding boxes.
2. Google S2 Geometry
- Maps Earth onto a 3D cube decomposed into hierarchical cells (Level 0 to 30).
- Provides uniform cell area shapes without Geohash edge-boundary anomalies.
3. QuadTree Spatial Index
In-memory tree where every parent node splits into 4 sub-quadrants when node item counts exceed threshold capacity.
NOTE — Database Support
Leverage PostGIS (PostgreSQL) or Redis Geospatial Commands (GEOADD, GEORADIUS) for built-in spatial indexing.
Key Architectural Comparison
| Geospatial Index | Structure | Query Complexity | Best Used For |
|---|---|---|---|
| Geohash (Base-32) | 1D string prefix grid. | Fast B-Tree range query. | Point searches with rectangular bounding boxes. |
| Google S2 Geometry | 64-bit integer Hilbert curve. | $O(\log N)$ integer comparisons. | Global spatial indexing without polar distortion (Uber). |
| QuadTree | 2D recursive tree. | Fast spatial quadrant pruning. | In-memory spatial index with varying density (Yelp). |