Rtree

lastmod 2018-08-26created 2014-09-153 edits

An R-tree is an index similar to a B-tree, but one that stores multidimensional spatial data. For example, in geography, an R-tree can quickly answer queries such as "find all cities within 200 km of the current location".

This data structure stores space by partitioning it into minimum bounding rectangles (MBR). These MBRs may overlap one another, and they are organized in a hierarchical tree structure in which a higher-level MBR contains lower-level MBRs. Each node of an R-tree holds information (MBR and pointer) about a variable number of child nodes within a predefined range.

The R-tree's insertion and deletion algorithms try to keep nearby data in the same leaf node whenever possible. This lets the R-tree maintain its MBRs robustly and improves search performance, because the search algorithms (intersection, containment, nearest neighbor) use these MBRs to decide whether to search the lower-level child nodes.

See also

• Tree

Favorite site

• Wikipedia (en) description of R-Tree
• R-Trees sample source code ¹
• An Analysis of Minecraft-like Engines | 0 FPS (about R-Tree)

References