System design
Part 3 of 6 · Geospatial IndexingQuadtrees & Space Partitioning — Adaptive Cells, Density & Updates
Quadtrees split a 2D region into four children when a capacity threshold is hit. Depth follows density — downtown deep, desert shallow. Cheap in-process; awkward as a durable cross-service shard key for moving objects.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Adaptive split vs a global cell id
Prefer
Quadtree in-process or per shard; cells across services
Use a quadtree where density skew is the problem and the tree lives in one process (or one shard). Keep geohash/H3/S2 when many services must agree on a cell id without sharing the tree.
- Maps tiles / quadkeys are a static quadtree of the world.
- Loose bounds delay splits for movers.
- Coarse parent cell + QT inside the shard is a common hybrid.
Alternative
One mutable global quadtree as the shard key
Splits change leaf identities. Every mover that crosses a midplane pays delete+insert. Merges under churn are often skipped — the tree only grows.
- No stable ID unless you persist the path.
- Uneven depth complicates load balancing.
- R-trees exist when the objects are rectangles, not points.
Insert then query
Equal midplane splits. No MBR overlap story — that is the R-tree page.
- 1
Descend to a leaf
Compare x/y to the node midplanes. Point-region variants store points only in leaves. - 2
Store or split
If capacity exceeded, create four children and reinsert the leaf's points. - 3
Query AABB
Skip children that do not overlap the search box. Convert radius to a bbox first. - 4
Filter
Haversine (or exact geom) on the candidates. Same theme as cells.
Overview
A quadtree recursively splits a 2D region into four equal children when a capacity / density threshold is hit. Maps tiles, collision systems, and sparse-rural / dense-city indexes like adaptive cells.
Variants: point QT, region QT, PR (point-region), MX; loose quadtrees for moving objects (fat bounds so movers do not split every tick). 3D is an octree (eight children).
You should be able to:
- Draw split and prune.
- Contrast with geohash (fixed id) and R-tree (data-sized MBRs with overlap).
- Say when you refuse a QT as the fleet shard key.
Diagrams - step by step
Three small diagrams. Step numbers in the labels give the animation order. The lesson map under Diagram 1 plays those steps.
Diagram 1 - Happy path: insert with split, then range query
Decisions
- 1
Step 1 Insert point x y
- nextStep 2 Descend by midplanes to a leaf
- 2
Step 2 Descend by midplanes to a leaf
- nextStep 3 Leaf over capacity?
- ?
Step 3 Leaf over capacity?
- noStep 4a Store point in the leaf
- yesStep 4b Split into NW NE SW SE
- 4
Step 4a Store point in the leaf
- nextStep 6 Range query box arrives
- 5
Step 4b Split into NW NE SW SE
- nextStep 5 Reinsert leaf points into children
- 6
Step 5 Reinsert leaf points into children
- nextStep 6 Range query box arrives
- 7
Step 6 Range query box arrives
- nextStep 7 Visit only overlapping nodes
- 8
Step 7 Visit only overlapping nodes
- nextStep 8 Filter by true distance
- skip the distance filterFailure path - box corners return points outside the radius
- 9
Step 8 Filter by true distance
- 10
Failure path - box corners return points outside the radius
Insert walks midplanes to a leaf. A full leaf splits into NW, NE, SW, and SE and the old points are reinserted. A range query then visits only nodes whose box overlaps the query, and a true-distance filter drops the corners.
Lesson map
Quadtrees & Space Partitioning — Adaptive Cells, Density & Updates
Diagram 1 walks 9 steps from Step 1 Insert point x y through Step 8 Filter by true distance.
Architecture. Step 1 Insert point x y Ready. Step 2 Descend by midplanes to a leaf Ready. Step 3 Leaf over capacity? Ready. Step 4a Store point in the leaf Ready. Step 4b Split into NW NE SW SE Ready. Step 5 Reinsert leaf points into children Ready. Step 6 Range query box arrives Ready. Step 7 Visit only overlapping nodes Ready. Step 8 Filter by true distance Ready. Failure path - box corners return points outside the radius Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB A["Step 1 Insert point x y Ready"] B["Step 2 Descend by midplanes to a leaf Ready"] C["Step 3 Leaf over capacity? Ready"] D["Step 4a Store point in the leaf Ready"] E["Step 4b Split into NW NE SW SE Ready"] F["Step 5 Reinsert leaf points into children Ready"] Q["Step 6 Range query box arrives Ready"] O["Step 7 Visit only overlapping nodes Ready"] FL["Step 8 Filter by true distance Ready"] X["Failure path - box corners return points outside the radius Ready"] A -->|continues| B B -->|continues| C C -->|no| D C -->|yes| E E -->|continues| F D -->|continues| Q F -->|continues| Q Q -->|continues| O O -->|continues| FL O -->|skip the distance filter| X
Diagram 2 - Failure path: moving objects thrash the tree
Sequence
- 1
GPS stream → Quadtree
Step 1 driver moves within a leaf - cheap overwrite
- 2
GPS stream → Quadtree
Step 2 driver crosses a leaf boundary - delete plus insert
- 3
Quadtree → Quadtree
Step 3 insert overflows the new leaf - split and reinsert
- 4
GPS stream → Quadtree
Step 4 driver crosses back - old leaf underflows and merges
- 5
GPS stream
Step 5 thousands of drivers per second repeat this and the tree thrashes
- 6
GPS stream
Fix - fixed cells with TTL, loose bounds, or periodic rebuild from a snapshot
A driver who stays inside one leaf is a cheap overwrite. Crossing a boundary is a delete plus an insert, and a full leaf splits. Crossing back can merge. Thousands of those moves a second thrash the tree. Use fixed cells with a TTL, loose bounds, or a periodic rebuild.
Diagram 3 - Decision: quadtree vs fixed cells vs R-tree
Decisions
- ?
Step 1 What are you indexing?
- points, even densityFixed grid - geohash or H3
- points, very uneven densityStep 2 Points move every few seconds?
- rectangles or polygonsR-tree
- 2
Fixed grid - geohash or H3
- Wrong pick on airport-level densityOne cell holds a huge hot set
- ?
Step 2 Points move every few seconds?
- yesFixed cells with TTL or a loose quadtree
- no - read-heavy tilesQuadtree rebuilt from snapshots
- 4
Fixed cells with TTL or a loose quadtree
- 5
Quadtree rebuilt from snapshots
- Wrong pick as a durable shard keyNo stable global id across processes
- 6
R-tree
- 7
No stable global id across processes
- 8
One cell holds a huge hot set
Even point density wants a fixed grid. Uneven density that moves every few seconds wants fixed cells or a loose quadtree, not a tight tree rebuilt on every GPS tick. Read-heavy tiles can rebuild a quadtree from snapshots. Rectangles and polygons want an R-tree. A quadtree node id is a poor durable shard key, and one geohash cell melts under airport density.
vs fixed cells and R-trees
| vs | Quadtree |
|---|---|
| Geohash / H3 / S2 | No global ID without encoding the path. Harder as a durable shard key unless you persist the tree or hash a coarse parent. |
| R-tree | Axis-aligned equal splits. R-tree MBRs size to data and may overlap. |
| Uniform grid | Adaptive saves memory in sparse areas; uneven depth complicates balance. |
Updates and moving objects
- Driver moves within a leaf → cheap overwrite.
- Crosses a leaf boundary → delete + insert; may trigger split (or merge).
- High-churn fleets: prefer fixed cells + TTL, or loose bounds that delay splits.
- Read-heavy tile servers: rebuild from snapshot; do not mutate per GPS tick.
Merge policy: underfull siblings can coalesce. Expensive if churn is high — production often skips merges and only splits.
Density and hotspots
Airports create deep subtrees. Query fan-out stays local, but memory and lock granularity skew.
Shard strategy: partition by a coarse parent cell, run the quadtree inside the shard. When QPS or cardinality blows the parent, split that parent across shards — cell shards, not a new ring lecture.
Hot leaf: cap depth; keep an overflow list; or switch the hot region to finer fixed H3.
Slippy quadkeys are a quadtree of the world — static, read-heavy, CDN-friendly. Live fleet is a different QPS shape: location services.
Insert / range query
Split insert and query so the chart stays one column.
Decisions
- 1
1 Point x y
- next2 Find leaf
- 2
2 Find leaf
- next3 Capacity exceeded?
- ?
3 Capacity exceeded?
- yes4 Create 4 children
- no6 Store in leaf
- 4
4 Create 4 children
- next5 Reinsert leaf points
- 5
5 Reinsert leaf points
- 6
6 Store in leaf
Flow
- 1
1 Query bbox
- next2 Visit overlapping nodes
- 2
2 Visit overlapping nodes
- next3 Filter true distance
- 3
3 Filter true distance
No labeled self-loop on the capacity node — yes goes to split, no goes to store.
Sandbox: point quadtree (Python)
Capacity-2 demo. Query a corner of the world.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Same idea (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Pitfalls
Insert 100 points in one corner and 2 in the opposite corner, cap=4. How deep is each side? A driver then drives across the midplane every second. Do you keep the QT or switch that region to geohash/H3?
Interview Q&A
When a quadtree over geohash?
Answer
Highly skewed density and an in-process spatial index. Not when many services need a simple, stable shard key.
Merge policy?
Answer
Underfull siblings can coalesce. Under high churn, skip merges — splits are one-way. Rebuild from snapshot if the tree gets ugly.
How do you query a radius?
Answer
Convert to an axis-aligned bbox, visit overlapping nodes, haversine-filter. Same two-phase idea as cell fan-out.
Thread safety?
Answer
Fine-grained locks per node, or copy-on-write snapshots for readers. A global lock on the root dies at airport QPS.
3D?
Answer
Octree — eight children, same capacity/split/prune story.
Hotspot leaf?
Answer
Cap depth; overflow list; or switch the hot region to finer fixed H3. Do not let one airport become the whole RAM budget.
How do map tiles relate?
Answer
Quadkeys / slippy tiles are a quadtree of the world. Static, read-heavy, CDN. Not the live fleet store.
vs R-tree?
Answer
R-trees minimize overlap and margin for rectangles. Quadtrees use equal midplane splits — simpler, less geometry-flexible.
How do you shard a quadtree?
Answer
You usually do not shard the tree globally. Shard by coarse parent cell, QT inside. Rebalance hot parents with cell shards.
Loose quadtree?
Answer
Inflated bounds so a moving point can travel a little without a delete+insert. Trades query extra-visit for fewer structural updates.