数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究数据结构中的R*树
基本概念
在数据处理的情况下，R*树被定义为R树的一种变体，用于索引空间信息。
R*树的构建成本略高于标准R树，因为数据可能需要重新插入；但生成的树通常具有更好的查询性能。与标准R树相同，它可以存储点数据和空间数据。R*树的概念由Norbert Beckmann、Hans-Peter Kriegel、Ralf Schneider和Bernhard Seeger于1990年提出。
R*树和R树的区别
R*树通过重复插入构建。这棵树几乎没有重叠，从而实现了良好的查询性能。最小化覆盖率和重叠对于R树的性能非常重要。在数据插入或查询时，重叠的含义是树的多个分支需要扩展（由于数据被划分为可能重叠的区域的方式）。最小化的覆盖率增强了剪枝性能，允许频繁地将整个页面排除在搜索之外，特别是对于负范围查询。R*树试图减少两者，实现了一系列改进的节点分裂算法和强制重新插入节点溢出的概念。这个概念基于这样的观察：R树结构对其条目插入的顺序高度敏感，因此插入构建（而不是批量加载）的结构可能不是最优的。条目的删除和重新插入允许它们在树中“找到”一个比其实际位置更合适的位置。
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
算法和复杂度
- 对于查询和删除操作，R*树实现了与常规R树类似的算法。
- 在插入时，R*树实现了一种组合策略。对于叶子节点，最小化重叠，而对于内部节点，最小化扩展和面积。
- 在分裂时，R*树实现了一种拓扑分裂，它根据周长选择分裂轴，然后最小化重叠。
- 除了改进的分裂策略外，R*树还尝试通过将对象和子树重新插入到树中来跳过分裂，这受到了平衡B树概念的启发。
因此，最坏情况下的查询和删除复杂度与R树相似。R*树的插入策略比R树的线性分裂策略（O(M)）复杂O(M log M)，但比页面大小为M个对象的二次分裂策略（O(M2)）复杂度低，并且对总复杂度影响不大。总的插入复杂度仍然与R树相当：重新插入影响树的一个分支，因此有O(log n)次重新插入，这与对常规R树执行划分相当。因此，总的来说，R*树的复杂度与常规R树相似。
477 次浏览
