原文towardsdatascience.com/spatial-index-r-trees-5ac6ad36ca20如果你一直在关注空间索引系列它始于对多维索引的需求和对空间填充曲线的介绍随后深入探讨了网格系统GeoHash 和 Google S2和镶嵌Uber H3。在本文中我们将探讨R-Tree数据结构数据驱动结构它被广泛用于存储多维数据例如数据点、线段和矩形。1. R-Trees 和矩形例如考虑下面所示的大学布局图。我们可以使用 R-Tree 数据结构来索引地图上的建筑物。为了做到这一点我们可以在建筑物或建筑物群周围放置矩形然后对它们进行索引。假设有一个更大的地图部分表示更大的部门我们需要查询该部门内的所有建筑物。我们可以使用 R-Tree 来找到所有位于部分或全部包含较大部分查询矩形内的建筑物。在上图红色矩形代表查询矩形用于请求 R-Tree 获取所有与查询矩形相交的建筑物R2, R3, R6。2. R-Tree – 直觉R-树中的主要思想是最小边界矩形。我们将在下一节中解释“最小”的含义。R-树的内部节点如下我们从一个表示大景观的根节点开始。内部节点是路标它们持有指向我们需要在树中向下导航的子节点的指针。即每个节点的条目指向数据空间的一个区域由 MBR 描述。例如考虑一个二叉搜索树。从根节点开始我们做出向左或向右的决定。R-树与此类似但更像是一个M 路树其中每个节点可以有多个条目如上图所示。内部节点由条目多维组成而不是整数或字符串值一维。在示例中有 4 个矩形的条目。2.1. MBR – 最小边界矩形最小边界矩形R1, R2, R3, R4以最小的方式包含存储在子树中的对象。例如假设我们有 3 个矩形R11, R12, R13。R1是能够完全包含所有三个矩形的最小矩形因此得名“最小”。2.2. 搜索过程和重叠的 MBRR-tree 中的搜索过程很简单对于一个查询对象/查询矩形在内部节点它是要检查节点中的任何条目是否与查询矩形相交的决定。例如考虑一个查询矩形Q1。很明显R1与Q1相交因此我们会从R1开始沿着树向下搜索。同样Q2与R2相交。然而在查询矩形与多个条目/矩形相交的情况下Q3与R2、R3、R4相交所有相交的矩形都必须被搜索。这可能发生在索引没有优化的情况下应该避免这种情况因为这违背了索引的初衷。2.3. R-树 – 属性这里是一个 R-tree 的较大示例。R-tree 中的每个节点都有m到M个条目。更具体地说每个节点都有m ≤ ⌈M/2⌉ and M个条目。除非它是叶节点否则节点至少有 2 个条目。到目前为止如果你也阅读了关于B-Trees 和 B Trees的博客文章你会发现 R-tree 与 B树非常相似。它在每个内部节点使用类似的思想将空间分割成多个区域。然而B树主要处理一维数据数据范围不重叠。3. 使用 R-树进行搜索现在我们已经了解了 R-tree 背后的思想和搜索过程让我们对搜索过程给出一个明确的定义目标找到所有与给定矩形S查询矩形重叠的矩形。用T表示当前级别/子树中的节点。S1在子树中搜索如果T不是叶节点检查T中的所有条目E。如果E的 MBR 与S重叠则继续在E指向的子树中进行搜索。S2在叶节点中搜索如果T是叶节点检查E的所有条目。所有与S重叠的条目都是查询结果的一部分。4. 插入到 R-树中在考虑插入时考虑以下图示的叶节点MBR其中包含 3 个条目/对象R1、R2和R3。假设叶节点还没有满MBR 对可以容纳的对象数量有一个阈值容量。假设有一个新的矩形R4到来它必须插入到叶节点内部。正如你所看到的为了捕捉新的对象MBR 被调整即扩大到最小地包含R1到R4。继续插入另一个对象R5MBR 再次被调整。在插入时当 MBR 更新即包含更多对象时新的 MBR 不仅要更新节点还要传播到其他较低级别甚至可能不总是传播到根节点。这是为了反映子树现在包含更多信息。4.1. 插入选择与示例不同并不总是清楚对象应该插入到哪个节点/子树中。这里MBR1、MBR2或MBR3。问题在于我们应该将R1插入到哪个 MBR 中暂时不考虑任何规则或理由R1可以插入到任何 MBR 中。将数据插入到MBR1需要极大地扩展MBR1以完全包含R1。这意味着什么比如说有一个查询矩形Q1。在将子树引导到MBR1之后我们发现没有任何东西没有对象。这是因为为了包含R1我们已经将MBR1扩展得很大以至于有很多空间但没有对象。因此可以公平地得出结论添加的一个标准是插入到需要最小扩展的 MBRs 中。根据这一点将数据插入到MBR2比插入到MBR1更好。同样MBR3也可能是一个不错的选择这取决于扩展因子。明说对于实现而言最小边界矩形MBR定义为每个维度上所有矩形中最大和最小值的矩形。总结到目前为止的 R-Tree 插入原则上可以将新的矩形插入到任何节点。如果节点已满则需要执行分割操作更多内容将在下一节中介绍。如果不是MBR 可能需要调整/扩展以容纳新对象如所示。观察扩展边界框是 R-Tree 性能的关键因素。尽量最小化重叠MBRs 的重叠。尽量最小化扩散MBR 的大小如第 4.1 节所示。4.2. 插入 – 算法这里是 R-Tree 论文用于空间搜索的动态索引结构的作者 A. Guttman 在 1984 年提出的算法。本节剩余部分主要涉及来自该论文的代码片段和解释但增加了更多示例和可视化。算法搜索插入的叶子节点ChooseLeafCS1设N为根。CS2如果N是叶子节点则返回N。如果N不是叶子节点在N中搜索一个条目其矩形MBR需要最小的面积增加以容纳新的矩形。在存在多个选项的情况下考虑具有最小面积MBR 的条目。CS3设N为子节点然后继续到 CS2 步骤重复。一个包含 8 个对象的简单示例每个对象有一个多维属性x 轴上的范围或线段和一个标识颜色。要将这些对象逐个插入到一个空的 R-tree 中该 R-tree 的度数为M 3每个节点上的最大条目数和m ≥ M/2每个节点上的最小条目数2。观察在所选叶子节点已满的情况下执行分割操作。让我们更好地理解溢出问题分割问题4.3. 处理溢出在节点/叶子节点已满且无法存储更多新条目的情况下需要执行分割操作就像 B树一样。不同之处在于分割可以是任意的而不仅仅是像 B树那样在中间进行。4.3.1. 分割问题在一个节点中有M 1个条目超过每个节点的最大容量应该考虑哪两个条目子集作为新节点和旧节点为了更好地理解分割问题让我们退一步考虑需要以有意义的方式分配到两个节点MBRs中的 4 个矩形R1, R2, R3, R4。为什么一个比另一个好如前所述第 4.1 节较差分割的扩展面积比良好分割大得多尽管有重叠。这导致节点/MBR 中有更多没有对象的空空间。R 树的一个实际用例是M 50有2^(M-1)种可能性。因此查看所有可能的子集并选择最佳方案的方法是不切实际的太昂贵了。4.3.2. 分割问题二次成本搜索具有可能最小面积的分隔成本在M上是二次的在维数d的数量上是线性的。理念搜索那些如果放在同一个节点中会导致最大 MBR 面积的条目对。然后将这些条目放在两个不同的节点中。然后考虑所有剩余的条目并考虑在两个节点中其中之一MBR 面积增加与另一个节点之间差异最大的那个。将此条目分配给增加最小的节点。重复此过程直到所有条目都被分配。在这个例子中创建了两个节点MBR1和MBR2。在同一个 MBR 中的R1和R2会导致创建最大的 MBR。然后将R3插入到MBR1而不是MBR2因为与MBR2相比MBR1的面积增加更小。当插入新条目时会调用“AdjustTree”方法。它负责调整父节点的 MBR 并自下而上传播更改处理分割以及 MBR 的变化。在最坏的情况下传播可以到达根节点。5. R-树变体R 树不保证良好的最坏情况性能但一般来说它们在现实世界数据中表现良好。针对这个问题优先级 R 树是空间树 R 树的最坏情况渐近最优的替代方案它本质上是一种 k 维树k-d 树和 R 树的混合体。另一个常用的变体是R*-树它在查询和删除操作上使用与常规 R 树相同的算法。然而在插入时R*-树使用一种组合策略对于叶节点重叠最小化对于内部节点扩大和面积最小化这使得树构建稍微昂贵一些。另一方面R±树解决了确保节点之间不重叠的一个主要问题从而提高了点查询性能。然而它通过在必要时将对象插入多个叶子节点来实现这一点由于重复条目和更大的树大小这带来了一定的缺点。希尔伯特 R-树使用空间填充曲线具体来说是希尔伯特曲线对数据矩形施加线性排序。它有两个变体打包希尔伯特 R 树适用于静态数据库其中更新非常罕见以及动态希尔伯特 R 树适用于动态数据库其中插入、删除或更新可能实时发生。6. 结论自 1984 年第一篇论文发表以来R 树已经取得了长足的进步。如今它们的应用范围涵盖多维索引、计算机图形学、视频游戏、空间数据管理系统以及更多领域。反之R 树在处理离散数据时可能会表现得很差。因此在使用 R 树之前强烈建议理解数据表示。当突变率非常高时即索引经常变化时R 树也相对较慢这是因为构建和更新索引由于树重新平衡的成本更高并且它们更优化于各种搜索操作。最后当主要处理点而不是多边形/区域时R 树可能是一个较差的算法选择。7. 参考文献除非另有说明所有图像均由作者提供[1]A.Guttman,A Dynamic Index Structure for Spatial Searching,presented at the ACM SIGMOD International Conference on Management of Data,1984\.[Online].Available:https://www.researchgate.net/publication/220805321_A_Dynamic_Index_Structure_for_Spatial_Searching.[2]R-Tree,Wikipedia.[Online].Available:https://en.wikipedia.org/wiki/R-tree.[3]B-Trees and B Trees,PyBlog.[Online].Available:https://www.pyblog.xyz/b-trees-b-plus-trees.[4]Spatial Index R-Tree,YouTube,https://www.youtube.com/watch?vU0jUvvQkaFw.