Engineering Atlas › System Design Fundamentals

Splitting space with quadtrees

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

Structure

Every node owns an axis-aligned box. A leaf stores a list of points. An internal node stores no points, only four children: north-west, north-east, south-west, south-east, each covering exactly a quarter of the parent. The root covers the whole domain, for example the world in latitude and longitude, or a projected map in metres.

This is the point-region (PR) quadtree, the variant most location services use. Splits happen at the box centre, not at a data point, so the shape depends only on which points exist, not on insertion order. The original quadtree of Finkel and Bentley split at each inserted point instead, so its shape did depend on order (Finkel and Bentley, 1974); Samet's survey names and compares the variants (Samet, 1984).

Insert

Descend to the leaf whose box contains the point and append it. If the leaf now exceeds capacity, create four children and push its points down. A maximum depth is essential: 600 points with identical coordinates (a stadium, a warehouse) can never be separated, so without a cap you recurse until the stack dies. At max depth a leaf simply grows.

Range query

Start at the root. Skip any subtree whose box misses the rectangle, test points in leaves, and recurse into internal nodes. Pruning is what makes this fast: a 2 km search in a planet-wide tree touches a few dozen nodes.

Nearest neighbours

For k-nearest, keep a priority queue keyed by the minimum distance from the query point to each node's box. Pop the closest entry; a leaf pushes its points with exact distances, an internal node pushes its children. Stop after popping k points. This "distance browsing" algorithm works for any hierarchical spatial index, R-trees included, and can return neighbours one at a time without fixing k in advance (Hjaltason and Samet, 1999). This best-first search visits the fewest nodes and handles nearest points in a neighbouring quadrant, where grid and geohash approaches stumble.

Delete and update

Deletion is a leaf operation; when four siblings together hold fewer than the capacity, merge them back into one leaf. A moving object is delete plus insert, but most updates stay in the same leaf and can be done in place.

Depth and memory

With N points and capacity C there are roughly N / C leaves, and depth grows with the density contrast between sparse and dense regions. Twenty levels of a world quadtree reach cells about 38 m wide at the equator, which is exactly the width of a level-20 web map tile (Bing Maps tile system).

Down the stack

Layer 1The contract

A range query returns exactly the points inside the rectangle, and a best-first k-nearest search returns the true k nearest points. Both guarantees hold only for the snapshot the query reads. Because the tree usually lives in a service's memory, freshness is whatever the update path provides: "changes visible within 10 minutes" for snapshot rebuilds, or seconds with a change stream. Memory use is roughly linear in the number of points, and query time grows with local density, not total size.

Layer 2The mechanism

d3-quadtree stores internal nodes as sparse 4-element arrays of children and leaves as small objects holding a datum. Coincident points are chained in a linked list through a next field instead of splitting forever, which is an alternative to a depth cap (d3-quadtree docs). Its visit callback walks nodes in pre-order and lets the caller prune a subtree by returning true, which is how range and nearest-neighbour searches are built on it.

Lucene's spatial module took a different route with QuadPrefixTree: each quadtree cell becomes a string token, and shapes are indexed as the set of cell tokens that cover them, so an inverted index can answer spatial queries. Elasticsearch used this for geo_shape (21 levels by default, 29 at most) but deprecated prefix trees in 6.6 because of the precision trade-off; shapes are now split into triangles and stored in a BKD tree (Elasticsearch 7.x docs). Older guides that tell you to tune tree_levels are describing the legacy path.

A linear quadtree stores only leaves, keyed by their Morton code, in a B-tree. Web map tiles are the best-known case: a Bing "quadkey" interleaves the tile's X and Y bits into base-4 digits, its length is the zoom level, and a tile's key starts with its parent's key, so tiles sit in an ordinary B-tree index (Bing Maps tile system). Postgres also ships a disk-based quadtree: SP-GiST's default operator class for points, quad_point_ops, which supports <-> nearest-neighbour ordering (Postgres docs).

Layer 3The machine

A pointer-based quadtree is a chain of dependent loads. Each level needs the child pointer before it can fetch the child, so a 20-level descent that misses cache costs about 20 times 80 to 100 ns, near 2 us. In practice the top 10 levels stay hot in L2 and L3 cache, and only the last few levels miss.

Node layout matters. Four 8-byte child pointers plus a 32-byte box is 64 bytes, one cache line, before allocator headers. Storing nodes in one flat array with 32-bit child indices halves the pointer size and keeps siblings adjacent. In garbage-collected runtimes, a snapshot rebuild that allocates half a million node objects every 10 minutes pushes the old generation hard; arrays of primitives avoid most of that. The swap itself is a single atomic reference store, and readers on the old tree finish undisturbed.

Why it's built this way

  1. Point density varies by orders of magnitude between oceans and city centres, so cells must adapt instead of being fixed.
  2. Adaptive cells mean a pointer-linked tree, which is natural in memory and awkward in a database.
  3. In-memory state must be rebuilt and replicated, so services use snapshot builds and atomic swaps.
  4. Pointer chasing is slow on modern CPUs, so fast implementations flatten the tree into arrays or Morton-ordered leaves.

Diagram

flowchart TD
    I["Insert point P"] --> D["Descend to child containing P"]
    D --> L{"Leaf?"}
    L -->|no| D
    L -->|yes| A["Append P to leaf"]
    A --> O{"Count > capacity and depth < max?"}
    O -->|no| Done["Done"]
    O -->|yes| S["Create NW, NE, SW, SE children"]
    S --> R["Move leaf points into children"]
    R --> Done

Worked example

A local-search service indexes 40 million businesses worldwide and answers "top 20 near me" at 15,000 QPS.

With capacity 100, the tree has around 400,000 leaves and about 530,000 nodes in total. Each point is an 8-byte ID plus two 8-byte floats, so 24 bytes; 40 million points is just under 1 GB, and node overhead adds perhaps 50 MB. That fits in the memory of a single serving host, so each replica holds the whole tree and queries never cross the network.

A KNN query for 20 results visits 6 to 15 leaves and computes up to 1,500 exact distances, 20 to 50 microseconds on one core. At 15,000 QPS the index needs under one core; serialisation, ranking, and the network cost more.

The hard part is freshness. Businesses change at about 50 updates per second. Two common designs:

Most teams start with snapshot-and-swap and add an overlay of recent changes if they need faster freshness.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
PR quadtree in memoryAdapts to density, fast KNN, simple codeYou own build, memory, replication, and freshnessRead-heavy, data fits in RAM, density varies a lot
Geohash index in a databaseNo custom service, durable, easy to shardFixed cell size, edge effects, more candidates in dense areasModerate scale, simple radius queries
R-tree (PostGIS, SQLite)Indexes shapes, not just points; disk-backedOverlapping boxes, write cost, database-boundPolygons and lines, or data larger than RAM
Fixed gridTrivial, O(1) cell lookupWastes memory in empty areas, overloads dense cellsBounded area with fairly uniform density

Pitfalls in production

Leadership lens

Check yourself

  1. Why does a PR quadtree's shape not depend on insertion order?

    Show answer

    It always splits at the geometric centre of a box, so the final set of leaves is determined only by which points exist, not by the order they arrived.

  2. A range query near a quadrant boundary returns correct results without any neighbour logic. Why, when geohash needs 8 neighbours?

    Show answer

    The query tests box intersection at every level, so every node that overlaps the search rectangle is visited regardless of which side of a boundary it is on.

  3. What breaks if you choose a capacity of 1?

    Show answer

    The tree becomes very deep with many tiny nodes, pointer-chasing dominates query time, memory overhead per point explodes, and duplicate points can only be handled by the depth cap.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →