Designing Yelp or Nearby Friends

A proximity search is fast because you bucket every place into a spatial cell once, so that answering "what's near me?" reads only the handful of cells the query circle touches instead of scanning all 500 million rows and computing 500 million distances. Every design below is the same single move — shrink the candidate set before you measure distance — done with progressively smarter cells.

What we are building

A read-heavy store of places (restaurants, theaters, shops) that answers: given a point (lat, lng) and a radius, return the nearby places, optionally filtered by category and sorted by distance or rating. Users also add/edit places and leave reviews.

• Functional: add/delete/update a Place; find all places within radius D of a point; add reviews (text, rating, photos).
• Non-functional: real-time search latency; overwhelmingly read-heavy (reads >> writes); places rarely move, so the index can be treated as near-static.

Scale & schema

Assume 500M places and 100K queries/sec, growing ~20%/yr. A Place row is LocationID (8B) + Name (256B) + Lat (8B) + Lng (8B) + Description (512B) + Category (1B) ≈ 793 bytes. Reviews and photos live in separate tables keyed by LocationID. The full row store is large and lives on disk; the interesting problem is the spatial index that turns a location into a short candidate list — that is what we design next.

Step 1 — the SQL range query, and why it stalls

Mechanism: store lat and lng in two columns, put a B-tree index on each, and select the bounding box:

SELECT * FROM Places
WHERE Latitude  BETWEEN X-D AND X+D
  AND Longitude BETWEEN Y-D AND Y+D;

Why it fails at 500M rows. The two indexes are independent. The latitude index returns every place in a thin horizontal band that wraps the whole planet — potentially tens of millions of rows; the longitude index returns a vertical band, equally huge. The engine must then intersect two enormous ID lists to keep only the places in the small box where the bands cross. You have paid to read two planet-spanning strips to answer a question about one neighborhood. There is no single index the box maps onto, so latency scales with the band size, not the answer size.

Why the naive box is also incorrect: a fixed degree delta D is not a fixed distance. One degree of longitude is ~69 miles at the equator but ~49 miles at 45°N and shrinks to 0 at the poles. A square degree box over-selects near the equator and under-selects near the poles, and its corners are farther than its edges. Treat lat/lng as Euclidean only to grab candidates; always apply a real spherical distance (haversine) as the final filter.

Step 2 — static grids, and why uniform cells break

Mechanism: chop the map into fixed cells and stamp each place with the GridID it falls in (indexed). Because cells are a fixed size, computing a point's cell and its 8 neighbors is pure arithmetic — no search. Size the cell to the query radius so a nearby search only ever touches the containing cell plus its 8 neighbors:

SELECT * FROM Places
WHERE GridID IN (g, g1, g2, ..., g8)
  AND Latitude  BETWEEN X-D AND X+D
  AND Longitude BETWEEN Y-D AND Y+D;

Keep the index in RAM as a hash map: GridID → list<LocationID>.

Worked memory (with the arithmetic fixed)

Correction: the commonly-quoted "20 million grids" forgets to square the cell side (it divides by 10 sq mi, not 10×10). A 10-mile cell is 100 sq mi, so it is ~2 million grids. The final ≈4 GB is unchanged because it is dominated by the 8 B × 500M location IDs, not by the tiny grid-key term.

Why uniform cells fail: real places are wildly non-uniform. A 10 mi cell over the Pacific holds a handful of coastal spots; the same-sized cell over downtown San Francisco holds tens of thousands. Every query that lands downtown scans a monster list, so your worst-case latency is set by your densest cell — exactly where traffic is heaviest.

Step 3 — the dynamic quadtree, and why it wins

Mechanism: make the cell size follow the data. Cap a cell at 500 places; when a cell overflows, split it into 4 equal children and redistribute. Dense downtown ends up as a deep pile of tiny cells; the open ocean stays one giant cell. A cell that can no longer split is a leaf and holds the actual place list; internal nodes are just 4 child pointers. That four-way tree is a quadtree, and it guarantees every leaf holds ≤500 places regardless of density — so worst-case scan cost is bounded everywhere.

Worked memory

The tree skeleton (10 MB) is a rounding error next to the 12 GB of location data — and 12 GB fits in RAM on a single modern server. That is the counter-intuitive punchline: the size of a planet-scale spatial index is small. The hard problems are fan-out, rebuild, and skew, not capacity.

The three operations, made concrete

Build. Start with one node covering the whole world; insert every place; whenever a leaf exceeds 500, split it into NW/NE/SW/SE and re-insert. Find the leaf for a point is a top-down walk: at each internal node compare the point to the node's midpoint and step into the one child quadrant that contains it — O(depth), no scanning. Find neighbors is a range query: recurse from the root but prune any child whose bounding box cannot intersect the query circle.

