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 B-tree. Worst case query and delete complexity are thus identical to the R-Tree. The insertion strategy to the R*-tree is with more complex than the linear split strategy () of the R-tree, 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 R-tree: reinsertions affect at most one branch of the tree and thus 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. References External links R-tree Database index techniques de:R-Baum