R+ tree

R+ tree is a tree data structure, 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 trees and K-D-B trees; they avoid overlapping of internal nodes by inserting an object into multiple leaves if necessary.

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
*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.

Algorithm

ee also

*R tree
*R* tree
*Hilbert R-tree

External links

References

T. Sellis, N. Roussopoulos, and C. Faloutsos. [http://citeseer.ist.psu.edu/sellis87rtree.html The R+-Tree: A dynamic index for multi-dimensional objects] . In VLDB, 1987.