本文的资料来源于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是不一样的,不会让小节点和兄弟合并,相反是将其中的数据重新插入,以避免空间分割效果退化。
2. R-tree如何组织空间对象的?
刚才已经提到,插入时,每次会选择离自己最近的节点路由下去,这意味着距离更近的对象,更有可能在同一个节点。这个近的意思其实是那个节点,能用最小的面积增长,把这个新对象包含在它的MBR里。
这样,我们可以非常容易举出反例,在R-tree上,两个距离很近的对象在两个不同的节点里。但是这并不影响R-tree整体的结构是完备的,高效的。追求绝对最近不一定有意义。
3. R-tree为何会产生节点空间重叠?
这要从R-tree的节点分割策略说起。因为在搜索时,所有产生overlap的区域都要被搜索。因此为了能增强剪枝率,索引包含的总的面积越小越好。分割就是这样的heuristic,目标是使分割后两个节点的总面积最小。这其实在插入时已经体现了,因为其尽可能让节点扩张的面积更小。这样的结果必然是会出现重叠以保证合并面积最小。
image.png
要找出绝对最小的两组对象,复杂度太高,原文提了两个启发式的贪婪分割方法。
【n是叶子节点容量,d是空间对象维度】
3.1 平方级别算法
- 找到两个对象,如果把它们放进一个组里,浪费空间最多;
- 遍历所有剩下的点:计算这个点到两个组产生的扩张面积,选择扩张面积差异最大的那个点。
- 把这个点分配到为了包括这个点,扩张面积较小的那个组。
- 如果剩下的点全部分配到一个组都不够它半满了,直接全丢到那个组里;否则选下一个点。
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条记录的待分裂节点:
- 选维度:
- 对每个维度,让孩子MBR在这个维度上的值排序,然后在中间选择一个点,将这个节点中的M条记录分成两部分,找到那个“最好的”分割点。由于分裂后需要有平衡性保障(每个节点中至少有m个记录),所以至多有M-2m+2个可能的分割点,即不能让两个子节点的基数差距太极端。
- 如何判定每个分割点的质量呢?即,如果按此分割点将记录分成两个节点,我们计算两个节点内部的margin area(即被节点所代表的MBR所覆盖,但没有被记录的MBR所覆盖,是无意义的覆盖区域),margin area越小越好。
- 最终每个维度都会选出一个最好的分割点,比较各个维度,选出一个最好的作为分裂维度。
- 对每个维度,让孩子MBR在这个维度上的值排序,然后在中间选择一个点,将这个节点中的M条记录分成两部分,找到那个“最好的”分割点。由于分裂后需要有平衡性保障(每个节点中至少有m个记录),所以至多有M-2m+2个可能的分割点,即不能让两个子节点的基数差距太极端。
- 选分割线:
- 给定维度之后,与想象中不同的是,不直接使用margin are选出来的最好的分割点直接分布,而是选择使两个子节点overlap-value【重叠区域】最小的分布进行分割。
网友评论