RTrees

R-trees are a family of height-balanced tree data structures designed for indexing multi-dimensional information such as rectangles, polygons, and points. They use minimum bounding rectangles (MBRs) to summarize the spatial extent of their child nodes. In an R-tree, internal nodes contain entries with a pointer to a child node and the MBR that bounds all rectangles in that child, while leaf nodes store entries that point to the actual data objects along with their MBRs. The tree aims to keep the height small and the MBRs compact to enable efficient searches.

Typically an R-tree stores between a minimum and maximum number of entries per node. Insertion routes down the tree choosing the path whose MBR requires the least enlargement to accommodate the new item. If a node overflows, it is split into two nodes and the split propagates upward. Variants include different split strategies, such as quadratic and linear splits, and considerations for reinserting subtrees to improve performance. Deletions may cause underfull nodes, prompting tree condensation to maintain occupancy.

Querying an R-tree relies on MBR intersections. Range queries traverse only those branches whose MBRs intersect the query region. Nearest-neighbor queries can be supported by progressively exploring promising branches. The design trades exactness of bounding boxes for efficient pruning, but high overlap among MBRs can degrade performance.

Variants such as the R*-tree and R+-tree aim to reduce overlap and improve query efficiency. R*-trees typically optimize splits to minimize both area and overlap, often yielding better performance for spatial queries. Other derivatives, like the X-tree, address high-dimensional data.

Applications include geographic information systems, computer-aided design, spatial databases, and multimedia databases that index spatial features. Limitations include sensitivity to data distribution and the curse of dimensionality, which can reduce pruning effectiveness in higher dimensions.