R*树

R*树和R树的不同

coverage和重叠的最小化对于R树的性能至关重要。重叠意味着，对于数据查询和插入，多于一个的树分支需要被扩展（由于这个方法数据将被分裂到许多可能重叠的区域）。 一个最小化的coverage 改进修剪性能，经常允许从搜索排除 所有页面，特别是负值范围的查询。
在节点溢出时，R*树尝试减少both, using a combination of a revised 节点分裂算法和强制重插的概念。 这基于观察that R树结构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. entries的删除和重插允许他们在树中“找”到一个比原来更适合的位置。
当一个节点溢出，它的一部分entries会被移除并重新插入到树。
(为了避免被随后的节点溢出引起an indefinite cascade of 重插，重插例程可能只被调用一次in 树的每一级when 插入任一新的entry。) This has the 
effect of producing more well-clustered groups of entries in nodes, 减少节点coverage。 此外，
actual node splits are often postponed, causing average node occupancy to rise.
重插能被看作增长树的一种优化方法, 它在节点溢出时被触发。