Location and proximity search
How to find what is near a point quickly: geohash, quadtrees, S2 and H3 cells, radius queries, static places versus moving drivers, and how to shard geographic data.
On this page
The problem: "restaurants within 2 km" over 50 million places
A maps app stores 50 million places with a latitude and longitude. A user asks for restaurants within 2 km. The first version runs:
SELECT * FROM places
WHERE lat BETWEEN 37.756 AND 37.792
AND lng BETWEEN -122.442 AND -122.397;
With an index on lat and another on lng, the database can use only one of them well. The lat index narrows the search to a horizontal stripe around the whole planet, every place at that latitude from San Francisco to Seoul, and then checks each one's longitude. At 20,000 searches a second, that is far too much work per query.
The difficulty is that ordinary indexes sort along one dimension, while "near" is a two-dimensional idea. Every technique in this lesson turns 2D nearness into something a 1D index or an in-memory tree can answer.
Signals that you are facing it
- "Find nearby drivers / restaurants / friends / hotels."
- "Within X km", "the closest N", "in this map view".
- Moving objects: drivers, couriers, delivery robots, shared bikes.
- Matching a request with a supply that has a location: ride hailing, food delivery, dating.
- Uneven density: thousands of places in one city block, none for 50 km in the countryside.
The idea: divide the map into cells with names
Divide the world into a grid of cells, give each cell an ID, and store each object under its cell ID. A proximity search becomes: which cells overlap my search circle? (a few lookups by ID), followed by which objects in those cells are really within range? (an exact distance check on a small set of candidates).
The schemes differ in cell shape, how cells are numbered, and whether cell size adapts to density.
The toolbox
Geohash
A geohash encodes a point as a short string. It splits the world in half by longitude (one bit), then by latitude (one bit), alternating, and writes every 5 bits as one base32 character. Each extra character makes the cell 32 times smaller, and points that share a prefix lie in the same cell.
| Length | Cell size (at the equator) | Typical use |
|---|---|---|
| 4 | 39 km × 19.5 km | Region |
| 5 | 4.9 km × 4.9 km | Town or district |
| 6 | 1.2 km × 0.61 km | Neighbourhood |
| 7 | 153 m × 153 m | Street |
(Cells shrink east to west away from the equator: at San Francisco a 5-character cell is about 4.9 km × 3.9 km.)
Because a geohash is a string, any sorted index can search it: a B-tree WHERE geohash LIKE '9q8yy%', a DynamoDB sort key, or a Redis sorted set. Redis's GEOADD and GEOSEARCH commands store a 52-bit geohash as the score in a sorted set.
The edge problem, and searching the cell plus its eight neighbours
Catch: two points 80 m apart can sit in cells with different prefixes, so you must always search the neighbours too. Near the poles and the 180° meridian, cells get thin or wrap around. And a fixed cell size fits dense cities and empty deserts equally badly.
Quadtree
A quadtree starts with one square covering the map and splits any square holding more than a threshold (say 100 places) into four quarters, recursively. Dense downtown areas end up with tiny cells; oceans stay as one big cell. A search walks down the tree to the leaf containing the point, then checks neighbouring leaves until it has enough results.
Catch: it is usually an in-memory structure built per server. Fine for static places (rebuild nightly, a few GB for tens of millions of points), awkward for objects that move every few seconds because each move can split or merge nodes.
S2 and H3
S2 (from Google) projects the Earth onto the six faces of a cube, divides each face into a hierarchy of square-ish cells (levels 0–30; level 30 cells are about 1 cm²), and numbers them along a Hilbert curve, a space-filling path that keeps nearby cells close in number. Each cell ID is a 64-bit integer, so a search circle becomes a handful of ID ranges to scan, with less distortion than geohash.
H3 (from Uber) tiles the Earth with hexagons at 16 resolutions (0–15); a resolution 9 hexagon covers roughly 0.1 km². In a hexagon grid every neighbour's centre is the same distance away, which makes "the ring of cells around me", movement between cells and heat maps of supply and demand simple. Each resolution has 12 pentagons, and a hexagon is not exactly made of seven smaller ones, so H3 is weaker for exact containment.
Spatial indexes in the database
Postgres with PostGIS stores geometries and builds a GiST index (an R-tree: a tree of nested bounding boxes). It answers radius queries directly:
CREATE INDEX places_geog_idx ON places USING GIST (geog);
SELECT id, name, ST_Distance(geog, ST_MakePoint(-122.4194, 37.7749)::geography) AS metres
FROM places
WHERE ST_DWithin(geog, ST_MakePoint(-122.4194, 37.7749)::geography, 2000)
ORDER BY metres
LIMIT 20;
Note the order: ST_MakePoint(longitude, latitude). Swapping them is the most common geo bug. Elasticsearch and MongoDB offer similar geo_distance and $near queries.
Comparing the options
| Option | Good at | Weak at | Use when |
|---|---|---|---|
| Geohash | Works on any sorted key-value store; simple | Edge cases; fixed cell size; distortion near poles | You need prefix search in a store with no geo support |
| Quadtree | Adapts to density | In-memory; costly for moving objects | Static places served from memory |
| S2 | Precise coverings as 64-bit ID ranges | More complex library | Large-scale indexing and sharding by cell range |
| H3 | Uniform neighbours; analytics, surge pricing | Not exactly hierarchical | Matching and supply/demand grids |
| PostGIS / Elasticsearch | Full geo queries, polygons, filters | One cluster's capacity | Most products up to tens of millions of places |
Worked example: static places versus moving drivers
Static places (a "nearby" search). 50 M places, 20,000 searches a second, a few thousand edits a day.
- Index entry: ID + cell + coordinates ≈ 40 bytes, so 50 M × 40 B = 2 GB. The whole index fits in memory on every server.
- Searching 6-character geohash cells (1.2 × 0.6 km) for a 2 km radius means covering a 4 km square with a few dozen cells; a downtown cell can hold thousands of places, so filter by category inside the index.
- This is a read-heavy problem: replicate the index, cache popular queries (by rounded location and category), rebuild nightly plus a stream of edits. See scaling reads.
Moving drivers. 1 M active drivers, each sending a location every 4 s.
Driver pings into an in-memory geo index, and a rider's search
- 1,000,000 ÷ 4 = 250,000 writes a second, each replacing the previous position. Live state: 1 M × ~50 bytes = 50 MB, tiny.
- So the problem is the write rate, not the size. Keep positions in memory (Redis
GEOADD, or a custom service holding an H3-cell-to-drivers map), sharded by city or cell range, and don't write every ping to a durable database. A sampled stream to Kafka keeps trip history. - Positions expire: a driver who loses signal must vanish after ~30 s. Redis sorted-set members have no individual TTL, so keep a "last seen" timestamp and sweep stale entries.
When not to use it
- Few objects. With 5,000 stores, compute the distance to all of them in memory: microseconds, no index.
- Search by region name, not distance. "Restaurants in Camden" is a filter on a
districtcolumn (or a polygon lookup once per place), not a radius search. - You already have PostGIS or Elasticsearch. Don't hand-build geohash tables when the database has a proper spatial index; build your own only for extreme write rates or stores without geo support.
Which case studies use it
- Design nearby places: a read-heavy static index with geohash or quadtree.
- Design Uber and the ride-hailing app: moving drivers in an in-memory cell index, ETA ranking, sharding by region.
- Design food delivery: restaurants near the customer (static) and couriers near the restaurant (moving).
In the interview
A social app shows which of your friends are within 5 km, for 50 M daily users who share location roughly every minute while the app is open. Average user has 300 friends. Design it.
Compare with our answer
- Writes: at peak maybe 10 M users active, one update a minute ≈ 170,000 writes a second, each overwriting the last position in an in-memory store with a TTL of a few minutes.
- The query is different from "everyone nearby": you only care about friends. With 300 friends, the simplest approach is to fetch their 300 last positions by user ID (a multi-get) and compute distances: no geo index needed.
- Alternatively, push: when a user's position changes cell, notify friends subscribed to them (a pub/sub per user), which fits a live map.
- Privacy: opt-in, coarse positions (round to a cell) for display, expiry when sharing stops.
- Shard the position store by user ID, not by location, since lookups are by friend ID.
A strong answer mentions: a write-rate estimate · in-memory positions with expiry · noticing the friend list is small so a geo index is optional · sharding by user ID for this query shape · privacy and coarse location.
A team stores restaurants in DynamoDB with a 5-character geohash as the partition key and runs one query on the user's own geohash cell. Users near the edges of cells complain that a restaurant across the street never appears, and the busiest downtown cell is throttled at lunch. What's wrong, and what would you change?
Compare with our answer
Two separate bugs. Querying only the user's own cell misses everything just across the cell edge. And using the geohash itself as the partition key puts every restaurant in a busy 5 km cell, and every search there, onto one partition.
A strong answer mentions:
- Query the cell and its 8 neighbours (or cover the radius with several cells), then filter by exact distance.
- Choose cell precision from the radius; consider smaller cells in dense areas.
- Spread hot cells: add a finer geohash or a suffix to the partition key, or put the prefix in the sort key under a coarser partition.
- Cache popular searches; downtown lunch queries repeat a lot.
- Consider a store with a native spatial index (PostGIS, Elasticsearch) if write rates are modest.
- Ordinary indexes sort in 1D; "near" is 2D. Cells turn it into lookups by cell ID.
- Radius query: cover the circle with cells (always include neighbours), then exact distance filter, then rank.
- Geohash: base32, 5 bits per char; 5 chars ≈ 4.9 km, 6 ≈ 1.2 × 0.6 km, 7 ≈ 153 m. Works on any sorted store. Redis GEO uses it.
- Quadtree: adapts to density; in memory; great for static places.
- S2: cube + Hilbert curve, 64-bit cell IDs, coverings as ID ranges. H3: hexagons, uniform neighbours.
- PostGIS: GiST index,
ST_DWithin;ST_MakePoint(lng, lat). - Static places: read-heavy, small index in memory, replicate and cache.
- Moving objects: write-heavy (1 M drivers / 4 s = 250 K/s); in memory, overwrite, expire stale positions.
- Shard by cell range, split hot cells, fan out at borders. Rank candidates by ETA, not distance.
1. A table has separate B-tree indexes on latitude and longitude. Why is a bounding-box query over 50 million rows slow?
Each B-tree is sorted along one dimension. Using the latitude index yields every place at that latitude worldwide, which is then filtered by longitude. Cells or spatial indexes solve the 2D problem.
2. A radius search returns places from the user's own geohash cell only, and misses a café 50 m away. Why?
Points that are close can fall on either side of a cell edge and share little or no prefix. Always query the neighbouring cells too, then filter by exact distance.
3. A ride-hailing app has 2 million active drivers sending positions every 5 seconds. Which design fits best?
2 M ÷ 5 = 400,000 writes a second of short-lived data. An in-memory index that overwrites positions handles it; durable per-ping rows or full rebuilds do not.
4. A food app finds the 10 nearest couriers by straight-line distance and assigns the closest. Couriers often arrive late. What is the best fix?
Straight-line distance ignores roads, rivers and one-way streets. The index's job is the shortlist; travel time decides.
5. Searches are sharded by city. During a festival, one city's shard is overloaded while others are idle. What helps most?
Load follows people, so fixed city shards get hot. Splitting by cell range (and replicating hot read ranges) spreads it. Routing to a shard without the data cannot answer the query.
6. A nearby-places index covers 80 million places at about 40 bytes per entry. Roughly how large is it?
80 × 10^6 × 40 bytes = 3.2 × 10^9 bytes ≈ 3.2 GB: small enough to hold in memory on each server and replicate.
Score 60% or more and the lesson is marked complete.