Engineering Atlas › System Design Fundamentals

Indexing regions with R-trees

12 min read · last reviewed 2026-10-17

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

In one minute

How it works

Shape of the tree

Each node fits in one page, typically 4 to 8 KB, holding between m and M entries (M is the fanout, often 50 to 200; m is about 40 percent of M, the value the R\*-tree authors found retrieved best (Beckmann et al., 1990)). A leaf entry is (MBR, object id). An internal entry is (MBR, child pointer), where the MBR covers every rectangle in that child. All leaves sit at the same depth. With a fanout of 100, four levels address 100 million objects.

Unlike a quadtree, an R-tree does not divide space; it groups objects. Sibling boxes can overlap, and some space is covered by no child at all.

Search

To find everything intersecting a window, recurse into every child whose MBR intersects it and report matching leaf entries. Heavy sibling overlap makes the search fan out into many subtrees, which is the main way R-tree performance degrades.

Nearest-neighbour search uses a priority queue ordered by the minimum distance from the query point to each MBR, popping nodes and entries in distance order. PostGIS exposes this as the <-> operator in ORDER BY.

Insert

Choose a leaf by descending from the root, at each level picking the child whose MBR needs the least enlargement to include the new rectangle (ties broken by smaller area). Add the entry and enlarge MBRs on the way back up. If the leaf overflows M entries, split it.

The split decides quality. Guttman's quadratic split seeds two groups with the pair of entries that would waste the most area together, then assigns the rest greedily (Guttman, 1984). The R\-tree chooses splits that minimise overlap and perimeter, and before splitting it reinserts the 30 percent of entries farthest from the node's centre. Forced reinsertion lets the tree reorganise as data arrives. It costs CPU, but in the paper's tests it raised disk accesses per insert by only about 4 percent, because fewer splits happen (Beckmann et al., 1990). Most engines use R\ heuristics.

Bulk loading

Building by repeated inserts gives a mediocre tree. For static or batch data, Sort-Tile-Recursive (STR) packing is better: sort entries by x centre, cut them into vertical slabs, sort each slab by y, and fill nodes completely. Repeat on the node boxes until one root remains. Packed trees have nearly 100 percent node utilisation and little overlap, and loading is a sort rather than millions of random page writes. Its authors measured up to 50 percent fewer disk accesses than Hilbert-curve packing on uniform or mildly skewed data, but about the same on highly skewed data (Leutenegger et al., 1997).

Postgres now does this kind of packing itself. CREATE INDEX on GiST uses a sorted build by default when the operator class provides a sortsupport function, and otherwise switches to a buffered build once the index outgrows effective_cache_size (Postgres docs). PostGIS added Hilbert-sorted builds in 3.2 and turned them on by default in 3.3 for Postgres 15 and later (PostGIS NEWS); see In the wild for why it took two releases.

Deletes shrink MBRs upward and reinsert the orphans of any node that underflows, which is expensive, so many systems tolerate underfill and rebuild periodically.

Down the stack

Layer 1The contract

The index promises a superset: every object whose bounding box intersects the query box is returned. It does not promise that the shapes intersect; the refine step does that. In PostGIS the index is crash-safe and transactional like any Postgres index, readers never block writers, and ORDER BY geom <-> point LIMIT k returns true nearest neighbours by walking the tree best-first (PostGIS workshop).

Layer 2The mechanism

PostGIS implements its R-tree on GiST, Postgres's generalised search tree. The 2D operator class stores each key as a BOX2DF: four 4-byte floats, 16 bytes, rounded outward so the float box always contains the true double-precision box. GiST calls a fixed set of support functions. Five are required: consistent (can this subtree match the query?), union (the parent box), penalty (how much a box grows if an entry is added, used to choose a subtree), picksplit (divide an overflowing page) and same. Optional ones include distance for KNN ordering and sortsupport for fast builds (Postgres docs). GiST is not PostGIS's only choice: it also supports SP-GiST, a space-partitioning quadtree or k-d tree, and BRIN, which stores one box per range of table blocks and is tiny but only works on spatially sorted, rarely updated tables (PostGIS docs).

SQLite's R*Tree module is a virtual table backed by three shadow tables: %_node holds node blobs, %_parent maps nodes to parents, and %_rowid maps rows to leaves. It also stores 32-bit float coordinates and rounds boxes outward, trading a few false positives for smaller nodes. The rounding has a catch: overlap queries never miss an entry, but a "contained within" query can drop an entry whose edge lies on the query's edge, so SQLite tells you to grow such query boxes by 0.000012 percent (SQLite docs).

Layer 3The machine

A Postgres page is 8 KB. An index tuple is an 8-byte header plus the 16-byte key, plus a 4-byte line pointer, so about 28 bytes, and a page holds roughly 250 entries at 90 percent fill. Reading a page from shared buffers costs well under a microsecond; from NVMe about 100 us; from a network disk often 1 ms or more. Inside a page, testing 250 boxes is 1,000 float comparisons, around a microsecond.

Writes cost more than they look. Every changed page is logged to the write-ahead log, and the first change to a page after a checkpoint writes the full 8 KB page image. An insert that splits a node touches the leaf, its new sibling, and the parent, so a bulk of random inserts right after a checkpoint can multiply WAL volume several times over.

Why it's built this way

  1. Storage is read in pages, so nodes are page-sized with high fanout to keep trees shallow.
  2. Shapes have extent and cannot be cut cleanly, so the tree groups objects and lets boxes overlap rather than partitioning space.
  3. Overlap makes searches fan out, so split and insert heuristics such as R\* fight it.
  4. Smaller keys mean more entries per page and fewer levels, so engines store 4-byte floats rounded outward and rely on the refine step for exactness.

Diagram

flowchart TD
    Q["Query window W"] --> R["Root node"]
    R --> C{"Child MBR intersects W?"}
    C -->|no| P["Prune subtree"]
    C -->|yes| N{"Leaf?"}
    N -->|no| C
    N -->|yes| E["Candidate entries"]
    E --> X["Exact geometry test"]
    X --> O["Results"]

Worked example

A property platform stores 150 million land-parcel polygons in PostGIS and serves map viewport queries at 3,000 QPS.

A 2D GiST entry is a 16-byte float box plus tuple header and line pointer, about 28 bytes, so an 8 KB page holds roughly 250 entries. That is 600,000 leaf pages, about 5 GB, in a tree 4 levels deep. The upper levels are about 2,400 pages, under 20 MB, which always stay in shared buffers, so a viewport query usually costs a handful of leaf reads.

A street-zoom viewport returns, say, 1,400 candidates by bounding box; the exact ST_Intersects check discards about 15 percent. Latency is 4 ms at p50 and 25 ms at p99, dominated by fetching heap rows for the geometry check.

Two things hurt. First, a handful of huge polygons (national parks, a coastline) have MBRs covering vast areas, so they appear as candidates in thousands of queries and bloat internal-node boxes. Splitting them with ST_Subdivide into pieces of at most 256 vertices, its default (PostGIS docs), cut p99 by half in this scenario. Second, a nightly import of 2 million changed parcels via row-by-row inserts degraded the tree over months. Building a fresh index concurrently and swapping it restored the original query times.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
R-tree / R\*-tree (PostGIS GiST, SQLite)Indexes arbitrary shapes, disk-based, KNN supportOverlap degrades search, inserts costlier than B-treePolygons, lines, or mixed geometry in a database
STR-packed static R-treeMinimal overlap, compact, fast to buildRebuild needed to change dataRead-only or batch-refreshed datasets
QuadtreeSimple, no overlap, adapts to densityShapes span many cells, mostly in memoryPoints in a custom in-memory service
Geohash / S2 / H3 cells in a B-treeWorks in any key-value store, easy to shardShapes need many cells to cover, approximateDistributed stores without spatial indexing

Pitfalls in production

Leadership lens

Check yourself

  1. Why can an R-tree search visit more than one child at the same level, when a B-tree lookup visits exactly one?

    Show answer

    Sibling MBRs can overlap, so a query window may intersect several of them, and each must be explored because any could contain matches.

  2. What does forced reinsertion in the R\*-tree buy, and what does it cost?

    Show answer

    Reinserting the outermost entries before splitting lets them find better homes, reducing overlap and improving query speed; the cost is extra work and page writes on inserts.

  3. Why does STR bulk loading produce a better tree than inserting the same data one row at a time?

    Show answer

    It sorts all entries spatially first and fills nodes completely in tile order, so nodes are full, groups are tight, and overlap is minimal; incremental inserts make local greedy choices that cannot be undone.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

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