We use analytics cookies.We use cookies to analyze site traffic and improve your experience.
Loading...
6 system design questions lean on this idea. Each walks through the full answer.
System Design Masterclass · Database Types Storage
Free preview: the first 2 parts of this 7-part lesson.
Already bought the course? Sign in to read the whole lesson.
this lesson is part of
System Design Masterclass
Unlock this lesson and the 751 other paid lessons
$25 once, by PayPal
See the System Design courseread the rest of this lesson in
System Design Masterclass
Unlock this lesson and the 751 other paid lessons
$25 once, by PayPal
See the System Design coursein Database Types Storage
This lesson is part of the full System Design Masterclass. Unlock it along with 769 other lessons for a one-time payment.
One-time payment by card or PayPal
Get Lifetime AccessOne-time payment: UPI, card or netbanking
Get Lifetime Access18 Foundation lessons are free, no payment needed. Try them now
It is easy and good
“It is really nice and good Please join the course”
You open Uber Eats. The app shows you restaurants near your location, sorted by distance. Behind the scenes, the backend runs something like: "find all restaurants within a 2 km radius of latitude 40.7128, longitude -74.0060."
If the database has 500,000 restaurants, a naive approach calculates the distance from your location to every single restaurant using the Haversine formula. 500,000 floating-point calculations. At scale, with millions of concurrent users making this query, that's not sustainable.
Geospatial indexes solve this by organizing location data into spatial data structures that prune the search space. Instead of checking every restaurant, the index narrows down to a few thousand candidates in the right geographic area, then calculates exact distances only for those.
Google Maps, Uber, DoorDash, Airbnb, every location-aware application relies on geospatial indexing. PostGIS (the PostgreSQL extension), MongoDB, Elasticsearch, and all support it. The specific data structures vary, but the principle is the same: partition space so you can skip irrelevant regions.
R-trees organize spatial data by grouping nearby objects into bounding rectangles, then grouping those rectangles into larger rectangles, recursively, like a tree.
Imagine a map of New York. An R-tree might group all restaurants in Manhattan into one bounding box, all in Brooklyn into another, all in Queens into another. Within Manhattan, restaurants in Midtown are grouped together, Downtown together, and so on.
Querying: "Find restaurants within 2 km of me." The engine checks which bounding boxes overlap with your 2 km circle. It skips entire boroughs that don't overlap. For boxes that do overlap, it recurses into smaller boxes, pruning at each level. Only the leaf-level restaurants within intersecting boxes get the exact distance calculation.
PostGIS uses GiST (Generalized Search Tree) indexes, which are R-trees internally. This is the most mature and powerful option for complex spatial queries (polygons, intersections, containment).
Geohashes encode a latitude/longitude pair as a string of characters. The more characters, the more precise the location:
"dr5r" → roughly New York City area (~20km precision)
"dr5ru" → Manhattan (~5km)
"dr5ru6" → Midtown (~1km)
"dr5ru6x" → a few blocks (~150m)
The key insight: locations that share a longer geohash prefix are closer together. This turns a 2D spatial problem into a 1D string prefix problem, and string prefix matching is something databases already do well with B-trees.
Querying: "Find restaurants near me." Compute your geohash at the desired precision, then search for all restaurants whose geohash starts with the same prefix. A B-tree index on the geohash column handles this efficiently.
Trade-off: Geohashes have edge effects. Two restaurants on opposite sides of a geohash boundary might be very close to each other but have completely different prefixes. The solution: also search neighboring geohash cells (there are at most 8 neighbors). This eliminates false negatives but adds complexity.