Two of this site's other Spatial entries — the KD-tree and the Quadtree — both index individual points and both partition the plane into regions that never overlap: a KD-tree cuts at the data's own median, a quadtree cuts at a box's fixed center, but either way, two sibling regions never share any territory. A lot of real spatial data isn't points at all, though — buildings on a map, sprite bounding boxes in a game, the footprint of a geometric feature. An R-tree indexes rectangles directly, and it builds its tree a different way entirely: instead of partitioning space top-down, it groups nearby rectangles bottom-up into a parent rectangle just big enough to contain them — a minimum bounding rectangle, or MBR. Nothing stops two sibling MBRs from overlapping, because nothing partitions space to prevent it.
That overlap is a real structural tradeoff, not a bug, but it has a real cost this page measures directly: a KD-tree or quadtree can prune a whole subtree the instant its region misses the query rectangle, guaranteed. An R-tree's subtrees can share territory, so a query can be forced to descend into more than one sibling even when only one of them actually holds a match — the other gets checked for nothing. The demo below hits exactly this case on its very first range query.
Thirteen rectangles, capacity 3 entries per node. Press Step or Run to insert them one at a time: watch a leaf's own bounding box grow to cover each new rectangle, and watch it split into two new leaves — by Guttman's quadratic split, not down the middle — the moment a fourth rectangle would land in an already-full one. Once every rectangle is placed, the demo switches to a range query for the small highlighted rectangle: watch it walk the tree, skip an entire dashed internal box (and everything under it) in one check when its MBR misses the query outright, but also — the point of this page — walk all the way into a solid leaf box whose MBR technically overlaps the query, only to find nothing inside it.
Inserting a rectangle starts at the root and calls ChooseLeaf: at every internal node, walk into whichever child's MBR would need to grow the least to include the new rectangle (ties go to the smaller MBR). This is a greedy, local decision at each level, not a search for the globally best leaf — it's what makes descent itself cheap, and it's also exactly why sibling MBRs end up overlapping at all: two different rectangles can each look like the "least enlargement" choice from two different parents, even when their final positions end up close together in space. Once ChooseLeaf reaches a leaf, the rectangle is simply appended to its entry list. If that pushes the leaf over capacity, it splits: Guttman's quadratic split first picks the two entries that would waste the most area if forced into one group (the "worst pair" — as far apart, relatively, as any two entries in the node), seeds two new groups with them, then repeatedly assigns whichever remaining entry has the *most lopsided* preference between the two groups, breaking ties by which group would grow less. A split can cascade: if a leaf's split leaves its parent internal node over capacity too, that parent splits the same way, all the way up to a possible new root.
A range query walks the tree checking one thing at every node: does this node's own MBR overlap the query rectangle at all? If not, the whole subtree under it — no matter how many rectangles it holds — is skipped without being read, the same one-check pruning a KD-tree or quadtree's boundary check gives. The difference only shows up when the MBR does overlap: for a quadtree, that guarantees real work waits inside (its regions are disjoint, so no sibling could have already claimed that territory). For an R-tree, an overlapping MBR is only a maybe — the actual rectangles inside might all sit in the non-overlapping part of that MBR, meaning the visit was for nothing. That's not a corner case; it's the direct, structural cost of building bottom-up instead of partitioning top-down, and it's what the Pitfalls section below measures with real numbers.
function makeNode(leaf) {
return { leaf, entries: [], rect: null };
}
function area(r) { return r.w * r.h; }
function rectOf(a, b) { // smallest rectangle covering both a and b
const minX = Math.min(a.x, b.x), minY = Math.min(a.y, b.y);
const maxX = Math.max(a.x + a.w, b.x + b.w), maxY = Math.max(a.y + a.h, b.y + b.h);
return { x: minX, y: minY, w: maxX - minX, h: maxY - minY };
}
function enlargement(r, add) { return area(rectOf(r, add)) - area(r); }
function overlaps(a, b) {
return !(a.x > b.x + b.w || a.x + a.w < b.x || a.y > b.y + b.h || a.y + a.h < b.y);
}
function updateRect(node) {
node.rect = node.entries.reduce((acc, e) => acc ? rectOf(acc, e.rect) : { ...e.rect }, null);
}
// ChooseLeaf: descend greedily -- at each level, enter whichever child's MBR
// would need to grow the least to include the new rectangle (ties: smaller MBR wins).
function chooseLeafPath(root, rect) {
const path = [root];
let n = root;
while (!n.leaf) {
let best = null, bestEnlarge = Infinity, bestArea = Infinity;
for (const e of n.entries) {
const enl = enlargement(e.rect, rect);
const a = area(e.rect);
if (enl < bestEnlarge || (enl === bestEnlarge && a < bestArea)) {
best = e; bestEnlarge = enl; bestArea = a;
}
}
n = best.child;
path.push(n);
}
return path;
}
// Guttman's quadratic split: seed two groups with the pair that would waste the
// most area if forced together, then greedily assign the rest by preference.
function quadraticSplit(entries, minEntries) {
let seed1 = 0, seed2 = 1, worst = -Infinity;
for (let i = 0; i < entries.length; i++) {
for (let j = i + 1; j < entries.length; j++) {
const d = area(rectOf(entries[i].rect, entries[j].rect)) - area(entries[i].rect) - area(entries[j].rect);
if (d > worst) { worst = d; seed1 = i; seed2 = j; }
}
}
const groupA = [entries[seed1]], groupB = [entries[seed2]];
let rectA = { ...entries[seed1].rect }, rectB = { ...entries[seed2].rect };
const remaining = entries.filter((_, i) => i !== seed1 && i !== seed2);
while (remaining.length) {
if (groupA.length + remaining.length === minEntries) { groupA.push(...remaining); break; }
if (groupB.length + remaining.length === minEntries) { groupB.push(...remaining); break; }
let bestIdx = -1, bestDiff = -Infinity, bestEnlA = 0, bestEnlB = 0;
for (let i = 0; i < remaining.length; i++) {
const enlA = enlargement(rectA, remaining[i].rect);
const enlB = enlargement(rectB, remaining[i].rect);
const diff = Math.abs(enlA - enlB);
if (diff > bestDiff) { bestDiff = diff; bestIdx = i; bestEnlA = enlA; bestEnlB = enlB; }
}
const entry = remaining.splice(bestIdx, 1)[0];
const toA = bestEnlA !== bestEnlB ? bestEnlA < bestEnlB
: area(rectA) !== area(rectB) ? area(rectA) < area(rectB)
: groupA.length <= groupB.length;
if (toA) { groupA.push(entry); rectA = rectOf(rectA, entry.rect); }
else { groupB.push(entry); rectB = rectOf(rectB, entry.rect); }
}
return [groupA, groupB];
}
function splitNode(node, minEntries) {
const [groupA, groupB] = quadraticSplit(node.entries, minEntries);
const a = makeNode(node.leaf); a.entries = groupA; updateRect(a);
const b = makeNode(node.leaf); b.entries = groupB; updateRect(b);
return [a, b];
}
function insert(root, rect, data, M = 4, m = 2) {
const path = chooseLeafPath(root, rect);
const leaf = path[path.length - 1];
leaf.entries.push({ rect, data });
updateRect(leaf);
let split = leaf.entries.length > M ? splitNode(leaf, m) : null;
let child = leaf;
for (let i = path.length - 2; i >= 0; i--) {
const parent = path[i];
const idx = parent.entries.findIndex(e => e.child === child);
if (split) {
const [a, b] = split;
parent.entries.splice(idx, 1, { rect: a.rect, child: a }, { rect: b.rect, child: b });
} else {
parent.entries[idx].rect = child.rect;
}
updateRect(parent);
split = parent.entries.length > M ? splitNode(parent, m) : null;
child = parent;
}
if (split) {
const [a, b] = split;
const newRoot = makeNode(false);
newRoot.entries = [{ rect: a.rect, child: a }, { rect: b.rect, child: b }];
updateRect(newRoot);
return newRoot;
}
return root;
}
function rangeQuery(node, range, found = []) {
if (!node.rect || !overlaps(node.rect, range)) return found; // subtree pruned, unread
if (node.leaf) {
for (const e of node.entries) if (overlaps(e.rect, range)) found.push(e.data);
} else {
for (const e of node.entries) rangeQuery(e.child, range, found);
}
return found;
}MBR overlap is not rare, and it costs real, measurable work. The demo above's own
13-rectangle tree has exactly one pair of sibling leaves whose MBRs overlap, and its range query walks
straight into the cost: the query rectangle is fully inside the overlap between two leaves — one
holding H and G, the other holding L and D. Both
get visited because both MBRs genuinely overlap the query. Only the first one has a real match
(G); the second is checked for nothing — none of its own rectangles happen to sit in the
sliver of space its MBR shares with the query. A separate, larger stress run (deterministic seed, 40
rectangles, same capacity 3) makes the same shape concrete at scale: 17 leaves, 7 of the 136
possible sibling-leaf-MBR pairs actually overlap — about 5% of all pairs, from ordinary random
placement, no adversarial input required. Neither KD-tree nor Quadtree can produce this failure mode
at all; their regions are disjoint by construction.
Despite that, range queries are still correct. Overlap costs extra visits, it never costs correctness — pruning only ever throws away a subtree once its MBR is proven not to overlap the query, never based on a guess. Checked against a brute-force linear scan across 30,000 query trials (3,000 trees of 1–80 random rectangles each, 10 random query rectangles per tree): zero mismatches.
The exact failure that broke Quadtree doesn't happen here — for a genuinely different reason, not because this implementation is more careful. Quadtree's own Pitfalls section found that 500 duplicate-coordinate points made its geometric-center split recurse forever, silently losing every point to 64-bit float underflow. Feeding this page's R-tree the same stress case — 500 zero-size rectangles at the exact same coordinate — doesn't reproduce that bug: quadratic split's seed-and-assign logic never depends on the entries actually being geometrically separable, so it just keeps splitting group sizes evenly regardless. All 500 survive, and the resulting tree is genuinely balanced: depth 8, 250 leaves holding exactly 2 entries each — the minimum allowed — even though every single rectangle is byte-for-byte identical. The two structures fail (or don't) along completely different axes: a quadtree's split is blind to the data, so identical data breaks its termination; an R-tree's split is driven entirely by the data's own pairwise costs, so identical data just produces identical, arbitrary-but-stable costs and an even split — no crash, but also no clustering signal at all to work with.
Anywhere the indexed objects have real extent, not just a location: spatial databases (PostGIS's GiST index, Oracle Spatial) use R-tree variants to answer "which parcels intersect this map view," game engines use them for broad-phase collision culling over hitboxes rather than single points, and GIS software indexes country/building/road-segment bounding boxes the same way. The common thread is data that's naturally rectangular (or has a cheap rectangular bounding approximation) rather than data that's naturally a single coordinate — the case a KD-tree or quadtree already covers well.
Insert: O(log n) average — ChooseLeaf descends one level per tree
level with an O(M) scan at each, and a quadratic split costs O(M²) to pick
seeds, but M is a small fixed constant (3 in the demo), so both are effectively O(1)
per level. Range query: O(log n + k) for k results under
typical data, same shape as Quadtree — but unlike
Quadtree or a KD-tree, there's no guarantee against
overlap forcing extra visits, so worst case degrades toward O(n) the more sibling MBRs
overlap, exactly the cost measured in the Pitfalls section above. Space:
O(n) rectangles stored total, plus one node object per split actually performed.
This site's guide, Choosing a Spatial Structure, compares this entry against the other seven Spatial entries that share the same "index points, query later" question side by side.