R+ tree
From Wikipedia, the free encyclopedia
R+ tree is a tree data structure, a variant of the R tree, used for indexing spatial information.
Contents |
[edit] 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
[edit] 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
[edit] 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.
[edit] Algorithm
[edit] External links
[edit] References
T. Sellis, N. Roussopoulos, and C. Faloutsos. The R+-Tree: A dynamic index for multi-dimensional objects. In VLDB, 1987.