CAPACITY = 500

class Node:
    def __init__(self, bounds):      # bounds = (min_lat, min_lng, max_lat, max_lng)
        self.bounds   = bounds
        self.places   = []           # populated only on leaves
        self.children = None         # 4 Nodes once split; None => leaf

    def is_leaf(self):
        return self.children is None

def child_for(node, lat, lng):       # which quadrant holds the point?
    min_lat, min_lng, max_lat, max_lng = node.bounds
    mid_lat = (min_lat + max_lat) / 2
    mid_lng = (min_lng + max_lng) / 2
    north = lat >= mid_lat
    east  = lng >= mid_lng
    if north and not east: return node.children[0]   # NW
    if north and east:     return node.children[1]   # NE
    if not north and not east: return node.children[2]  # SW
    return node.children[3]                              # SE

def find_leaf(node, lat, lng):       # top-down descent, O(depth)
    while not node.is_leaf():
        node = child_for(node, lat, lng)
    return node

def split(node):
    lo_lat, lo_lng, hi_lat, hi_lng = node.bounds
    mid_lat, mid_lng = (lo_lat + hi_lat) / 2, (lo_lng + hi_lng) / 2
    node.children = [
        Node((mid_lat, lo_lng, hi_lat, mid_lng)),    # NW
        Node((mid_lat, mid_lng, hi_lat, hi_lng)),    # NE
        Node((lo_lat, lo_lng, mid_lat, mid_lng)),    # SW
        Node((lo_lat, mid_lng, mid_lat, hi_lng)),    # SE
    ]
    moving, node.places = node.places, []
    for p in moving:
        insert(node, p)              # push down into the new children

def insert(node, p):                 # p has .lat, .lng
    if node.is_leaf():
        node.places.append(p)
        if len(node.places) > CAPACITY:
            split(node)
    else:
        insert(child_for(node, p.lat, p.lng), p)

def search(node, center, radius, out):   # center = (lat, lng)
    if not circle_intersects_box(center, radius, node.bounds):
        return                        # prune: this whole subtree is too far
    if node.is_leaf():
        for p in node.places:
            if haversine(center, (p.lat, p.lng)) <= radius:
                out.append(p)
    else:
        for c in node.children:
            search(c, center, radius, out)

Why the single-cell shortcut is wrong. A tempting version just calls find_leaf and returns that one cell's places. But a place sitting a few meters across the leaf boundary is inside your radius yet lives in the neighbor leaf — so a single-cell answer silently drops results near every edge. You must visit all leaves the circle overlaps. search() above does this correctly by pruning on box-intersection. When you instead want k-nearest with a growing radius, chain the leaves (see below) and walk outward until you have k or hit the max radius.

Traced example: nearby restaurants in San Francisco

Query point (37.77, −122.42), radius 0.5 mi, category restaurant, want 20 results. The descent compares the point to each node's midpoint and steps into exactly one child (all midpoints below are the true arithmetic centers of each cell):

Now the range phase, walking outward via the sibling chain until we hit 20. One mechanism note: a plain doubly-linked leaf chain orders leaves by list position, not compass direction — so "north" and "east" neighbors are located either by re-descending from the shared parent with a point nudged just across the boundary, or by chaining leaves in Z-order/Hilbert order so spatial neighbors are usually (not always) chain-adjacent:

Total places actually distance-checked: 486 + 301 + 228 ≈ 1,015 — versus 500,000,000 for a full scan. The haversine step in row 1 is what corrects the earlier lat/lng-box distortion: the cells give candidates, real spherical distance gives the answer.

Scaling out: partitioning, rebuild, and serving

12 GB fits one box today, but 20%/yr growth and 100K QPS force partitioning across many quadtree servers. Two schemes:

• Shard by region (e.g. ZIP): all places in a region live on one server; a query goes straight to the server owning the user's region. Gain: a query touches one server — no fan-out. Cost: load mirrors geography, so a popular region (downtown, a festival) creates a hot shard, and regions grow unevenly, so balance drifts and you must repartition. Good when traffic is geographically even and you value locality.
• Shard by hash(LocationID): each place is hashed to a server, spreading dense areas evenly. Gain: uniform load, no hotspots. Cost: a place's neighbors are now scattered across all servers, so every nearby-search is a scatter-gather — fan out to all shards, each returns its local matches, an aggregator merges and sorts. You trade a hot-shard risk for fan-out latency on every query. This is the usual choice at this scale.

