数据结构中的R *树

  • Z时代
  • 2024-01-10
  • 分类：综合

基本概念

在数据处理的情况下，R *树被定义为为索引空间信息而实现的R树的变体。

R *树比标准R树的建造成本稍高，因为可能需要重新插入数据。但是生成的树通常具有更好的查询性能。与标准R树相同，它可以存储点和空间数据。R *树的概念由Norbert Beckmann，Hans-Peter Kriegel，Ralf Schneider和Bernhard Seeger于1990年提出。

R *树和R树之间的区别

R * -Tree通过重复插入来构造。该树几乎没有重叠（即几乎没有重叠），因此查询性能良好。覆盖和重叠的最小化对于R树的性能非常重要。在数据插入或查询时，重叠的含义是需要扩展树的一个以上分支（由于将数据划分在可能重叠的区域中的方式）。最小化的覆盖范围可增强修剪性能，从而允许将整个页面频繁排除在搜索范围之外，尤其是对于负范围查询而言。R * -tree尝试减少两者，既实现了修订后的节点拆分算法的集合，又实现了在节点溢出时强制重新插入的概念。该概念基于以下观察结果：R树结构很容易受到其条目插入顺序的影响，因此，插入构建（而非批量加载）的结构可能不是最优的。条目的删除和重新插入使他们可以“找到”树中比实际位置更合适的位置。

算法和复杂度

  • R *树实现与用于查询和删除操作的常规R树类似的算法。

  • 插入时，R *树将实施组合策略。对于叶节点，重叠最小化，而对于内部节点，扩大和面积最小化。

  • 分割时，R *树实现拓扑分割，该拓扑根据周长选择分割轴，然后使重叠最小化。

  • 除了增强的拆分策略外，R *树还尝试通过将对象和子树重新插入到树中来跳过拆分，这受到平衡B树的概念的启发。

因此，最坏情况的查询和删除复杂度类似于R-Tree。R *树的插入策略的O（M log M）比R树的线性拆分策略（O(M)）更复杂，但比二次拆分策略（O（M 2））复杂。）用于M个对象的页面大小，并且对总复杂度影响很小。总插入复杂度仍可与R树媲美：重新插入会影响树的最大一个分支，因此会影响O（log n）重新插入，这与对常规R树执行除法相当。因此，总的来说，R *树的复杂性与常规R树的相似。

以上是 数据结构中的R *树 的全部内容， 来源链接： utcz.com/z/327300.html

回到顶部