An R+ tree is a method for looking up data using a location, often (x, y)
coordinates
In geometry, a coordinate system is a system that uses one or more numbers, or coordinates, to uniquely determine the position of the points or other geometric elements on a manifold such as Euclidean space. The order of the coordinates is sig ...
, and often for locations on the
surface of the earth. Searching on one number is a solved problem; searching on two or more, and asking for locations that are nearby in both x and y directions, requires craftier algorithms.
Fundamentally, an R+ tree is a
tree data structure
In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be conn ...
, a variant of the
R tree, used for
indexing spatial information.
Difference between R+ trees and R trees
R+ trees are a compromise between
R-tree
R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons. The R-tree was proposed by Antonin Guttman in 1984 and has found sign ...
s and
kd-trees: they avoid overlapping of internal nodes by inserting an object into multiple leaves if necessary. Coverage is the entire area to cover all related rectangles. Overlap is the entire area which is contained in two or more nodes.
Minimal coverage reduces the amount of "dead space" (empty area) which is covered by the nodes of the R-tree. Minimal overlap reduces the set of search paths to the leaves (even more critical for the access time than minimal coverage). Efficient search requires minimal coverage and overlap.
R+ trees differ from R trees in that: nodes are not guaranteed to be at least half filled, the entries of any internal node do not overlap, and an object ID may be stored in more than one leaf node.
Advantages
Because nodes are not overlapped with each other, point query performance benefits since all spatial regions are covered by at most one node. A single path is followed and fewer nodes are visited than with the R-tree.
Disadvantages
Since rectangles are duplicated, an R+ tree can be larger than an R tree built on same data set. Construction and maintenance of R+ trees is more complex than the construction and maintenance of R trees and other variants of the R tree.
Notes
References
* T. Sellis, N. Roussopoulos, and
C. FaloutsosThe R+-Tree: A dynamic index for multi-dimensional objects In VLDB, 1987.
{{DEFAULTSORT:R Tree
R-tree
Database index techniques
de:R-Baum