Proximity Search

Geospatial proximity search answers two classic system design questions: "Which restaurants are within a 3 km radius of my current location?" (Yelp, Google Maps) and "Which 10 available drivers are closest to this passenger?" (Uber, Lyft).

Querying coordinates with standard relational indexes is inefficient because physical geographic space is two-dimensional, whereas standard database indexes order data along a single dimension. Spatial indexing patterns map 2D spherical coordinates into 1D linear strings or integers, enabling sub-millisecond range and bounding-box lookups across millions of locations.

Why standard B-Trees fail on 2D coordinates

A naive approach stores places in a relational table with separate latitude and longitude columns:

1 SELECT id, name FROM places 
2 WHERE latitude BETWEEN 37.70 AND 37.80 
3   AND longitude BETWEEN -122.50 AND -122.40;

A standard composite B-Tree index on (latitude, longitude) sorts primarily by latitude. The database uses the index to filter the narrow latitude slice, but within that slice, it must perform an exhaustive scan across all longitude values. As table sizes grow to millions of points, 2D range scans degrade into high-latency disk reads.

Geohash: Interleaving latitude and longitude

A Geohash converts a (latitude, longitude) coordinate pair into a short alphanumeric string (Base32) by recursively dividing the world into halves and interleaving their binary bits:

Because of bit interleaving, points that share a long Geohash prefix are physically close to each other on Earth:

1 9q8yy (precision 5, ~4.9 km x 4.9 km cell)
2 9q8yyk (precision 6, ~1.2 km x 0.6 km cell)
3 9q8yyk8 (precision 7, ~150 m x 150 m cell)

To find all restaurants near a user, compute the user's 6-character Geohash cell and query standard database indexes using prefix matching:

1 SELECT * FROM places WHERE geohash LIKE '9q8yyk%';

Quadtrees: Adaptive spatial partitioning

While Geohash creates fixed grid boundaries, real-world populations are unevenly distributed: downtown Manhattan contains millions of venues, while rural farmland contains very few.

A Quadtree is an in-memory 2D tree where every internal node splits into exactly four children (North-West, North-East, South-West, South-East):

Quadtrees require keeping the tree structure in memory, making them ideal for read-heavy venue searches with periodic batch re-indexing.

Hexagonal global grids: Uber H3 and Google S2

Modern mobility platforms have largely transitioned from square Geohashes to hierarchical hexagonal discrete global grids like Uber H3:

Handling fast-moving objects: Ride-hailing architectures

In ride-hailing (Uber, Lyft), thousands of drivers transmit GPS pings every 3 to 5 seconds. This creates a massive write-heavy workload that would destroy a disk-based relational database.

Production architectures separate static locations from dynamic locations:

Numbers to quote

Where it bites

• Polar and 180th meridian edge anomalies: Coordinate calculations near the international date line (-180 / +180 degrees longitude) wrap around, creating mathematical discontinuities in naive bounding box formulas.
• Altitude blindness: 2D coordinate projections ignore altitude. A driver on a highway overpass and a passenger on the street directly below share the exact same 2D coordinates but cannot reach each other.
• In-memory quadtree rebalancing: If mobile drivers move into a concentrated event venue (like a football stadium exiting), an in-memory quadtree undergoes continuous node splitting and rebalancing, causing latency spikes. Use fixed-resolution H3 or Redis GEO instead of mutable quadtrees for moving entities.