空间索引：R 树

原文：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. 搜索过程和重叠的 MBR

R-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。继续插入另一个对象R5，MBR 再次被调整。

在插入时，当 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 年提出的算法。

本节剩余部分主要涉及来自该论文的代码片段和解释，但增加了更多示例和可视化。

算法：搜索插入的叶子节点（ChooseLeaf）：

• CS1：设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?v=U0jUvvQkaFw.