Geospatial Indexing: Geohash vs S2 vs QuadTree

Geohash for Tracking
Geohash converts lat/lon to string prefix. Compute geohash_6 for each position. Store entity ID in a set keyed by geohash. Moving from cell A to cell B: remove from set A, add to set B. Two set operations per cell change.
Query nearby: compute center geohash and 8 neighbors. Union all entity IDs from those 9 sets. Post-filter by actual distance. Simple implementation using standard data structures. Works well for moderate scale.
S2 Cells for Global Scale
S2 provides equal-area cells globally using Hilbert curve on cube projection. Cell IDs are 64-bit integers. Range queries on cell IDs are efficient. Better locality than geohash: nearby points more consistently have nearby cell IDs.
S2 covering algorithm computes minimal set of cells covering a region. For radius query, get covering cells, query each. Fewer cells than geohash neighbor expansion for irregular shapes. More complex implementation but better geometric properties.
In-Memory Grid
For highest performance, use in-memory grid with entities stored directly. Divide world into fixed-size cells. Each cell is a list of entity IDs. Cell lookup is O(1) array access. No string operations, no set membership checks.
Trade-off is memory usage and cell size flexibility. Grid cell size is fixed at startup. If query radius varies widely, some queries will be inefficient. Best for systems with consistent query radius like ride matching.
✅ Best Practice: For real-time tracking, optimize index update speed over query sophistication. Geohash with Redis sets handles most use cases. S2 adds complexity but better geometry. In-memory grid is fastest but least flexible.

💡 Key Takeaways

✓Geohash: entity in set keyed by cell; cell change is two set operations

✓S2: equal-area cells, Hilbert curve, better locality for global scale

✓In-memory grid: O(1) cell lookup, fastest but fixed cell size

✓Query pattern: get covering cells, union entity IDs, post-filter by distance

✓Choose based on scale, query patterns, and implementation complexity tolerance

📌 Interview Tips

1Describe geohash update: moving from cell dr5 to cell dr6 is SREM dr5 entity, SADD dr6 entity

2For global service, recommend S2: consistent cell sizes at all latitudes

3For single-city ride matching with fixed 5 km radius, recommend in-memory grid for speed

← Back to Real-time Location Tracking Overview