Module 10 · Data structures for scale · Lesson 2 of 11
Quad trees
A spatial tree that splits space into four wherever points are dense and leaves it coarse where they are sparse. Insertion and range queries, why it adapts to density where a fixed grid cannot, nearest-neighbour search.
The video walkthrough is part of Pro.
See what Pro includesWhy it matters
A fixed grid like geohash has one cell size everywhere, so a cell that holds three restaurants in the suburbs holds three thousand in Manhattan, and a nearby query there scans them all. A quad tree subdivides only where points are dense, so every leaf holds a bounded number of points regardless of where it is. It is the structure behind many "find businesses near me" systems and a standard interview answer when density is uneven.
The idea
A quad tree is a tree in which each node covers a rectangular region and has either zero or four children, each covering one quadrant of the parent. Points live in leaves. A leaf that exceeds a capacity (say 100 points) splits into four and redistributes its points. Dense areas end up with deep subtrees of tiny leaves; empty areas stay as single large leaves.
Operations
- 1
Insert
Descend from the root into the quadrant containing the point until a leaf; add the point; if the leaf exceeds capacity, split it into four and push its points down. Depth grows logarithmically with density, not with total count. - 2
Range query (rectangle or radius)
Starting at the root, visit only children whose region intersects the query box; at leaves, test each point. Regions that do not intersect are skipped entirely, which is where the speed comes from. - 3
k nearest neighbours
Find the leaf containing the query point, collect its points, then expand to neighbouring leaves outward (a best-first search ordered by distance to each region) until k points are found and no unexplored region could be closer than the k-th. - 4
Delete and move
Remove the point from its leaf; if the four siblings together fall below capacity, merge them back. A moving object is a delete plus an insert, usually staying in the same leaf.
Quad tree versus fixed grid
| Geohash grid | Quad tree | |
|---|---|---|
| Cell size | Fixed per precision | Adaptive: small where dense, large where sparse |
| Points per cell | Varies wildly with density | Bounded by capacity |
| Storage | Any sorted store or database column | In-memory tree, or serialised nodes in a key-value store |
| Query cost | Nine prefix lookups plus a scan of whatever is in them | Logarithmic descent plus bounded leaf scans |
| Updates | Change a string | Insert, delete, occasional split or merge |
| Distribution | Trivial: shard by prefix | Harder: tree spans the dataset; partition by top-level quadrants or regions |
Running one at scale
A quad tree over a few hundred million points fits in the memory of a large server (each node is a region plus pointers; leaves hold point ids). Build it from a snapshot of the data, keep it updated from a stream of changes, and rebuild periodically to repair fragmentation. Replicate the whole tree to several servers for read scaling, since queries are read-heavy, and partition by region (one tree per country or top-level quadrant) when it outgrows one machine. Persist node structure to a key-value store if restart time matters. Store ids in leaves and look up details elsewhere, so the tree stays compact.
Relatives
An octree is the three-dimensional version (voxels, 3D games). A k-d tree splits on one alternating dimension at a time and suits static point sets and nearest-neighbour search in higher dimensions. R-trees, next lesson, index rectangles rather than points and are what databases use for spatial indexes.