Requirements and Scale
Functional: given a user location (lat/lng) and search radius, return nearby businesses ranked by rating and relevance. Business owners can add, update, and delete their listings. Users add reviews. Non-functional: low latency (< 200ms), highly available.
Scale: 500M places, 100K searches/sec. Places are updated infrequently (few per second). Searches are read-heavy.
Why Not Simple SQL?
Naive approach: SELECT * FROM places WHERE lat BETWEEN (user_lat - r) AND (user_lat + r) AND lng BETWEEN (user_lng - r) AND (user_lng + r). Problems: (1) Two-column index not efficient — database must scan many rows. (2) Doesn't handle circular radius (lat/lng ranges form a rectangle, not a circle). (3) Won't scale to 500M places with 100K QPS. We need a spatial index.
QuadTree Spatial Index
A QuadTree recursively divides a 2D space into four quadrants. Leaf nodes contain a list of places. Internal nodes have no places — they just divide the space. Split a node when it contains more than a threshold number of places (e.g., 500). A leaf node represents a grid cell that is small enough to be useful.
Leaf nodes store: grid_id, top_left_lat/lng, bottom_right_lat/lng, list of {place_id, lat, lng}. For a proximity query at (lat, lng) with radius r: (1) Find the leaf node containing the user's location. (2) Expand to adjacent leaf nodes until we have enough results or cover the radius. Leaf nodes are linked by a doubly linked list for efficient adjacency traversal.
graph TD World["World"] --> NE["NE Quadrant"] World --> NW["NW Quadrant"] World --> SE["SE Quadrant"] World --> SW["SW Quadrant"] SW --> SW_NE["SW-NE: leaf [place1, place2]"] SW --> SW_NW["SW-NW: leaf [place3]"] SW --> SW_SE["SW-SE: leaf [place4, place5, place6]"] SW --> SW_SW["SW-SW: leaf (empty)"]
Distributed QuadTree
The QuadTree for 500M places fits in ~20 GB of RAM — manageable on a single server. But for 100K QPS we need multiple servers. Run 5-10 QuadTree servers with the full tree replicated on each. All servers are read-only replicas; updates go through a primary QuadTree server which propagates to replicas. Load balance reads across all QuadTree servers. Place metadata (name, address, rating, phone, hours) is stored in a SQL DB (MySQL) sharded by place_id; the QuadTree server only stores lat/lng and place_id, then the app fetches details from the SQL DB for the top results.
Search Flow and Ranking
Query flow: (1) User sends lat/lng/radius to search API. (2) App server queries QuadTree server → gets list of place_ids within radius. (3) Filter place_ids by category (restaurants, gas stations). (4) Fetch metadata for top-N from Place DB. (5) Rank by composite score: distance (closer = higher), rating (stars), review count (popularity), business hours (open now). (6) Return top-K results with name, distance, rating, thumbnail.
Updates and Consistency
When a new business is added: (1) Insert into Place DB (primary SQL). (2) Propagate update to QuadTree servers via message queue. QuadTree update: find the leaf node for the new place's lat/lng; if the node is at capacity, split it into 4 children; insert place into the correct child. Deletion: remove from leaf node; if the node is now empty and its siblings are also empty, collapse siblings back into parent. This dynamic resizing ensures the tree adapts to the place density on the map.