System design
Part 4 of 6 · Geospatial IndexingR-Trees & R-star — MBRs, Bulk Load & Range/KNN Queries
R-trees index rectangles via nested minimum bounding rectangles. Databases (PostGIS GiST) use them for range, intersect, and kNN. Bulk-load static POIs; do not page-split a moving fleet — keep cells for membership.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Where the R-tree belongs
Prefer
Bulk-loaded R-star / GiST for shapes; cells for the fleet
POIs, buildings, and geofences are read-mostly. Pack them bottom-up. Live drivers upsert into cell sets. Hybrid is the production answer, not a religion.
- MBRs are cheap rejectors — exact geometry still runs.
- R-star reinserts overflow entries to improve tree shape.
- Hilbert packing is a cousin of S2's 1D locality.
Alternative
Incremental R-tree on every GPS tick
Each move updates an MBR. Pages split. Overlap grows. You invented a slow quadtree with extra bounding boxes.
- A global R-tree is also a global write hotspot.
- Shard by region/cell, R-tree inside — never one planet tree.
- GIN is inverted posting, not geometry — do not mix the AMs.
Window and kNN
False positives at the MBR layer are normal. Exact test is mandatory.
- 1
Search window
AABB, or radius expanded to a bbox. - 2
Prune
Descend only children whose MBR intersects the window (range) or looks close (kNN bound). - 3
kNN queue
Best-first pop by mindist. Stop when k results beat remaining lower bounds. - 4
Refine
Exact geometry or haversine. Same theme as cell fan-out.
Overview
R-trees index rectangles via nested minimum bounding rectangles (MBRs). PostGIS GiST, MySQL/SpatiaLite, and many GIS engines use them for range, intersect, and k-nearest-neighbor.
Interviews want overlap intuition, why R-star reinserts, bulk load vs incremental insert, and when cells beat trees for fleet tracking.
You should be able to:
- Draw leaf MBRs inside parent MBRs and a pruning walk.
- Say why MBR hits are not answers.
- Refuse R-tree membership for 1–5 s GPS.
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: window query with MBR pruning
Decisions
- 1
Step 1 Search window - box or radius bbox
- nextStep 2 Start at the root MBR
- 2
Step 2 Start at the root MBR
- nextStep 3 Child MBR intersects the window?
- ?
Step 3 Child MBR intersects the window?
- noStep 4a Prune that subtree
- yesStep 4b Descend into the child
- 4
Step 4a Prune that subtree
- 5
Step 4b Descend into the child
- nextStep 5 Collect leaf candidates
- 6
Step 5 Collect leaf candidates
- nextStep 6 Exact geometry or haversine test
- return MBR hits as answersFailure path - empty corners of rectangles count as matches
- 7
Step 6 Exact geometry or haversine test
- nextStep 7 Return true hits
- 8
Step 7 Return true hits
- 9
Failure path - empty corners of rectangles count as matches
Start at the root MBR. Prune any child whose rectangle misses the window, and descend into the ones that intersect. Leaf hits are candidates. An exact geometry or haversine test drops the empty corners of those rectangles.
Lesson map
R-Trees & R-star — MBRs, Bulk Load & Range/KNN Queries
Diagram 1 walks 8 steps from Step 1 Search window - box or radius bbox through Step 7 Return true hits.
Architecture. Step 1 Search window - box or radius bbox Ready. Step 2 Start at the root MBR Ready. Step 3 Child MBR intersects the window? Ready. Step 4a Prune that subtree Ready. Step 4b Descend into the child Ready. Step 5 Collect leaf candidates Ready. Step 6 Exact geometry or haversine test Ready. Step 7 Return true hits Ready. Failure path - empty corners of rectangles count as matches 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 Search window - box or radius bbox Ready"] B["Step 2 Start at the root MBR Ready"] C["Step 3 Child MBR intersects the window? Ready"] P["Step 4a Prune that subtree Ready"] D["Step 4b Descend into the child Ready"] E["Step 5 Collect leaf candidates Ready"] F["Step 6 Exact geometry or haversine test Ready"] G["Step 7 Return true hits Ready"] X["Failure path - empty corners of rectangles count as matches Ready"] A -->|continues| B B -->|continues| C C -->|no| P C -->|yes| D D -->|continues| E E -->|continues| F F -->|continues| G E -->|return MBR hits as answers| X
Diagram 2 - Failure path: R-tree as the live fleet index
Sequence
- 1
Fleet GPS → R-tree pages
Step 1 10k drivers update every 2 s
- 2
R-tree pages → R-tree pages
Step 2 each move grows or shrinks MBRs up the tree
- 3
R-tree pages → R-tree pages
Step 3 overflows cause splits and R-star forced reinserts
- 4
Nearby query → R-tree pages
Step 4 queries wait on hot pages and overlapping MBRs
- 5
Fleet GPS
Step 5 write amplification and slow reads
- 6
Fleet GPS
Fix - cells in Redis for the live fleet, keep the R-tree for geofences
Ten thousand drivers updating every two seconds grow, shrink, split, and reinsert MBRs on the way to the root. Nearby queries wait on those hot pages. Keep the live fleet in cells. Leave the R-tree for geofences.
Diagram 3 - Decision: build and query an R-tree, or use cells
Decisions
- ?
Step 1 Indexing rectangles or polygons?
- no - moving pointsCells - geohash, H3 or S2
- yesStep 2 Data mostly static?
- 2
Cells - geohash, H3 or S2
- ?
Step 2 Data mostly static?
- yesBulk load - STR or Hilbert packing
- no - steady insertsR-star tree with incremental inserts
- 4
Bulk load - STR or Hilbert packing
- nextStep 3 Query type?
- 5
R-star tree with incremental inserts
- nextStep 3 Query type?
- Wrong pick for per-second GPSMBR churn thrashes pages
- ?
Step 3 Query type?
- windowMBR intersect, then exact test
- kNNBest-first queue by mindist
- 7
MBR intersect, then exact test
- 8
Best-first queue by mindist
- 9
MBR churn thrashes pages
Moving points belong in cells. Mostly static rectangles bulk-load with STR or Hilbert packing. A steady insert stream wants an R*-tree. Window queries prune by MBR intersection, then test exact geometry. kNN walks a best-first queue ordered by mindist. An R*-tree on per-second GPS thrashes pages.
MBR mental model
- Leaf: MBR → object id / geometry.
- Internal: MBR → child page, covering its children.
- Query: descend nodes whose MBR intersects the search window; prune the rest.
- Overlap among sibling MBRs = extra I/O. Split quality matters.
Empty space inside an MBR is why you get false positives. Always run the exact predicate.
R-tree vs R*-tree
| Flavor | Insert story | Query story |
|---|---|---|
| Classic R-tree | Quadratic / linear split; local insert | Fine if splits stay clean |
| R*-tree | Optimize overlap, margin, area; forced reinsert of overflow entries | Usually better; slightly costlier insert |
| Bulk load (STR, Hilbert-pack) | Sort geometries, build bottom-up | Best for static / rarely updated POIs and map features |
Hilbert R-trees pack by a space-filling curve — cousin of S2 thinking.
Write-heavy vs read-heavy
- Static POIs / polygons → bulk-load R-star or clustered Hilbert R-tree.
- Moving drivers every 1–5 s → MBR updates thrash pages. Prefer cell membership (geohash / H3) in Redis. Keep R-tree for zones.
- Hybrid: cells for live fleet; GiST for geofences and analytics. Architecture: location services.
vs cells and quadtrees
- Cells: O(1) encode, easy shards, weak for arbitrary polygons without coverings.
- Quadtree: equal splits, no MBR overlap concept; simpler, less geometry-flexible. Depth: quadtrees.
- R-tree: first-class rectangles/polygons; harder to shard by primary key alone. Shard by region/cell, tree inside.
Query path
Range and kNN share prune-then-refine. No self-loop on the intersect decision — prune is its own node.
Decisions
- 1
1 Search AABB
- next2 Root MBR
- 2
2 Root MBR
- next3 Intersects child?
- ?
3 Intersects child?
- yes4 Descend or kNN queue
- no5 Prune child
- 4
4 Descend or kNN queue
- next6 Leaf candidates
- 5
5 Prune child
- 6
6 Leaf candidates
- next7 Exact geometry
- 7
7 Exact geometry
kNN: priority queue ordered by mindist(MBR, query point). A remaining node whose lower bound exceeds the k-th result is dead.
GiST — geometry only
Postgres GiST is a balanced tree of predicates. Geometry, ranges, and some trigram ops use it. GIN is inverted posting (arrays, JSONB, FTS). B-tree is equality/range/sort. Those three AMs are taught in B-tree vs Hash vs GIN vs GiST. This page only needs: geometry → GiST → R-tree-like.
Sandbox: MBR intersect and didactic kNN (Python)
Flat list + mindist — not a paged tree. Shows why the bound exists.
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
Query point outside two sibling MBRs. One MBR's mindist is 10, the other 50. You already have k=1 at distance 12. Do you open the second child? Why does overlap make this question harder?
Interview Q&A
Why MBR false positives?
Answer
A rectangle covers empty space. The object may be a skinny polygon in one corner. Exact geometry (or haversine for points) is required.
Why R-star forced reinsert?
Answer
Overflow entries are taken out and inserted again so a bad local split can be repaired. Better query shape; extra insert work.
When do you bulk load?
Answer
Initial POI load, nightly rebuilds, map features. Avoid for per-second GPS. STR and Hilbert-pack sort then build bottom-up.
kNN vs radius?
Answer
kNN is best-first by lower bound until k results beat the rest. Radius is a window plus filter. Both prune with MBRs.
GiST vs GIN?
Answer
GiST: lossy trees / geometry / ranges. GIN: inverted lists for arrays, JSONB, FTS. See SQL indexes — this cluster does not re-teach B-tree or Hash.
How do you shard an R-tree?
Answer
You do not shard one global tree by primary key. Shard by region or cell, R-tree inside each shard.
Hilbert R-tree?
Answer
Pack entries in space-filling-curve order so nearby objects share leaves. Same locality instinct as S2 cell ids.
Fleet tracking?
Answer
Usually cells in an in-memory KV. R-tree / GiST for geofence polygons and analytics.
What does overlap do to I/O?
Answer
A query rectangle may intersect two sibling MBRs even if the true objects sit in one. You read extra pages. Split heuristics exist to shrink that.
mindist of 0?
Answer
The query point sits inside the MBR. That child cannot be pruned; you must open it (then maybe prune deeper).