本文的资料来源于R-tree初代论文
R-TREES: A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING (1984年SIGMOD)
做本文的一个动机是，中文互联网上对R-tree结构的介绍不少，但是对其设计原因讲的不多，尤其是对于底层小矩形是如何“排序”，“聚类”的。而这个问题导致了R-tree在兄弟节点所代表的空间上是有重叠的。

1. R-tree的基本介绍

• 索引的数据对象未必是一个点，也有可能在高维空间上有面积/体积。

• R-tree索引的其实是数据对象的MBR。

• 叶子节点是数据对象MBR的MBR，中间节点是孩子节点MBR的MBR，直至根节点。

• R-tree的中间节点和叶子节点至少有m条记录，m是不足半满的，这一点弱于B+-tree。

• 搜索方法：从根节点起，其中所有和query对象有overlap的子树，全都要进行搜索。直到找到所有和query对象有overlap的数据对象

• 插入方法：

  • 找到对应叶子节点：由于子树的MBR可能都无法完全重叠要插入的数据对象q，因此每次都找和q距离最近的（包含q则距离为0）。距离同样近就选择面积小的。
  • 插入q至叶子节点：有可能造成分裂，后面讲。
  • 树调整：让对应叶子节点的MBR要调整一下，使得能闭包q的范围，相应逐层向上调整。如果有分裂的叶子节点，就让父节点再插入一个entry，也有可能造成父节点继续分裂。

• 删除方法：不详细介绍了。但是和B-tree是不一样的，不会让小节点和兄弟合并，相反是将其中的数据重新插入，以避免空间分割效果退化。

image.png

2. R-tree如何组织空间对象的？

刚才已经提到，插入时，每次会选择离自己最近的节点路由下去，这意味着距离更近的对象，更有可能在同一个节点。这个近的意思其实是那个节点，能用最小的面积增长，把这个新对象包含在它的MBR里。
这样，我们可以非常容易举出反例，在R-tree上，两个距离很近的对象在两个不同的节点里。但是这并不影响R-tree整体的结构是完备的，高效的。追求绝对最近不一定有意义。

3. R-tree为何会产生节点空间重叠？

这要从R-tree的节点分割策略说起。因为在搜索时，所有产生overlap的区域都要被搜索。因此为了能增强剪枝率，索引包含的总的面积越小越好。分割就是这样的heuristic，目标是使分割后两个节点的总面积最小。这其实在插入时已经体现了，因为其尽可能让节点扩张的面积更小。这样的结果必然是会出现重叠以保证合并面积最小。

image.png

要找出绝对最小的两组对象，复杂度太高，原文提了两个启发式的贪婪分割方法。

【n是叶子节点容量，d是空间对象维度】

3.1 平方级别算法

1. 找到两个对象，如果把它们放进一个组里，浪费空间最多；
2. 遍历所有剩下的点：计算这个点到两个组产生的扩张面积，选择扩张面积差异最大的那个点。
3. 把这个点分配到为了包括这个点，扩张面积较小的那个组。
4. 如果剩下的点全部分配到一个组都不够它半满了，直接全丢到那个组里；否则选下一个点。

3.2 线性级别算法

和平方级别算法很像，只不过初始点是在各维上贪婪的选择某一维离得最远的两个点。
选剩下的点时也不做选择了，随机选择，分配到扩张面积更小的那一组。

4. 问题：重叠区域

重叠其实是一个很大的麻烦，但是原版R-tree并没有考虑到。一个重要的原因是一旦查询对象和重叠区域有交集，那么多个子树都要同时查询，严重影响剪枝率。因此，后续的方法都着重在改善重叠区域问题。

4.1 R+-tree

如果数据对象横跨多个区域，那就在多个区域都存一份，这样就不会在叶子节点之间有overlap。相应的，中间节点之间也没有overlap。
分裂时，会对叶子节点每个维度扫一遍，尝试在均匀把它们分开，在所有维度上，根据Care的指标为分裂打分，选择最好的

• 缺点：重复放置了部分数据，节点负载不能被保证半满以上，插入分裂算法复杂一些。

4.1 R*-tree

R*-tree修改了分裂算法和路由算法，使得重叠面积也被考虑进代价之中。但显然，R*-tree仍然允许重叠，只不过重叠少了很多。R*-tree被认为是一种经典优化。

image.png

具体来说，R*-tree的分裂算法如下，对于一个有M+1条记录的待分裂节点：

1. 选维度：
   1. 对每个维度，让孩子MBR在这个维度上的值排序，然后在中间选择一个点，将这个节点中的M条记录分成两部分，找到那个“最好的”分割点。由于分裂后需要有平衡性保障（每个节点中至少有m个记录），所以至多有M-2m+2个可能的分割点，即不能让两个子节点的基数差距太极端。
      • 如何判定每个分割点的质量呢？即，如果按此分割点将记录分成两个节点，我们计算两个节点内部的margin area（即被节点所代表的MBR所覆盖，但没有被记录的MBR所覆盖，是无意义的覆盖区域），margin area越小越好。
   2. 最终每个维度都会选出一个最好的分割点，比较各个维度，选出一个最好的作为分裂维度。
2. 选分割线：
   1. 给定维度之后，与想象中不同的是，不直接使用margin are选出来的最好的分割点直接分布，而是选择使两个子节点overlap-value【重叠区域】最小的分布进行分割。