How it works
For location search, a common variant is a bucketed region quadtree. Start with a rectangle covering your service area. Each internal node has four children representing its northwest, northeast, southwest, and southeast quarters; each leaf holds a bucket of location IDs and coordinates.
Insert a point by following the quadrant that contains it. When a leaf exceeds a chosen capacity, such as 100 points, split it and redistribute its contents. Set a maximum depth or minimum cell size so identical or tightly clustered coordinates cannot cause endless subdivision.
For a radius query, compute a bounding box around the search circle and traverse only nodes whose regions intersect it. Collect candidates from those leaves, then calculate geographic distance to remove points outside the circle. Search every intersecting cell, not just the one containing the requester.
For nearest-neighbor search, visit regions in order of their minimum possible distance from the query point. Once you have k candidates, stop only when no unvisited region can contain a closer point. Finding k points in the first leaf is not enough.
For moving objects, update coordinates in place while they remain in the same leaf; remove and reinsert them when they cross a boundary. Track object-to-leaf membership to avoid searching for the old entry, and use update versions to reject out-of-order locations. Optional merging of sparse sibling leaves needs hysteresis to avoid repeated splits and merges.
A quadtree is an index, not a complete distributed storage design. You can assign top-level regions to servers and maintain local trees, but must separately handle routing, replication, and queries crossing server boundaries. For geographic data, define the coordinate projection and handle longitude wrapping; latitude and longitude degrees are not uniform distances.
A worked example
Finding nearby drivers in a dense city
Suppose a service indexes 40,000 available drivers in a 32-by-32-kilometer projected region. Configure leaves to split above 100 drivers, with a minimum cell width of 125 meters. Downtown subdivides more deeply than the outskirts; the minimum width permits crowded leaves to exceed 100 entries. For a rider requesting drivers within 2 kilometers, traverse leaves intersecting the search bounding box, deduplicate driver IDs, and filter by geographic distance and location age. A driver crossing a leaf boundary changes membership using a versioned update. Discovery returns candidates, not reservations: the matching service must still atomically claim an available driver. If downtown traffic overloads one server, move ownership or add serving capacity rather than merely splitting its local tree.
Trade-offs to say out loud
- Adaptive cells versus structural overhead
- Dense areas get finer subdivisions, but tree nodes, child references, and bucket metadata consume memory.
- Selective search versus worst-case scans
- Spatial pruning can greatly reduce candidate work, but large queries or clustered data can still require visiting most points.
- Fast reads versus moving-object maintenance
- Frequent location changes create membership updates, synchronization work, and possible split or merge churn.
- Smaller cells versus query fan-out
- Finer cells reduce irrelevant candidates per cell but can increase the number of cells and servers a query touches.
- Adaptive indexing versus load balancing
- Splitting a dense leaf does not relieve an overloaded server unless ownership or query execution also changes.
- Freshness versus coordination
- Asynchronous index updates improve write-path independence but can temporarily miss moved objects or return stale candidates.
When to reach for it
- The core request is a radius, bounding-box, or nearest-neighbor search over point locations.
- Location density varies sharply, such as crowded downtown areas surrounded by sparse suburbs.
- You need to explain how nearby discovery avoids scanning all drivers, profiles, restaurants, or listings.
- The interviewer asks how spatial cell size should change as an area becomes more crowded.
How to bring it up in the interview
- Start with the query contract: radius or nearest k, expected density, location update rate, and acceptable staleness. Explain why those requirements justify a spatial index.
- Draw one split and walk through a query crossing two leaf boundaries. Interviewers often probe whether your search can miss a closer object in an adjacent cell.
- State a leaf capacity and maximum depth as tunable choices, not universal constants. Expect questions about identical coordinates, split churn, and memory usage.
- Separate candidate discovery from authoritative decisions. Nearby driver results may be stale; assigning a driver still needs an exclusive claim against current availability.
- Compare with geohash and explain distributed ownership separately. Expect follow-ups on cross-region fan-out, hot downtown areas, concurrent updates, and rebuilding an index after failure.
Common mistakes
- Searching only the requester's leaf, which misses nearby objects across cell boundaries.
- Claiming every lookup is O(log n), despite uneven depth, broad queries, and worst-case scans.
- Splitting without a depth or cell-size limit, allowing coincident points to trigger unbounded subdivision.
- Treating a tree split as automatic database sharding or assuming equal point counts imply equal traffic.
- Using raw latitude and longitude differences as physical distance, or treating a stale spatial index as authoritative availability.
Where it comes up
Interview questions where quadtree is part of a strong answer, and why.
- Design a ride hailing app like UberNearby-driver discovery needs a spatial index that supports frequent movement, boundary-aware search, and stale candidate handling.
- Design a food delivery app like DoorDashCourier dispatch needs efficient nearby-courier retrieval while location updates continuously change spatial membership.
- Design a dating app like TinderNearby-profile discovery needs spatial pruning before applying exclusion histories, preferences, and privacy checks.
- Design a restaurant review app like YelpNearby restaurant search needs spatial candidate retrieval that covers cell boundaries before filtering and ranking.
- Design Facebook MarketplaceLocation-based listing discovery needs bounded spatial retrieval rather than scanning every active listing.
Questions people ask
What is a quadtree used for in system design?
A quadtree indexes two-dimensional locations so radius, map-window, and nearest-neighbor queries can skip irrelevant regions. It is useful for nearby discovery in ride hailing, local search, and marketplaces. It does not itself provide durable storage, replication, or exclusive assignment.
What is the difference between quadtree and geohash?
A quadtree explicitly divides a region into four children at each split and can adapt its leaf depth to local density. Geohash encodes latitude and longitude into hierarchical string cells, which are convenient as database keys and prefixes. Geohash can also use variable precision, so the distinction is not simply adaptive versus fixed; compare tree traversal and update costs with prefix/range lookup and cell-covering costs. Both need boundary-aware searches and exact distance filtering.
What is the time complexity of a quadtree?
Point insertion follows a path of depth h, plus any bucket redistribution needed during splitting. Range and nearest-neighbor query cost depends on visited nodes and examined points, not just tree depth. Favorable distributions allow effective pruning, but worst-case queries can examine all n points.