Rtree

R-tree is a height-balanced tree data structure used for indexing multi-dimensional information, such as rectangles or polygons, in spatial databases and geographic information systems. It was introduced by Antonin Guttman in 1984 as a dynamic alternative to grid-based indexing for efficient range and nearest-neighbor queries.

The tree organizes data into nodes that contain entries describing minimum bounding rectangles (MBRs) for their child entries. Each non-leaf node stores MBRs that cover all rectangles in its subtrees and pointers to child nodes, while leaf nodes contain MBRs with pointers to the actual data records. A node has a capacity limiting the number of entries; when an insertion would overflow, the node is split into two and the tree is adjusted upward to preserve balance.

Key operations include insertion, which selects a subtree to minimize the enlargement of existing MBRs, and node splitting according to algorithms such as linear, quadratic, or more commonly, the improved split methods used in variants. R*-tree, a popular refinement, adds a reinsertion step and prioritizes minimizing area, overlap, and perimeter of MBRs, leading to better query performance. Other variants, such as the R+-tree, modify how overlaps and duplicates are handled to improve search efficiency in certain workloads.

Queries exploit the MBRs to prune non-relevant branches. Range queries retrieve all records whose MBRs intersect the query region, while nearest-neighbor queries traverse nodes in order of increasing distance to their MBRs. The R-tree generally performs well for low to moderate dimensions but can suffer from overlapping MBRs in higher dimensions, which can degrade performance.

Applications include geographic information systems, computer-aided design, meshes and graphics databases, and any domain requiring efficient spatial indexing and retrieval.