Design Geo Proximity Search

Design Geo Proximity Search

Step 1 of 11

places50 M

Fifty million places, and a position is two numbers — which no single sorted index can order by.

The Idea

Return the twenty nearest places to a point, from fifty million of them. A position is two numbers, and no single sorted index can order by both at once.

Real-World Example

Postcodes. Shared leading characters put neighbours next to each other in a list, which is what lets a clerk open one drawer instead of reading every address in the country.

The Tradeoff

A geohash makes proximity a prefix match on a plain index, and inherits the grid's lie: two points either side of a cell edge can share a much shorter prefix, or none at all, so the surrounding cells are read too. A quadtree follows density instead, shallow in empty regions and deep downtown, and costs a live tree to maintain rather than a string.

Your turn

Put the steps in the right order.

1. 1Read the candidate places in that cell and its eight neighbours↑↓
2. 2Encode each place's position as a geohash string and index it↑↓
3. 3Sort the candidates by true distance and cut to twenty↑↓
4. 4Encode the search point and trim the prefix to the radius asked for↑↓

Check order

Mini quiz

1 / 3

A geohash turns proximity into a prefix match, which matters because:

• APrefixes compress well
• BLatitude becomes optional
• CAn ordinary sorted index can then answer the query
• DIt removes the need to read neighbours