R*树

R*树
发明时间	1990年
发明者	諾伯特·貝克曼、漢斯-彼得·克里戈爾、拉爾夫·施奈德、伯恩哈德·西格
用大O符号表示的时间复杂度
算法 平均 最差 空间 $O(n)$ $O(n)$ 搜索 $O(\log n)$ 插入 $O(\log n)$

在数据处理中，R*树（英語：R*-tree）是R树的一种变体，可用来索引空间信息。R*树的构造花费比标准R树略高，因为数据可能需要被重新插入，但生成的树通常能获得更好的查询性能。像标准R树一样，它能存储点和空间数据。它在1990年由諾伯特·貝克曼（Norbert Beckmann）、漢斯-彼得·克里戈爾、拉爾夫·施奈德（Ralf Schneider）和伯恩哈德·西格（Bernhard Seeger）提出。

R*树和R树的不同

由反复插入构建的R*树 (in ELKI)。 这颗树的重叠较少，因此有很好的查询性能。 红的和蓝的MBRs是索引页，绿的MBRs是叶节点。

覆盖和重叠的最小化对于R树的性能至关重要。重叠意味着，在数据查询和插入时，需要扩展树的多个分支（由于数据会被拆分到许多可能重叠的区域）。覆盖率的最小化提高了修剪性能，允许更频繁地从搜索中排除整个页面，特别是负范围查询。

R*树通过结合修改后的节点拆分算法和在节点溢出时强制重新插入的概念，去尝试减少覆盖和重叠。这是基于观察到 R-tree 结构非常容易受到其条目插入顺序的影响，因此插入构建（而不是批量加载）结构可能不是最优的。条目的删除和重新插入可能让它们“找到”树中比其原始位置更合适的位置。

当一个节点溢出时，它的一部分条目会从节点中删除并重新插入到树中。（为了避免由后续节点溢出导致的无限级联重新插入，在插入任何新条目时，在树的每一级中，重新插入的例程可能只被调用一次。）这带来了在节点中生成更多聚集良好的条目组的效果，从而减少节点覆盖。此外，实际的节点拆分经常被推迟，导致平均节点占用率上升。重新插入可以看作是节点溢出触发的增量树优化的一种方法。

性能

• 改进的启发式拆分可以生成更矩形的分页，因此更适合许多应用程序。
• 重插方法优化了现有树，但增加了复杂性。
• 同时高效地支持点和空间数据。

在德国邮区数据库上不同拆分尝试的效果

• 
  R树，采用Guttman二次拆分方式。
  有很多从东延伸到西的页，它们跨越整个德国，并且页重叠很多。这无益于那些经常只需要一个与许多切片相交的小矩形区域的大多数应用。
• 
  R树，采用Ang-Tan线性拆分。
  尽管条形区域的延伸不像Guttman拆分那样远，条形切割的问题影响几乎每一个叶页。叶页重叠很少，但目录页重叠却很多。
• 
  R*树拓扑拆分。
  由于R*树尝试最小化页重叠，使得页重叠非常少，并且重插进一步优化此树，拆分策略亦尽量避免产生条形区域，因而结果页对于通常的地图应用有用得多。

算法和复杂性

• R*树的查询和删除操作使用和常规R树一样的算法。
• 插入时，R*树使用一种组合策略。对于叶节点，重叠被最小化，而对于内节点，则最小化放大和面积。
• 拆分时，R*树使用一种拓扑拆分，根据周长选择拆分轴，然后最小化重叠。
• 除改良的拆分策略外，R*树还尝试通过将对象和子树重新插入树中来避免拆分，这受到B树平衡概念的启发。

因此，最坏情况下R*树的查询和删除复杂度与R树相当。R*树的插入策略的${\mathcal {O}}(M\log M)$比R树线性拆分策略的复杂度高（${\mathcal {O}}(M)$），但比R树取页大小为$M$时的二次拆分策略（${\mathcal {O}}(M^{2})$）复杂度低，并且对总复杂度没有太大的影响。R*树总的插入复杂性仍与R树相当。重插至多影响一个树支，因此重插操作具有${\mathcal {O}}(\log n)$的复杂度，这与正规R树的拆分操作相当。总体而言，R*树的复杂度与正规R树处于同一数量级。

一个完整的算法实现必须考虑诸多未在此处涉及的邊角案例与特殊情况。

外部链接

包含R*树的库：

• Boost.Geometry rtree documentation (C++, maybe R-tree only)
• ELKI R*-tree package documentation（页面存档备份，存于互联网档案馆） (Java)
• Spatial Index Library（页面存档备份，存于互联网档案馆） (C++)
• SQLite R*-tree module（页面存档备份，存于互联网档案馆） (C)
• TPIE Library（页面存档备份，存于互联网档案馆） (C++)
• XXL Library（页面存档备份，存于互联网档案馆） (Java, maybe R-tree only)

示例代码：

• A header-only C++ R* Tree Implementation（页面存档备份，存于互联网档案馆） (probably buggy and it does not generate a R*-tree, but a freely defined (by the code author) variation of the original definition)
• A 2D R*-tree implementation (C/C++)
• R-tree Demo Applet (requires Java)（页面存档备份，存于互联网档案馆）