HotShard
Spatial index

Quadtree

Find the points near a location without checking every point, by cutting space into squares.

Every 'find drivers near me' or 'restaurants near me' feature has the same problem behind it. There are millions of points on the map, and you can't check the distance to each one per request. A quadtree fixes this by cutting the map into squares, and cutting finer only where points cluster. A search then skips whole squares that can't hold a match.

~6 min read

Start here: the problem it solves#

TL;DRthe 30-second version
  • Nearby search over millions of points can't scan every point. A B-tree on one coordinate barely helps, because nearness is two-dimensional.
  • A quadtree cuts a square into four quadrants, NW, NE, SW, SE, and keeps cutting only where points are dense.
  • A radius query walks the tree and skips any quadrant whose box misses the circle. That pruning is the whole speedup.
  • Roughly O(log n) when points are spread out. Clustered or coincident points push it toward O(n), so cap the depth.

Say you have millions of points, drivers or restaurants, each with a latitude and longitude. You constantly need to answer 'which ones are within 2km of here?'. Checking the distance to every point is O(n) per query. A ride-hailing service can't scan every driver on the continent for each request.

The obvious fix is a normal B-tree index on the coordinates. It barely helps. A B-tree sorts on one key. Index latitude, and you can grab every point in a latitude band. But that band wraps the whole globe east to west, so it still holds far too many points. A composite (lat, lon) index only helps on the first axis. Once you fix latitude, longitude is unsorted inside it.

You need a structure that partitions both axes together. A spatial index organizes points by where they are, so a query can rule out whole areas at once. A quadtree does this by carving space into a hierarchy of squares. You ask only the squares that overlap your search area and ignore everything else.

The mechanism: squares within squares#

The root node covers the whole world as one square. Each node holds up to a small capacity of points, often 4. When a node overflows, it splits into four equal quadrants, NW, NE, SW, SE, and pushes its points down into whichever child contains each one. Points only ever live in leaf cells.

  1. Insert a point: descend from the root. At each node, pick the child quadrant whose box contains the point, until you reach a leaf.
  2. Add the point to that leaf. If the leaf now exceeds its capacity, split it into four and redistribute its points.
  3. If all the points fall into the same child, that child overflows too. Splitting cascades down until the points separate or a depth cap stops it.
  4. Dense regions keep splitting and get deep. Sparse regions stay one coarse cell.
Why not a fixed grid?A fixed grid has to pick one cell size everywhere. That's too coarse for a city and too fine, and mostly empty, for an ocean. A quadtree only refines where the data is. A city becomes a deep subtree. An empty ocean stays one big cell.

A depth cap is mandatory. If many points share the same coordinates, no split can separate them. Every split funnels them into the same quadrant, and the tree recurses forever. Cap the depth, and the bottom cell becomes an oversized bucket that holds the coincident points in a list. The query still works. It just scans that list.

Now the query. To find every point within a radius, walk the tree from the root. At each node, check whether its square intersects the search circle. If it doesn't, skip the whole subtree. None of those points can be in range. If it does, descend into its children. At a leaf, distance-check only the handful of points it holds.

highlighted = descended (box overlaps the circle) · dashed = pruned (box misses it)

  • rootbox hits circle → descend
    • NWbox misses → prune
      • a
      • b
      • SW
    • NEbox hits → descend
      • leaf pointsdistance-checked
    • SWbox misses → prune
    • SEbox misses → prune

Visited: root, NE. Pruned: NW and everything inside it, plus SW and SE. Only the points in NE's leaf are distance-checked.

A radius query prunes the quadrants it can't reach
PredictYour search circle sits entirely inside one leaf cell's square. How much of the rest of the tree does the query examine?

Hint: What does the box test say at the root's other three children?

Almost none of it. At the root, only the one child whose box contains the circle passes the test. The other three quadrants are pruned right away, and their subtrees are never visited. The query descends a single path to that leaf and distance-checks just the points there. That's why the pruning, not the tree itself, is the source of the speedup.

Complexity: when it's fast, and when it isn't#

When points are reasonably spread out, the depth is about log4(n). Every level cuts the space, and roughly the point count, by four. So descending to a leaf is O(log n).

  • Insert: O(log n) average. Descend to a leaf, append, occasionally split. Each split is O(capacity), a small constant.
  • Point or small-range query: O(log n + k), where k is the number of matches returned.
  • Space: O(n) for the points, plus internal nodes. Each split allocates four children even if some stay empty.
  • Worst case, clustered or coincident points: O(n). The tree becomes a long thin chain, and the box test stops pruning.
