R*-tree

In data processing R*-trees are a variant of R-trees used for indexing spatial information.

R*-trees have slightly higher construction cost than standard R-trees, as the data may need to be reinserted; but the resulting tree will usually have a better query performance.

It was proposed by Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger in 1990.

A minimized coverage improves pruning performance, allowing exclusion of whole pages from search more often, in particular for negative range queries.

Deletion and reinsertion of entries allows them to "find" a place in the tree that may be more appropriate than their original location.

Re-insertion can be seen as a method of incremental tree optimization triggered on node overflow.

The total insert complexity is still comparable to the R-tree: reinsertions affect at most one branch of the tree and thus

An implementation of the full algorithm must address many corner cases and tie situations not discussed here.

R*-Tree built by repeated insertion (in ELKI ). There is little overlap in this tree, resulting in good query performance. Red and blue MBRs are index pages, green MBRs are leaf nodes.