Paper: R-Trees: A Dynamic Index Structure for Spatial Searching — Antonin Guttman, SIGMOD 1984.

The R-tree is a height-balanced index structure for spatial data: objects that occupy non-zero area in multi-dimensional space (rectangles, polygons, regions). It extends B-tree ideas to multi-dimensional range search, where traditional 1D ordered indexes fail.

# Background: Why B-trees Don’t Work for Spatial Data

A B-tree orders records by a single scalar key. This gives efficient point and range queries in one dimension. Spatial data breaks both assumptions:

1. Objects have extent, not just a location — a county boundary or a circuit component occupies a region. A single point cannot represent it.

2. No total ordering exists in 2D+ — there is no natural way to linearise 2D rectangles such that nearby rectangles in space are nearby in the ordering. Any linearisation (e.g. Morton curve) loses spatial proximity for some configurations.

Hash tables are also ruled out: they support only exact match, not range/overlap search.

# Core Structure

An R-tree is a height-balanced tree where each node stores between $m$ and $M$ entries ($m \leq \frac{M}{2}$). The root has at least 2 children unless it is a leaf.

Leaf nodes store index records of the form $(I, \text{tuple-id})$:

• $\text{tuple-id}$: pointer to the actual data tuple.
• $I = [I_0, I_1, \ldots, I_{n-1}]$: the minimum bounding rectangle (MBR) of the spatial object, one closed interval $[a, b]$ per dimension.

Non-leaf nodes store entries of the form $(I, \text{child-pointer})$:

• $I$: the MBR that tightly encloses all rectangles in the child node.
• $\text{child-pointer}$: pointer to the child node.

         [R1 | R2]                     ← root: MBRs covering subtrees
        /          \
  [R3|R4|R5]    [R6|R7]                ← internal nodes
  /   |   \      /    \
[R8..] [R11..] [R13..] [R15..] [R17..] ← leaves → data tuples

The critical difference from a B-tree: bounding rectangles at the same level can overlap. A search rectangle may overlap multiple subtrees, all of which must be visited. Unlike B-trees, worst-case search is not $O(\log N)$ — but in practice, good splits minimise overlap and keep search efficient.

# Searching

Algorithm Search: given search rectangle $S$, find all records whose MBR overlaps $S$.

• At each non-leaf node: for every entry $E$, if $E.I$ overlaps $S$, recurse into $E.\text{child}$.
• At each leaf node: for every entry $E$, if $E.I$ overlaps $S$, return $E.\text{tuple-id}$ as a result.

Because bounding rectangles can overlap, the search may fan out into multiple subtrees. The quality of the tree (how tightly MBRs fit, how little they overlap siblings) directly determines how many subtrees are pruned.

# Insertion

Algorithm Insert: insert a new entry $E$ into the tree.

1. ChooseLeaf: descend from the root to a leaf. At each non-leaf node, choose the child entry whose MBR requires the least enlargement to include $E.I$. Break ties by choosing the entry with the smallest existing area.

2. Add to leaf: if the leaf has room, install $E$. Otherwise, invoke SplitNode to split the leaf into two nodes $L$ and $LL$, distributing the $M+1$ entries between them.

3. AdjustTree: ascend from the leaf to the root. At each level, tighten the parent’s MBR entry to cover the updated child. If a split occurred below, add the new sibling node (potentially causing another split at the current level).

4. If the root is split, create a new root with the two halves as children.

# Deletion

Algorithm Delete: remove entry $E$.

1. FindLeaf: descend the tree to find the leaf $L$ containing $E$ (checking MBR overlap at each internal node).

2. Remove $E$ from $L$.

3. CondenseTree: if $L$ has fewer than $m$ entries, eliminate the node and re-insert all its orphaned entries back into the tree at the appropriate level. Propagate upward, eliminating under-full nodes and adjusting MBRs.

# Node Splitting

The node split algorithm is the most important design choice — it determines the quality of the resulting MBRs and therefore search performance. The goal is to minimise the total area of the two resulting MBRs (smaller MBRs = less overlap with future queries = better pruning).

Guttman presents three algorithms:

# Exhaustive Split — $O(2^M)$

Try all $2^{M-1}$ ways to partition $M+1$ entries into two groups of at least $m$. Pick the partition minimising total MBR area. Optimal but exponential — impractical for $M > 10$.

# Quadratic Split — $O(M^2)$

A greedy approximation. Not guaranteed to find the minimum-area split.

PickSeeds: find the two entries that would waste the most area if placed together. For each pair $(E_1, E_2)$, compute $d = \text{area}(\text{MBR}(E_1, E_2)) - \text{area}(E_1.I) - \text{area}(E_2.I)$. Pick the pair with largest $d$ — they are the “most separated” seeds.

PickNext (repeat until all entries assigned):

1. For each unassigned entry, compute $d_1$ = area increase to add it to group 1, $d_2$ = same for group 2.

2. Assign the entry with the greatest $|d_1 - d_2|$ to the group with smaller increase. (If one group must receive all remaining entries to reach $m$, assign them all.)

# Linear Split — $O(M)$

Uses a cheaper seed selection; PickNext just picks any remaining entry and assigns it to the group needing less enlargement.

LinearPickSeeds: along each dimension, find the entry with the highest low side and the entry with the lowest high side. Normalise the separation by the total extent of all entries along that dimension. Choose the pair with the greatest normalised separation across any dimension.

# Why Overlap is the Enemy

The fundamental tension in R-tree design is minimising MBR overlap at each level. Consider two sibling nodes with large, heavily overlapping MBRs:

Bad split:          Good split:
┌──────────┐        ┌────┐  ┌────┐
│ ┌──────┐ │        │    │  │    │
│ │      │ │        │    │  │    │
│ └──────┘ │        └────┘  └────┘
└──────────┘
(MBRs overlap → both subtrees visited on most searches)

With a bad split, a search rectangle that touches the overlap region must descend into both subtrees. A good split keeps MBRs tight and disjoint, allowing one subtree to be pruned entirely.

This is why ChooseLeaf picks the child needing least MBR enlargement: it tries to insert each new object under the subtree already closest to it spatially, keeping MBRs small.

# Performance Results

Tested on VLSI circuit layout data (the RISC-II chip’s CENTRAL cell: 1057 rectangles in 2D) and larger synthetic datasets up to 4559 rectangles. Implemented in C on a Vax 11/780.

Insertion cost (Figure 4.2): exhaustive split grows exponentially with page size (too many combinations to try); linear and quadratic are nearly flat. Linear is fastest.

Search performance (Figures 4.4–4.5): all three split algorithms produce nearly identical search quality — pages touched per qualifying record and CPU cost differ by at most 10%. Search is insensitive to split algorithm choice.

Deletion cost (Figure 4.3): dominated by tree height (re-insertions), not split algorithm.

Storage overhead (Figure 4.6): ~40 bytes per item for linear split with $m=2$, $M=50$ (1024-byte pages). Index nodes are denser than data nodes, so space is dominated by leaf nodes.

Recommended configuration: page size 1024 bytes ($M \approx 50$), $m = M/2$ or $M/3$. Linear split. This gives good performance with insert cost nearly independent of tree size.

# Key Takeaways

The R-tree is the standard foundation for spatial indexes in databases (PostGIS, Oracle Spatial, SQLite R*Tree). Later variants (R*-tree, R+-tree) improve on the splitting and insertion heuristics but keep the same core structure.