R*树

维基百科,自由的百科全书
跳转至: 导航搜索

R*树被用来索引空间信息,是R树的一种变体。R*树的构造花费比标准R树略高。例如数据可能需要被重新插入,但这通常能获得更好的查询性能。像标准R树一样,它能存储点和空间数据。 它在1990年由Norbert Beckmann,Hans-Peter Kriegel,Ralf Schneider,和Bernhard Seeger提出。[1]

R*树和R树的不同[编辑]

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

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. 重插能被看作增长树的一种优化方法, 它在节点溢出时被触发。

性能[编辑]

  • Improved split heuristic produces pages that are more rectangular and thus better for 许多应用。
  • 重插方法优化已经存在的树,但增加了复杂性。
  • 同时高效地支持点和空间数据。
在德国邮区数据库上不同分裂尝试的效果
R树 with Guttman 二次分裂。[2]
有很多从东延伸到西的页,它们跨越整个德国,并且页重叠很多。这无益于那些经常只需要一个很小矩形和许多slices相交的大多数应用。 
R树 with Ang-Tan 线性分裂。[3]
While the slices的延伸不像Guttman分裂那样远,the slicing 问题影响几乎每一个叶页。叶页重叠很少,但目录页重叠却很多。 
R*树拓扑分裂。[1]
由于R*树尝试最小化页重叠,页重叠非常少,而重插进一步优化此树。 分裂策略also does not prefer slices,结果页对于通常的地图应用有用得多。 

算法和复杂性[编辑]

  • R*树的查询和删除操作使用和正规R树一样的算法。
  • 插入时,R*树使用一种组合策略。对于叶节点,重叠被最小化,而对于内节点,则enlargement和area被最小化。
  • 分裂时,R*树使用一种拓扑分裂,其选择一条基于perimeter的分裂轴,然后最小化重叠。
  • 除改良的分裂策略外,R*树也尝试通过重插对象和子树来避免分裂,灵感来自平衡一颗B树的概念。

显然,worst case 查询和删除复杂性 are thus identical to R树. 插入策略 to R*树 is with \mathcal{O}(M \log M) 比线性分裂策略更复杂 (\mathcal{O}(M)) of the R树, but less complex 比二次分裂策略 (\mathcal{O}(M^2)) for a page size of M objects and has little impact on the 总复杂性. 总的插入复杂性 is still comparable to the R树: 重插至多影响一个树支 and 因此 \mathcal{O}(\log n) reinsertions, comparable to performing a split on a 正规R树. So on overall, R*树的复杂性 is the same as that of a 正规R树.

一个完整的算法实现必须address many corner cases and tie situations not discussed here.

参考资料[编辑]

  1. ^ 1.0 1.1 Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. The R*-tree: an efficient and robust access method for points and rectangles. Proceedings of the 1990 ACM SIGMOD international conference on Management of data - SIGMOD '90. 322. 1990. doi:10.1145/93597.98741. ISBN 0897913655.  编辑
  2. ^ Guttman, A. R-Trees: A Dynamic Index Structure for Spatial Searching. Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84. 47. 1984. doi:10.1145/602259.602266. ISBN 0897911288.  编辑
  3. ^ Ang, C. H.; Tan, T. C.. New linear node splitting algorithm for R-trees//Scholl, Michel; Voisard, Agnès. Proceedings of the 5th International Symposium on Advances in Spatial Databases (SSD '97), Berlin, Germany, July 15–18, 1997, Lecture Notes in Computer Science, 1262. Springer. 1997: pp. 337–349. doi:10.1007/3-540-63238-7_38.  编辑

外部链接[编辑]

包含R*树的库:

示例代码: