Geo-spatial and Location Services: Geohash, Quadtree, S2/H3
Index latitude/longitude data so that a query like 'which drivers/restaurants are within 2 km of me' runs in milliseconds.
56.1 Why is it used?
- Uber/Ola/Rapido need the nearest driver, and Swiggy/Zomato need nearby restaurants and delivery partners. All of these are 'nearby search'.
- A normal index (B-tree) sorts lat and lng separately, so a 2D 'inside a circle' query is slow and ends up close to a full scan.
- Lakhs of drivers send their location every 4-5 seconds. Writes and reads at this speed need a special geo index.
- Surge pricing, delivery zones, ETA and geo-fencing (delivery only within 5 km of the store) all run on area/cell based calculations.
- Splitting the map into cells/grids makes data sharding and analytics (which area has more demand) easy.
56.2 How it works
- 1.Driver app sends location -> geo index update (Redis GEOADD)
- 2.Rider makes a request -> radius search (GEOSEARCH)
- 3.Sort by distance / ETA
- 4.The best driver is matched
Live locations stay in Redis, so the radius search runs in milliseconds
- Geohash: repeatedly splits the world into 32 parts and turns lat/lng into a string (like 'tdr1y'). A common prefix = nearby places.
- Geohash precision: 5 characters = 4.9 km x 4.9 km cell, 6 characters = 1.2 km x 0.6 km, 7 characters = 153 m.
- Edge problem: two nearby points can fall in different cells, so you search your own cell + the 8 neighbour cells.
- Quadtree: keep splitting the map into 4 parts until a box has no more than N points. Small boxes in a crowded city, big boxes in villages.
- Google S2: projects the Earth onto a cube and builds 64-bit cell IDs using a Hilbert curve. Good for area coverage and polygon queries.
- Uber H3: divides the Earth into hexagons (resolution 0-15). All 6 neighbours of a hexagon are at the same distance, so it is best for surge/demand analysis.
- R-tree / GiST index: a DB like PostGIS builds a tree of bounding boxes. Polygon, line and distance queries become fast.
- Flow: driver location -> geo index update (Redis GEOADD) -> rider request -> radius search (GEOSEARCH) -> sort by distance/ETA -> match.
- Extra: the old GEORADIUS command has been deprecated since Redis 6.2. Use GEOSEARCH instead.
56.3 Tools you can use
| Tool | Type | How it is used |
|---|---|---|
| Redis GEO | In-memory geo index | GEOADD drivers 77.59 12.97 d42; GEOSEARCH drivers FROMLONLAT ... BYRADIUS 2 km ASC. Internally it is geohash + a sorted set. |
| PostGIS (PostgreSQL) | Spatial database extension | A geography column + GiST index; ST_DWithin and ST_Contains handle radius and polygon (delivery zone) queries. |
| Elasticsearch / OpenSearch geo | Search engine | geo_point/geo_shape fields; a geo_distance query + text filter, like 'pizza within 3 km, rating > 4'. |
| Uber H3 | Open-source hex grid library | latLngToCell(lat, lng, 9) gives a hexagon ID; gridDisk finds the surrounding hexagons so you can count demand/supply. |
| Google S2 Geometry | Open-source cell library | Cover a region with S2 cells and run range queries on the cell IDs. Used in Google Maps and MongoDB 2dsphere. |
| MongoDB 2dsphere | Document DB geo index | $near and $geoWithin queries on GeoJSON points/polygons. |
| AWS Location Service / Google Maps Platform | Managed maps APIs | Geocoding, routing, ETA and geofencing APIs. You do not have to maintain map data yourself. |
56.4 Comparison: Redis GEO vs PostGIS vs Elasticsearch geo vs H3
| Point | Redis GEO | PostGIS | Elasticsearch geo | Uber H3 |
|---|---|---|---|---|
| What it is | In-memory geo sorted set | Full spatial SQL database | Search engine with geo fields | A library: hexagon cell IDs, not a DB |
| Speed | Sub-millisecond, fastest | Milliseconds, depends on the index | Milliseconds, scales out | ID calculation takes microseconds |
| Frequent updates (location every 4 sec) | Excellent | Okay, needs tuning for heavy writes | Weak, near real-time because of the refresh interval | Just calculate the new cell ID |
| Query types | Radius/box, nearest | Radius, polygon, intersection, routing (pgRouting) | Distance + full-text + filters | Neighbours, rings, aggregation by cell |
| Durability | RAM based, persistence optional | Strong, ACID | Durable, replicas | Depends on wherever you store the data |
| Complexity | Very simple | Needs SQL + GIS knowledge | Cluster has to be managed | The concept has to be understood |
| Best for | Live driver/rider locations | Delivery zones, maps data, GIS analytics | Nearby restaurant/hotel search with text | Surge pricing, demand heatmaps |
56.5 When to choose which
- Redis GEO: live moving objects (drivers, delivery boys) whose location changes every few seconds.
- PostGIS: you need polygons, delivery zones, permanent geo data and complex spatial SQL.
- Elasticsearch: you need 'nearby + text search + filters + ranking' in a single query (Zomato search).
- H3/S2: area-wise aggregation, surge pricing, sharding by cell. Combine it with a DB.
- Real systems use a mix: Redis live tracking + PostGIS zones + Elasticsearch search + H3 analytics.
56.6 Real-world example
Scenario: finding the nearest delivery partner or driver in Swiggy/Uber.
- Every driver's app sends lat/lng every 4 seconds. The location service updates Redis with GEOADD.
- Redis is sharded city-wise (bengaluru:drivers, delhi:drivers) so that no single key gets too big.
- The user places an order/ride request: GEOSEARCH returns the top 20 drivers within a 2 km radius in ASC order.
- If too few are found, the radius is widened 2 -> 4 -> 6 km (expanding search).
- After the straight-line distance, a routing service computes the actual road ETA and the best driver is chosen.
- Uber open-sourced H3: the city is split into hexagons and the surge multiplier comes from each hexagon's demand vs supply.
- The delivery zone check happens in PostGIS with ST_Contains(zone_polygon, user_point): is the address serviceable or not.
56.7 Interview tips
- Putting a normal B-tree index on lat/lng and running 'WHERE lat BETWEEN ... AND lng BETWEEN ...': slow on big data, and you get a box instead of a circle.
- Searching only your own cell in geohash: drivers near the boundary are missed, so take the 8 neighbours too.
- Writing every location update to a (SQL) DB: the write load is huge. Keep live data in Redis and send history through Kafka -> data lake.
- Interview tip: explain the geohash vs quadtree vs H3 trade-off, and do the maths for the location update rate in 'Design Uber / Yelp nearby' (for example 1 lakh drivers / 4 sec = 25,000 writes/sec).