Introduction

Open a map app and search "coffee near me." Within milliseconds it returns a handful of cafรฉs from a database of millions of places. How?

A naรฏve approach would scan every location and check its distance. For small datasets that works fine โ€” but geography datasets contain billions of points, polygons, road segments, and building footprints. Scanning them all for every query would be catastrophically slow.

R-trees, introduced by Antonin Guttman in 1984, solved this with one elegant idea: group nearby objects into bounding rectangles, then group those rectangles into larger ones, building a hierarchy. A spatial query then descends the tree, pruning entire branches the moment their bounding box doesn't overlap the query region. Most of the index is never touched.

The key insight is that spatial data has locality โ€” nearby things tend to stay nearby โ€” and a good index exploits that locality to skip work. R-trees are the workhorse behind PostGIS, Oracle Spatial, SQLite's SpatiaLite, and virtually every GIS database on the planet.

Try It

Below is a small R-tree holding 16 rectangles (shown in blue). Click Draw query and drag on the canvas to define a query region (shown in orange). The tree will highlight the bounding boxes it inspects (yellow) and the rectangles it actually returns (green). Click Reset to start over.

<div class="toolbar">
  <button id="btnDraw" type="button">Draw query</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
  <span id="info" class="info">Click "Draw query", then drag on the canvas.</span>
</div>
<canvas id="canvas" width="560" height="360"></canvas>
<div id="results" class="results"></div>

* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; background: #fff; }
.toolbar { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.info { font-size: .85rem; color: #555; flex: 1; min-width: 160px; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; display: block;
         cursor: crosshair; touch-action: none; width: 100%; max-width: 560px; }
.results { margin-top: .5rem; font-size: .85rem; color: #333; min-height: 1.3em; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// R-Tree demo: a tiny 2-level R-tree of 16 axis-aligned rectangles.
// The user draws a query rectangle; the tree highlights visited bounding boxes
// and returned (intersecting) leaf rectangles.

const W = 560, H = 360;
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

// โ”€โ”€ Tree data โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// 16 leaf rectangles [x, y, w, h] (in canvas coords 0..560 x 0..360)
const LEAVES = [
  [30,  20,  60, 40],  [110, 30,  50, 35], [30,  90,  55, 45], [100, 80,  45, 50],
  [180, 15,  65, 40],  [270, 25,  50, 45], [195, 80,  60, 40], [280, 75,  55, 45],
  [360, 20,  50, 40],  [430, 15,  60, 45], [370, 80,  55, 40], [450, 75,  50, 45],
  [50,  200, 55, 45],  [130, 210, 60, 40], [55,  270, 50, 40], [140, 275, 55, 45]
];

// Build bounding box of an array of [x,y,w,h]
function bbox(rects) {
  let minX=Infinity, minY=Infinity, maxX=-Infinity, maxY=-Infinity;
  for (const [x,y,w,h] of rects) {
    minX=Math.min(minX,x); minY=Math.min(minY,y);
    maxX=Math.max(maxX,x+w); maxY=Math.max(maxY,y+h);
  }
  return [minX, minY, maxX-minX, maxY-minY];
}

// Group leaves into 4 clusters (the internal nodes of our 2-level tree)
const CLUSTERS = [
  { leaves: [0,1,2,3]   },
  { leaves: [4,5,6,7]   },
  { leaves: [8,9,10,11] },
  { leaves: [12,13,14,15] }
];
// Compute cluster bounding boxes
for (const c of CLUSTERS) c.bb = bbox(c.leaves.map(i => LEAVES[i]));
// Root bounding box
const ROOT_BB = bbox(CLUSTERS.map(c => [c.bb[0], c.bb[1], c.bb[2], c.bb[3]]));

// โ”€โ”€ Intersection test โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function intersects([ax,ay,aw,ah], [bx,by,bw,bh]) {
  return ax < bx+bw && ax+aw > bx && ay < by+bh && ay+ah > by;
}

// โ”€โ”€ Drawing โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function draw(query, visitedBBs, hitLeaves) {
  const scale = canvas.clientWidth / W;
  ctx.clearRect(0, 0, W, H);

  // Draw all leaf rectangles
  for (let i = 0; i < LEAVES.length; i++) {
    const [x,y,w,h] = LEAVES[i];
    const isHit = hitLeaves && hitLeaves.has(i);
    ctx.fillStyle = isHit ? 'rgba(34,197,94,.35)' : 'rgba(59,130,246,.18)';
    ctx.strokeStyle = isHit ? '#16a34a' : '#2563eb';
    ctx.lineWidth = isHit ? 2 : 1.2;
    ctx.beginPath(); ctx.rect(x,y,w,h); ctx.fill(); ctx.stroke();
  }

  // Draw visited cluster bounding boxes
  if (visitedBBs) {
    for (const bb of visitedBBs) {
      ctx.strokeStyle = '#eab308';
      ctx.lineWidth = 1.8;
      ctx.setLineDash([5,3]);
      ctx.beginPath(); ctx.rect(...bb); ctx.stroke();
      ctx.setLineDash([]);
    }
  }

  // Draw query rectangle
  if (query) {
    ctx.fillStyle = 'rgba(249,115,22,.15)';
    ctx.strokeStyle = '#ea580c';
    ctx.lineWidth = 2;
    ctx.beginPath(); ctx.rect(...query); ctx.fill(); ctx.stroke();
  }
}