The worst case is realA quadtree doesn't self-balance. Its shape comes entirely from where the points are. Pile a million points into one tiny area and the tree becomes a chain of single-occupied quadrants all the way down to the depth cap. With no cap, depth and memory are unbounded. Two points at distance d in a world of width W force about log2(W/d) levels, no matter how many points there are.

If this comes up in an interview#

The one-linerA quadtree cuts space into four quadrants, recursively, only where points are dense. A radius query prunes every quadrant whose box misses the circle, so 'near me' costs about O(log n) instead of a scan of every point.
Why not just put a B-tree index on (lat, lon)?

A B-tree sorts on one key. Fix latitude, and longitude is unsorted inside that band, so the band still holds far too many points. Nearness is two-dimensional, and a 1D sort has to pick an axis. You need an index that partitions both axes together.

What makes a quadtree slow?

Clustered or coincident points. The tree's shape mirrors the data, so when many points pile into a small area it becomes a deep, thin chain, and queries drift toward O(n). Without a depth cap, coincident points make subdivision and memory unbounded. A depth cap and a sensible leaf capacity keep it fast.

Quadtree vs. k-d tree vs. R-tree: when does each win?

A quadtree splits space into four equal quadrants regardless of the data. It's simple, with fixed cell geometry, but no balance guarantee. A k-d tree splits at the median point one axis at a time, so it stays balanced and works in higher dimensions, which is good for k-nearest-neighbor. An R-tree groups nearby objects into balanced bounding rectangles, indexes shapes, not just points, and handles updates well. That's what PostGIS uses.

How would you do 'drivers within 2km' at global scale with constantly moving drivers?

Don't keep one global quadtree. Shard space with a cell system like geohash, Google S2, or Uber H3, so each region has its own small tree and the cell ID doubles as the shard key. Moving points that cross cell boundaries cause split and merge cascades, so rebuild hot trees periodically instead of updating in place.

Trade-offs: quadtree vs. its relatives
Quadtreek-d treeR-treeGeohash
IndexesPoints (2D)Points (k-D)Points and rectanglesPoints → 1D string
BuildSimple, top-down splitsMedian splits per axisComplex, balancedTrivial bit-interleave
QueryBox-prune, ~O(log n)~O(log n), good k-NN~O(log n), balancedPrefix range scan
UpdatesSplit cascades; no rebalanceHard to keep balancedDesigned for dynamicJust insert a key
ClusteringDegrades (unbalanced)Stays balancedStays balancedEdge-of-cell misses
Best forIn-memory point sets, gamesk-NN, higher dimensionsGeospatial DBs (PostGIS)Sharding, key-value stores

Geohash turns a 2D coordinate into a 1D string by interleaving the latitude and longitude bits. Shared prefixes mean the points are close, so an ordinary B-tree becomes a spatial index. But two points can be physically close and land in different prefix buckets. Real systems query the cell plus its eight neighbors to compensate. Quadtrees, k-d trees, and R-trees prune in the plane directly, so they don't have this problem.

Rule of thumbReach for a quadtree when the data is points, mostly in memory, not badly clustered, and you value simplicity. Reach for an R-tree when you index rectangles or shapes, or need balance and durable on-disk updates in a database. Reach for geohash, S2, or H3 when you need to shard space across many machines using a stable 1D cell ID.
Failure modes
  • Degenerate deep trees. Clustered or near-coincident points force subdivision far past the point of usefulness, and query cost climbs toward O(n).
  • Unbounded subdivision. Exact duplicates can never be separated by splitting, so without a depth cap the tree recurses forever and exhausts memory. Always cap depth and let the bottom cell hold a bucket.
  • Uneven latency. Real-world skew (everyone in the city, no one in the desert) makes some branches far deeper than others, so latency varies by query location.
  • Costly updates. Frequent inserts and deletes in dense regions trigger split and merge cascades. Moving objects, like live drivers crossing cell boundaries, make this worse. Many systems rebuild periodically instead of updating in place.
  • Empty-child overhead. Each split allocates all four children even when the points fall into one, wasting memory in sparse but deep regions.
References
References
Up nextGeohash
RelatedB+ Tree← Back to the learning path

Feedback on this topic →