Interview patterns · Design 13

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.

AdvancedInterview priority: High30 min
On this page
  1. The problem: "restaurants within 2 km" over 50 million places
  2. Signals that you are facing it
  3. The idea: divide the map into cells with names
  4. The toolbox
  5. Worked example: static places versus moving drivers
  6. When not to use it
  7. Which case studies use it
  8. In the interview
  9. Quiz

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.

LengthCell size (at the equator)Typical use
439 km × 19.5 kmRegion
54.9 km × 4.9 kmTown or district
61.2 km × 0.61 kmNeighbourhood
7153 m × 153 mStreet

(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

OptionGood atWeak atUse when
GeohashWorks on any sorted key-value store; simpleEdge cases; fixed cell size; distortion near polesYou need prefix search in a store with no geo support
QuadtreeAdapts to densityIn-memory; costly for moving objectsStatic places served from memory
S2Precise coverings as 64-bit ID rangesMore complex libraryLarge-scale indexing and sharding by cell range
H3Uniform neighbours; analytics, surge pricingNot exactly hierarchicalMatching and supply/demand grids
PostGIS / ElasticsearchFull geo queries, polygons, filtersOne cluster's capacityMost 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 district column (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

In the interview

Your turn: "friends nearby"

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.

Your turn: spot the bug

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.
Proximity search on one page
  • 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.
Check what stuck

1. A table has separate B-tree indexes on latitude and longitude. Why is a bounding-box query over 50 million rows slow?

2. A radius search returns places from the user's own geohash cell only, and misses a café 50 m away. Why?

3. A ride-hailing app has 2 million active drivers sending positions every 5 seconds. Which design fits best?

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?

5. Searches are sharded by city. During a festival, one city's shard is overloaded while others are idle. What helps most?

6. A nearby-places index covers 80 million places at about 40 bytes per entry. Roughly how large is it?

Score 60% or more and the lesson is marked complete.

Passing the quiz also marks it complete. Progress is saved in this browser only.