// โ”€โ”€ R-tree query โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function queryTree(q) {
  const visitedBBs = [];
  const hitLeaves = new Set();
  let inspected = 0;
  for (const c of CLUSTERS) {
    if (intersects(q, c.bb)) {
      visitedBBs.push(c.bb);
      inspected++;
      for (const idx of c.leaves) {
        if (intersects(q, LEAVES[idx])) hitLeaves.add(idx);
      }
    }
  }
  return { visitedBBs, hitLeaves, inspected };
}

// โ”€โ”€ Interaction โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
let drawing = false, startX = 0, startY = 0, currentQuery = null;
let mode = 'idle'; // 'idle' | 'drawing' | 'done'

function canvasRect() { return canvas.getBoundingClientRect(); }
function toCanvasCoords(clientX, clientY) {
  const r = canvasRect();
  const scaleX = W / r.width, scaleY = H / r.height;
  return [(clientX - r.left) * scaleX, (clientY - r.top) * scaleY];
}
function normRect(x1,y1,x2,y2) {
  return [Math.min(x1,x2), Math.min(y1,y2), Math.abs(x2-x1), Math.abs(y2-y1)];
}

function setInfo(msg) { document.getElementById('info').textContent = msg; }
function setResults(msg) { document.getElementById('results').textContent = msg; }

document.getElementById('btnDraw').addEventListener('click', () => {
  mode = 'drawing';
  currentQuery = null;
  draw(null, null, null);
  setInfo('Drag on the canvas to draw a query rectangle.');
  setResults('');
  document.getElementById('btnDraw').disabled = true;
});

document.getElementById('btnReset').addEventListener('click', () => {
  mode = 'idle';
  currentQuery = null;
  draw(null, null, null);
  setInfo('Click "Draw query", then drag on the canvas.');
  setResults('');
  document.getElementById('btnDraw').disabled = false;
});

canvas.addEventListener('mousedown', e => {
  if (mode !== 'drawing') return;
  drawing = true;
  [startX, startY] = toCanvasCoords(e.clientX, e.clientY);
});
canvas.addEventListener('mousemove', e => {
  if (!drawing) return;
  const [cx, cy] = toCanvasCoords(e.clientX, e.clientY);
  const q = normRect(startX, startY, cx, cy);
  draw(q, null, null);
});
canvas.addEventListener('mouseup', e => {
  if (!drawing) return;
  drawing = false;
  const [cx, cy] = toCanvasCoords(e.clientX, e.clientY);
  const q = normRect(startX, startY, cx, cy);
  if (q[2] < 5 || q[3] < 5) { setInfo('Drag a larger rectangle.'); draw(null,null,null); return; }
  currentQuery = q;
  mode = 'done';
  const { visitedBBs, hitLeaves, inspected } = queryTree(q);
  draw(q, visitedBBs, hitLeaves);
  const skipped = CLUSTERS.length - inspected;
  setInfo('Query complete.');
  setResults(
    fmt('Visited %inspected% of %length% bounding boxes (skipped %skipped%). Found %size% of %length2% rectangles.', { inspected: inspected, length: CLUSTERS.length, skipped: skipped, size: hitLeaves.size, length2: LEAVES.length })
  );
  document.getElementById('btnDraw').disabled = false;
});

// Touch support
canvas.addEventListener('touchstart', e => { e.preventDefault();
  if (mode !== 'drawing') return;
  drawing = true;
  [startX, startY] = toCanvasCoords(e.touches[0].clientX, e.touches[0].clientY);
}, { passive: false });
canvas.addEventListener('touchmove', e => { e.preventDefault();
  if (!drawing) return;
  const [cx, cy] = toCanvasCoords(e.touches[0].clientX, e.touches[0].clientY);
  draw(normRect(startX, startY, cx, cy), null, null);
}, { passive: false });
canvas.addEventListener('touchend', e => { e.preventDefault();
  if (!drawing) return;
  drawing = false;
  const t = e.changedTouches[0];
  const [cx, cy] = toCanvasCoords(t.clientX, t.clientY);
  const q = normRect(startX, startY, cx, cy);
  if (q[2] < 5 || q[3] < 5) return;
  currentQuery = q; mode = 'done';
  const { visitedBBs, hitLeaves, inspected } = queryTree(q);
  draw(q, visitedBBs, hitLeaves);
  const skipped = CLUSTERS.length - inspected;
  setResults(fmt('Visited %inspected% of %length% bounding boxes (skipped %skipped%). Found %size% of %length2% rectangles.', { inspected: inspected, length: CLUSTERS.length, skipped: skipped, size: hitLeaves.size, length2: LEAVES.length }));
  document.getElementById('btnDraw').disabled = false;
}, { passive: false });

// Initial render
draw(null, null, null);
setInfo('Click "Draw query", then drag on the canvas.');

