R* tree

R* tree is a variant of R tree for indexing spatial information. R* tree supports point and spatial data at the same time with a slightly higher cost than other R-trees. It was proposed by Norbert Beckmann in 1990.

Difference between R* trees and R trees

Minimization of both coverage and overlap is crucial to the performance of R-trees. R* trees attempts to reduce both overlap and coverage. R* trees need a forced reinsertion algorithm when a node overflows. When a node overflows, instead of splitting:

• Remove some entries and reinsert them into the tree
• Could result in all reinserted entries fitting on some existing pages, avoiding a split.

Performance

• Likely significant improvement over other R tree variants, but there is overhead due to the reinsertion method.
• Efficiently supports point and spatial data at the same time

Algorithm

References

• Norbert Beckmann, Hans- N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322–331

External links

• R-tree Demo