R* tree
R*trees are a variant of Rtrees used for indexing spatial information. R*trees have slightly higher construction cost than standard Rtrees, as the data may need to be reinserted; but the resulting tree will usually have a better query performance. Like the standard Rtree, it can store both point and spatial data. It was proposed by Norbert Beckmann, HansPeter Kriegel, Ralf Schneider, and Bernhard Seeger in 1990.^{[1]}
Difference between R*trees and Rtrees
Minimization of both coverage and overlap is crucial to the performance of Rtrees. 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 to exclude 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 Rtree structures are highly susceptible to the order in which their entries are inserted, so an insertionbuilt (rather than bulkloaded) structure is likely to be suboptimal. 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 wellclustered groups of entries in nodes, reducing node coverage. Furthermore, actual node splits are often postponed, causing average node occupancy to rise. Reinsertion can be seen as a method of incremental tree optimization triggered on node overflow.
Performance
 Improved split heuristic produces pages that are more rectangular and thus better for many applications.
 Reinsertion method optimizes the existing tree, but increases complexity.
 Efficiently supports point and spatial data at the same time.
Effect of different splitting heuristics on a database with Germany postal districts  


Algorithm and complexity
 The R*tree uses the same algorithm as the regular Rtree for query and delete operations.
 When inserting, the R*tree uses a combined strategy. For leaf nodes, overlap is minimized, while for inner nodes, enlargement and area are minimized.
 When splitting, the R*tree uses a topological split that chooses a split axis based on perimeter, then minimizes overlap.
 In addition to an improved split strategy, the R*tree also tries to avoid splits by reinserting objects and subtrees into the tree, inspired by the concept of balancing a Btree.
Worst case query and delete complexity are thus identical to the RTree. The insertion strategy to the R*tree is with more complex than the linear split strategy () of the Rtree, but less complex than the quadratic split strategy () for a page size of objects and has little impact on the total complexity. The total insert complexity is still comparable to the Rtree: reinsertions affect at most one branch of the tree and thus reinsertions, comparable to performing a split on a regular Rtree. So on overall, the complexity of the R*tree is the same as that of a regular Rtree.
An implementation of the full algorithm must address many corner cases and tie situations not discussed here.
References
 1 2 Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*tree: an efficient and robust access method for points and rectangles". Proceedings of the 1990 ACM SIGMOD international conference on Management of data  SIGMOD '90 (PDF). p. 322. doi:10.1145/93597.98741. ISBN 0897913655.
 ↑ Guttman, A. (1984). "RTrees: A Dynamic Index Structure for Spatial Searching". Proceedings of the 1984 ACM SIGMOD international conference on Management of data  SIGMOD '84 (PDF). p. 47. doi:10.1145/602259.602266. ISBN 0897911288.
 ↑ Ang, C. H.; Tan, T. C. (1997). "New linear node splitting algorithm for Rtrees". In Scholl, Michel; Voisard, Agnès. Proceedings of the 5th International Symposium on Advances in Spatial Databases (SSD '97), Berlin, Germany, July 15–18, 1997. Lecture Notes in Computer Science. 1262. Springer. pp. 337–349. doi:10.1007/3540632387_38.
External links
Wikimedia Commons has media related to R* tree. 
Libraries containing R*trees:
 Boost.Geometry rtree documentation (C++)
 ELKI R*tree package documentation (Java)
 Spatial Index Library (C++)
 SQLite R*tree module (C)
 TPIE Library (C++)