Overview
An R-Tree groups nearby spatial objects into minimum bounding rectangles, enabling efficient overlap and range queries.
ExtendedSource checked
R-Tree
Indexes rectangles or spatial objects with nested bounding boxes.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Advanced
- Family
- Spatial Index
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
Core Concepts
bounding rectanglespatial hierarchyoverlap querynode split
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(log n)
Average
O(log n) average query
Worst
O(n)
Space
O(n)
When to Use
- Use when objects have extents such as rectangles or polygons and overlap queries are common.
- Use when gIS indexes is a central requirement.
When Not to Use
- Avoid when points lie on a fixed grid where a simpler grid or quadtree works better.
- Avoid when a simpler array, map, or list already meets the access pattern.
What It Does
- Stores bounding rectangles
- Groups nearby objects hierarchically
- Queries overlapping branches
Use Cases
- GIS indexes
- Database spatial queries
- Bounding-box search
Inputs
- Rectangles or spatial objects
Outputs
- Hierarchical bounding-box index
Key Formulas (1)
Box enlargement
enlargement = area(union(box, itembox)) − area(box)
enlargement = area(union(box, item_box)) - area(box)Chooses an insertion child by added bounding-box area.
Pseudocode
- 1.Insert an object into the child requiring least bounding-box enlargement
- 2.Split overflowing nodes
- 3.Update ancestor bounding boxes
- 4.Query by visiting boxes that overlap the search region
Canonical Example
- Input
- query rectangle overlaps two parent boxes
- Output
- visit only those two branches
- Explanation
- The tree prunes spatial groups whose bounding boxes do not overlap.
Implementation Notes
- Use proven split heuristics or bulk loading for static datasets.
- Keep update operations small and test invariants after insertions and deletions.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- Poor insertion order can produce overlapping boxes that reduce pruning.
- The advertised performance depends on maintaining the structure's invariants.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow nested rectangles grouping nearby spatial objects.
Step 1 of 4: Insert an object into the child requiring least bounding-box enlargement
data-structureNotes
Split heuristics strongly affect query performance.
Sources (1)
What each reference supports for this entry.
R-Trees
PaperOriginal reference for R-tree bounding rectangles, hierarchical spatial indexing, and insertion/search behavior.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toQuadtree
R-trees and quadtrees are spatial indexes with different bounding and subdivision strategies.
Tags
Data StructureSpatial IndexSpatial Data StructureTree