R-Tree Algorithm

An R-tree is a tree data structure for indexing multidimensional spatial information such as the coordinates of geographic features, introduced by Antonin Guttman in 1984. It groups nearby objects together and represents each group by its minimum bounding rectangle at the next level up the tree, the R in the name, so that leaf nodes describe individual objects such as points, lines or shapes while higher levels describe increasingly coarse approximations of the data beneath them. Because a spatial query that does not intersect a bounding rectangle also cannot intersect anything inside it, an R-tree can skip searching most of its nodes when answering queries such as finding every restaurant within a given distance or the nearest matching feature to a point, including under distance metrics such as great-circle distance; the structure borrows its balanced, page-based, disk-oriented organization from the B-tree, which is why it has seen extensive use in geographic information systems and spatial databases.