"Geohash vs quadtree vs S2 vs H3"
Comparing spatial indexes for proximity search: geohashes, quadtrees, Google S2 and Uber H3, plus R-trees in databases. How each divides the map, handles neighbours and density, fits in a key-value store, and which to pick for nearby search, ride matching and heat maps.
Reading is half of it. See this used in a real interview: walk through Design Yelp →
"Find restaurants within 2 km" and "find the nearest available drivers" need a spatial index: a way to turn two-dimensional locations into something a database can search quickly. Interviewers often ask which you would use and why. The main candidates divide the world into cells in different ways, and each has strengths. This guide compares them so you can choose with a reason.
Geohash
Encodes latitude and longitude into a string by repeatedly halving the world, interleaving longitude and latitude bits, and writing them in base32. Each extra character makes the cell smaller (about 5 km at 5 characters, about 150 m at 7).
- Prefix property: nearby points usually share a prefix, so a string index or key-value range scan finds points in a cell.
- Easy to store in any database as a string column or key prefix.
- Edge problems: two points across a cell boundary can have very different hashes, so you must also search the eight neighbouring cells.
- Uneven cell shape and size by latitude; rectangles get narrow near the poles.
Quadtree
A tree where each node covers a square region and splits into four children when it holds too many points.
- Adapts to density: dense cities get small cells, empty areas stay large. A query reads a similar number of points anywhere.
- Usually kept in memory and rebuilt or updated as points move; less natural to store in a plain database.
- Great for static or slowly changing data (businesses); frequent updates (moving drivers) require locking or rebuilding strategies.
Google S2
Projects the sphere onto the six faces of a cube and divides each face with a Hilbert curve into a hierarchy of cells, each identified by a 64-bit integer.
- Good locality: the Hilbert curve keeps nearby cells close in id order, so range scans on cell ids work well.
- Region coverings: any shape (circle, polygon) can be approximated by a small set of cells at mixed levels, which turns "points within this area" into a few range queries.
- Cells are roughly equal in area across the globe.
- Used by Google Maps, many databases and geofencing systems.
Uber H3
Divides the world into hexagons at 16 resolutions, each cell with a 64-bit id.
- Uniform neighbours: every hexagon has six neighbours at the same distance, which makes "rings" around a point, smoothing and movement modelling clean.
- Ideal for aggregation and analytics: supply and demand per cell, surge pricing, heat maps. See surge and dynamic pricing.
- Hexagons do not nest perfectly (a parent only approximately contains its children), which matters less for analytics than for exact containment.
R-trees and database support
Spatial databases (PostGIS, MySQL spatial, Elasticsearch geo fields) use R-trees or BKD trees: hierarchical bounding boxes that index points and shapes. For moderate scale, ST_DWithin with a spatial index on PostGIS is often enough, and avoids building your own index. Redis GEOSEARCH uses geohash-encoded sorted sets. See Redis data structures.
Comparison
| Geohash | Quadtree | S2 | H3 | |
|---|---|---|---|---|
| Cell shape | rectangles | squares (adaptive) | quadrilaterals on a cube | hexagons |
| Storage | strings, any database | in-memory tree | 64-bit integers | 64-bit integers |
| Adapts to density | no (choose a precision) | yes | via mixed-level coverings | no (choose a resolution) |
| Neighbour search | 8 neighbours, edge cases | tree traversal | library support | uniform rings |
| Best for | simple proximity in a key-value store | in-memory nearby search on static points | precise region queries, geofencing | aggregation, pricing, heat maps, movement |
Choosing for common questions
- Nearby businesses (Design Yelp): data changes slowly and reads dominate. Geohash or S2 cell ids in the database with neighbour cells, or an in-memory quadtree replicated per region; PostGIS is fine at moderate scale.
- Nearest drivers (Design Uber): locations change every few seconds. Keep an in-memory map from cell id (geohash, S2 or H3) to the set of drivers, update cell membership as drivers move, and search the rider's cell plus rings of neighbours.
- Surge pricing and demand forecasting: H3 hexagons for clean aggregation.
- Maps and geofences (Design Google Maps): S2 coverings for regions and tiles.
- Dating apps (Design Tinder): coarse cells to find candidates, then exact distance filtering.
Practical tips
- Always do a final exact distance check on candidates from the cells; cells are an approximation.
- Choose cell size so a typical query touches a handful of cells with a manageable number of points; expand the search radius if results are too few.
- Shard by region or by cell id prefix, watching for dense hot cells (city centres, airports). See hot keys and skew.
Checklist
- Geohash for simple string-indexed proximity, with neighbour cells.
- Quadtree for density-adaptive, in-memory search over mostly static points.
- S2 for precise region coverings and range scans on integer ids.
- H3 for uniform neighbours and aggregation.
- PostGIS or engine-native geo indexes when scale allows.
- Exact distance filtering and density-aware sharding.