C++UCS301
Spatial Data StructuresC++17

R-Trees

R-trees index spatial objects using nested minimum bounding rectangles and are widely used in GIS and spatial databases.

What to understand

  • Bounding rectangles
  • Overlap-aware search
  • Node splitting
  • Range and nearest-neighbour queries

Remember this

  1. 1R-trees index objects with extent
  2. 2Overlapping rectangles may require multiple search paths
  3. 3R*-trees improve split and reinsertion choices

Detailed notes

An R-tree groups spatial objects into minimum bounding rectangles. Internal rectangles cover all descendants, so a query descends only into rectangles that overlap its region—though overlap may require multiple paths.

Like B-trees, R-trees are balanced and page-oriented. Insertion chooses a child requiring small enlargement; overflow triggers a split whose quality strongly affects future overlap and query cost.

How it works

  1. 1Represent every object by its bounding rectangle.
  2. 2Choose a subtree using enlargement and area criteria.
  3. 3Expand ancestor rectangles after insertion.
  4. 4Split overflowing nodes while minimising overlap and dead space.

Where it is used

  • GIS and spatial databases
  • Nearby-facility and map-feature queries
  • Urban planning, land parcels, and service zones

Common mistakes

  • Assuming rectangles never overlap
  • Treating an R-tree as a point-only quadtree
  • Ignoring coordinate systems and geographic distance distortion

Implementation perspective

This is primarily a conceptual or selection topic. Use the linked implementation topics in this section to see the invariant expressed in C++.

Exam & viva

Open a prompt when you are ready to check your answer.