// โ”€โ”€ Node-verifiable logic (run in browser console or node) โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// Cluster bboxes: 0=[30,20,130,115], 1=[180,15,155,105], 2=[360,15,140,105], 3=[50,200,145,120]
// Verify: a query covering only cluster 0's area visits exactly 1 bounding box / 4 leaves.
const testQ = [20, 15, 140, 130]; // right=160 < 180 (cluster 1 starts at 180)
const testR = queryTree(testQ);
console.assert(testR.inspected === 1, fmt('Should visit 1 cluster, got %inspected%', { inspected: testR.inspected }));
console.assert(testR.hitLeaves.size === 4, fmt('Should hit 4 leaves, got %size%', { size: testR.hitLeaves.size }));
// A query covering nothing should visit 0 bounding boxes
const emptyQ = [400, 280, 50, 50]; // bottom-right corner, no leaves there
const emptyR = queryTree(emptyQ);
console.assert(emptyR.hitLeaves.size === 0, 'Empty query should hit 0 leaves');
console.log('R-tree demo assertions passed.');
Result
Console

Notice how the tree skips entire clusters the moment their bounding box misses the query region. With 16 rectangles the saving is modest; with millions of shapes the pruning makes the difference between milliseconds and minutes.

The Real Complexity

R-trees are a solved engineering problem โ€” Guttman's 1984 paper described the complete structure โ€” but their theoretical analysis is subtler than it looks.

  • Query time: O(logโกn)O(\log n) average. If the bounding boxes at each level overlap little, a region query visits O(logโกn)O(\log n) nodes, just like a balanced binary search tree. Each node holds between m and M children (typical values: m=2, M=50), so the tree height is โŒˆlog_M nโŒ‰.
  • Worst case: O(n)O(n). In degenerate cases โ€” long thin rectangles, pathological insertion order โ€” bounding boxes at the same level overlap heavily. A query that touches one box may then need to descend into all of them, collapsing to a linear scan.
  • Insertion and deletion: O(logโกn)O(\log n) amortized. Inserting a rectangle chooses the child whose bounding box needs the least enlargement, then adjusts bounding boxes up the path to the root. Deletion finds the entry, removes it, and re-inserts orphaned entries.
  • The overlap problem. Minimising overlap between sibling bounding boxes is the central challenge of R-tree design. The original algorithm uses greedy heuristics; later variants โ€” R*-tree (Beckmann et al., 1990) and Hilbert R-tree โ€” use more aggressive rebalancing and space-filling curve ordering to keep overlap low.
  • Comparison to k-d trees. K-d trees partition space with axis-aligned hyperplanes rather than bounding boxes, which avoids overlap but handles extended objects (polygons, segments) awkwardly. R-trees store any rectangle natively.

In practice, a well-tuned R*-tree on geographic data achieves query performance close to the theoretical O(logโกn)O(\log n) bound, which is why it became the default spatial index in virtually every serious database.

Where It Matters

Any system that needs to answer "what's near here?" efficiently leans on R-trees or their descendants:

  • Geographic information systems (GIS): PostGIS, Oracle Spatial, and SpatiaLite index road networks, land parcels, and satellite imagery tiles using R-trees. Spatial joins ("which roads cross this flood zone?") become logarithmic instead of quadratic.
  • Map and navigation apps: The tile selection and point-of-interest lookup in applications like Google Maps, OpenStreetMap, and Mapbox all rely on spatial indexes. Your "nearby restaurants" result comes back in under 100 ms for exactly this reason.
  • Ride-sharing dispatch: Platforms like Uber and Lyft maintain a live spatial index of driver locations. Matching a rider to the nearest available driver is a nearest-neighbour query on a structure that updates thousands of times per second.
  • Game engines and collision detection: Unity, Unreal Engine, and most physics engines use a variant called a dynamic AABB tree (axis-aligned bounding-box tree) โ€” essentially a real-time R-tree โ€” to quickly find which objects might be colliding before running expensive physics calculations.
  • Computational biology: Protein structure databases index atoms in 3-D space with R-trees to find residues within a given distance of a query point.
  • Astronomy: Star catalogs and sky-survey pipelines use R-trees to answer queries like "which known objects fall inside this telescope field of view?"

Learn how an R-tree prunes a spatial search and you understand the index inside nearest-neighbor search algorithms, spatial joins, and real-time collision pipelines alike.

Conclusion

R-trees rest on an almost embarrassingly simple idea: wrap groups of nearby shapes in bounding boxes, nest those boxes in bigger ones, and you get a hierarchy that lets a query skip huge swathes of the data in a single comparison.

Guttman published the original paper in 1984, and four decades later the R*-tree variant is still the default spatial index in every serious database. That longevity says something: the bounding-box hierarchy maps so naturally onto how spatial data is organised in the real world that no fundamentally different structure has displaced it.

The next time a map shows you coffee shops in your neighbourhood before you finish typing, an R-tree quietly pruned away millions of irrelevant locations in the background โ€” and you never had to wait for the linear scan.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/r-tree/Content licensed under CC BY-NC 4.0.