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. Like the standard R-tree, it can store both point and spatial data. It was proposed by Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger in 1990. Difference between R*-trees and R-trees. Minimization of both coverage and overlap is crucial to the performance of R-trees. Overlap means that, on data query  or insertion, more than one branch of the tree needs to be expanded (due to the way data is being split in regions which may overlap). A minimized coverage improves pruning performance, allowing exclusion of whole pages from search more often, in particular for negative range queries. The R*-tree attempts to reduce both, using a combination of a revised node split algorithm and the concept of forced reinsertion at node overflow. This is based on the observation that R-tree structures are highly susceptible to the order in which their entries are inserted, so an insertion-built (rather than bulk -loaded) structure is likely to be sub-optimal. Deletion and reinsertion of entries allows them to "find" a place in the tree that may be more appropriate than their original location. When a node overflows, a portion of its entries are removed from the node and reinserted into the tree. (In order to avoid an indefinite cascade of reinsertions caused by subsequent node overflow, the reinsertion routine may be called only once in each level of the tree when inserting any one new entry.) This has the effect of producing more well-clustered groups of entries in nodes, reducing node  coverage. Furthermore, actual node splits are often postponed, causing average node occupancy to rise. Re-insertion can be seen as a method of incremental tree optimization triggered on node overflow. Algorithm and complexity. Worst case query and delete complexity are thus identical to the R-Tree. The insertion strategy to the R*-tree is with formula_1 more complex than the linear split strategy (formula_2) of the R-tree, but less complex than the quadratic split strategy (formula_3) for a page size of formula_4 objects and has little impact on the total complexity. The total insert complexity is still comparable to the  R-tree: reinsertions affect at most one branch of the tree and thus formula_5 reinsertions, comparable to performing a split on a regular R-tree. So on overall, the complexity of the R*-tree is the same as that of a regular R-tree. An implementation of the full algorithm must address many corner cases and tie situations not discussed here.