Rebuild after failure. A quadtree server is a rebuildable cache, not the source of truth — the row store is. If both a primary and its replica die, brute-force rebuild means scanning the entire places table and re-hashing every LocationID: slow, and the shard serves nothing meanwhile. Fix with a QuadTree Index server — a reverse map server# → HashSet<place (LocationID, lat, lng)> — so a fresh server asks for exactly its places and rebuilds in seconds. Replicate that index too. Reads scale via primary/secondary replicas (secondaries lag a few ms — fine for near-static places). Hot places sit behind an LRU cache (Memcached). Ranking by popularity is precomputed and refreshed once or twice daily off-peak — updating the tree on every review would thrash search throughput for a signal that need not be real-time.

Pitfalls

• Euclidean lat/lng. A degree of longitude shrinks toward the poles; a square-degree box is not a circle and is wrong far from the equator. Use lat/lng only to gather candidates, then filter with haversine.
• Boundary misses. The nearest restaurant may be a few meters into the next cell. Answering from a single leaf drops edge results — always scan every cell the query circle overlaps.
• Degenerate splits (infinite subdivision). A mall food court where 800 venues share one geocoded point can never split below the 500 cap — the cell keeps trying to split into children that all inherit the same point. Guard with a max depth (or an overflow list on the leaf) so identical coordinates don't loop forever.
• Rebuild storm. Without the reverse index, a dead shard rebuilds by scanning 500M rows while serving nothing — a small failure becomes a coverage gap. The QuadTree Index server is what makes recovery fast.
• Hot shard vs fan-out. Region sharding invites hot shards; hash sharding cures that but makes every read a scatter-gather. There is no free lunch — pick the failure you can tolerate.
• Assuming places never move. This whole design leans on a near-static tree. The moment objects move continuously (drivers, friends), per-move re-insertion thrashes the tree — that is a different design (see Uber).

When to reach for a quadtree — and when not

Reach for it when your data is point-like, highly non-uniform in density (real geography always is), mostly static, small enough to hold in RAM, and you control the code and want cell resolution to adapt automatically to density. That is exactly Yelp.

Decision signals vs named alternatives

Choose the quadtree when data is skewed, static, point-based, and RAM-resident and you want adaptive resolution. Prefer geohash/Redis when you'd rather lean on an existing store and can accept fixed precision and simpler ops. Prefer S2/H3 when objects move on a globe and clean neighbor math matters — which is why ride-sharing (Uber) uses them. Prefer PostGIS when the dataset fits one database and you need rich geometry and transactional correctness more than raw QPS.

Takeaways

• Every step is one idea: shrink the candidate set before measuring distance. SQL boxes shrink it a little; grids shrink it to a cell; the quadtree makes the cell adapt to density so worst-case scan cost is bounded everywhere.
• Adaptive resolution beats fixed cells precisely because real geography is skewed — the quadtree spends nodes where places are dense and leaves the ocean as one big cell.
• The index is tiny (~12 GB) and fits one server; the real engineering is fan-out (hash sharding), fast rebuild (reverse index), and taming skew — not storage size.
• Get the arithmetic right: a 10-mile cell is 100 sq mi → ~2M grids, not 20M. And always finish with true spherical distance — lat/lng boxes only nominate candidates.

Re-authored and deepened for this guide. Sources: Grokking the System Design Interview (Designing Yelp / Nearby Friends — Proximity Server); the QuadTree data structure (Finkel & Bentley, 1974); Google S2 Geometry and Uber H3 hierarchical spatial indexing; Redis GEOADD/GEOSEARCH geohash commands; and PostGIS ST_DWithin / GiST R-tree indexing. Memory figures and the San Francisco descent trace were recomputed and verified; the widely-copied "20 million grids" figure is corrected to ~2 million (a 10-mile cell is 100 sq mi, and the ≈4 GB index is unchanged because it is dominated by the 8 B × 500M location IDs).

Observability: the three signals that tell you the index is misbehaving

Three metrics catch the failure modes above before users feel them. Leaf-size p99: a leaf stuck at the 500 cap that will not split is a degenerate-coordinate hotspot (the food-court-single-point case) — page on it. Rebuild time per shard: if it climbs, the QuadTree Index reverse map is stale or missing and a crash will become a coverage gap. Haversine drop rate: the fraction of gathered candidates the final spherical-distance filter rejects — a high drop rate means the cells are too coarse (you are scanning far more places than you return), so tighten the leaf cap or cell resolution. These are the observable versions of the pitfalls: dense-leaf skew, slow rebuild, and over-coarse candidate gathering.

Drill ladder

1. L1: Why Euclidean lat/lng distance is wrong.
2. L2: Boundary miss — query circle overlaps N cells.
3. L3: Size 500M places × 8 B id ≈ 4 GB ids — total index ~12 GB claim defend.
4. L4: Region vs hash sharding trade-off for Super Bowl weekend hotspot.
5. L5: Defend S2/H3 over quadtree for drivers.