R-tree
|
|
This article is about an R-tree data structure. See Real tree for another meaning.
R-trees are tree data structures that are similar to B-trees, but are used for spatial access methods i.e., for indexing multi-dimensional information; for example, the (X, Y) coordinates of geographical data. A common real-world usage for an R-tree might be: "Find all museums within 2 miles of my current location".
The data structure splits space with hierarchically nested, and possibly overlapping, boxes.
Each node of an R-tree has a variable number of entries (up to some pre-defined maximum). Each entry within a non-leaf node stores two pieces of data; a way of identifying a child node, and the bounding box of all entries within this child node.
The insertion and deletion algorithms use the bounding boxes from the nodes to ensure that "nearby" elements are placed in the same leaf node (in particular, a new element will go into the leaf node that requires the least enlargement in its bounding box). Each entry within a leaf node stores two pieces of information; a way of identifying the actual data element (which, alternatively, may be placed directly in the node), and the bounding box of the data element.
Similarly, the searching algorithms (for example; intersection, containment, nearest) use the bounding boxes to decide whether or not to search inside a child node. In this way, most of the nodes in the tree are never "touched" during a search. Like B-trees, this makes R-trees suitable for databases, where nodes can be paged to disk when needed.
Different algorithms can be used to "split" nodes when they become too full, resulting in the "Quadratic" and "Linear" R-tree sub-types.
R-trees do not historically guarantee good worst-case performance, but generally performed well with real-world data. However, a new algorithm was published in 2004 that defines the Priority R-Tree, which claims to be as efficient as the currently most efficient methods and is at the same time worst-case optimal.
| Contents |
Variants
Algorithm
References
- Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. ACM SIGMOD International Conference on Management of Data, ISBN 0-89791-128-8
- Lars Arge, Mark de Berg, Herman J.Haverkort, Ke Yi: The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree, Proc. ACM SIGMOD international conference on Management of data, ISBN 1-58113-859-8
External links
- R-tree portal (http://www.rtreeportal.org/)de:R-Baum