R+ tree is a variant of R tree for indexing spatial information.

Difference between R+ trees and R trees

• R+ trees is a compromise between R tree and K-D-B tree.
• It avoids overlapping of internal nodes by inserting an object into multiple leaves if necessary
• R+ trees differ R trees:
  • 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 is benefits from the non-overlapping of nodes
• A single path is followed and fewer nodes are visited than with the R-tree

Disadvantages

• Since rectangles are duplicated, R+ tree can be larger than R tree built on same data set.
• Construction and maintenance of R+ tree are more complex than R tree and other variants of R tree.

Algorithm

External links