R+ tree

From Wikipedia, the free encyclopedia

The introduction to this article provides insufficient context for those unfamiliar with the subject matter.
Please help improve the introduction to meet Wikipedia's layout standards. You can discuss the issue on the talk page.

R+ tree is a tree data structure, a variant of the R tree, used for indexing spatial information.

1 Difference between R+ trees and R trees
2 Advantages
3 Disadvantages
4 Algorithm
5 External links
6 References

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