数据结构中的R *树
基本概念
在数据处理的情况下，R*树被定义为为索引空间信息而实现的R树的变体。
R*树比标准R树的建造成本稍高，因为可能需要重新插入数据。但是生成的树通常具有更好的查询性能。与标准R树相同，它可以存储点和空间数据。R*树的概念由NorbertBeckmann，Hans-PeterKriegel，RalfSchneider和BernhardSeeger于1990年提出。
R*树和R树之间的区别
R*-Tree通过重复插入来构造。该树几乎没有重叠（即几乎没有重叠），因此查询性能良好。覆盖和重叠的最小化对于R树的性能非常重要。在数据插入或查询时，重叠的含义是需要扩展树的一个以上分支（由于将数据划分在可能重叠的区域中的方式）。最小化的覆盖范围可增强修剪性能，从而允许将整个页面频繁排除在搜索范围之外，尤其是对于负范围查询而言。R*-tree尝试减少两者，既实现了修订后的节点拆分算法的集合，又实现了在节点溢出时强制重新插入的概念。该概念基于以下观察结果：R树结构很容易受到其条目插入顺序的影响，因此，插入构建（而非批量加载）的结构可能不是最优的。条目的删除和重新插入使他们可以“找到”树中比实际位置更合适的位置。
算法和复杂度
R*树实现与用于查询和删除操作的常规R树类似的算法。
插入时，R*树将实施组合策略。对于叶节点，重叠最小化，而对于内部节点，扩大和面积最小化。
分割时，R*树实现拓扑分割，该拓扑根据周长选择分割轴，然后使重叠最小化。
除了增强的拆分策略外，R*树还尝试通过将对象和子树重新插入到树中来跳过拆分，这受到平衡B树的概念的启发。
因此，最坏情况的查询和删除复杂度类似于R-Tree。R*树的插入策略的O（MlogM）比R树的线性拆分策略（O(M)）更复杂，但比二次拆分策略（O（M2））复杂。）用于M个对象的页面大小，并且对总复杂度影响很小。总插入复杂度仍可与R树媲美：重新插入会影响树的最大一个分支，因此会影响O（logn）重新插入，这与对常规R树执行除法相当。因此，总的来说，R*树的复杂性与常规R树的相似。