全部栏目

首页 热点资讯 义务教育 高等教育 出国留学 考研考公
您的当前位置：首页Rtree基本原理

Rtree基本原理

2024-12-13 来源：哗拓教育

1.背景

空间数据经常是多维的，并不能用一些点来简单的表示。例如地图里面的街道、村庄等。对空间数据的一个典型操作是查找某个区域的所有目标，例如望京SOHO附近的饭店。

对空间数据建立索引是一种好的想法，但传统数据库的一维索引并不适合对多维数据的查找。例如 hash 等结构也不适合，因为搜索的时候有一定的范围。而类似 B-Tree 的一些结构不能实现对多维数据的查找。

2. R-Tree索引

R-Tree 索引是一个高度平衡的树，在它的叶节点存放指向数据的指针。并且 RTree 能够保证对一个空间数据的搜索只需要访问很小一部分的 node。

空间数据库包含了很多 tuple ，这些 tuple 代表了空间数据。每一个 tuple 有一个唯一的标识（ID ），这样可以访问到某个 tuple 。 RTree 中叶节点包含的索引记录的形式是 (I , tuple-identifier), 这里的 id 指向数据库中的一个 tuple 。 I 表示一个 n 维的矩形，这个矩形是一个 bounding box ，用来涵盖被索引的空间数据对象。

I =(I0, I1, I2, …., In-1) ， n 表示维度， Ii 是一个闭区间 [a, b], 用来表示对象在第 i 维中的长度。另外，如果 a 或者 b 是无穷的话，表示该对象延伸到了无限远处。

非叶节点的形式是 (I, child-pointer) 。 child-pointer 是子节点的地址； I 是覆盖了其所有子节点的矩形。

在 RTree 中，每个节点所有的子节点的数目是有限制的，假设每个节点最多拥有 M 个子节点，m<=M/2. 则 RTree 有以下的属性：

  • 除了根节点外，每个节点所拥有的子节点数要在 [m, M] 间；
  • 对于每一个叶节点的索引记录 (I , tuple-identifier) ， I 是最小的能够包含 n 维数据对象的矩形；
  • 对于每一个非叶节点的索引记录 (I, child-pointer) ， I 是最小的能够包含所有子节点的矩形；
  • 根节点至少有 2 个子节点；
  • 所有的叶节点都在同一层；
R-Tree.png

2.1 查找

查找是从根节点开始( 实现的时候需要从任意节点都可以) 。查找时，可能会有多个子树被访问。

假设根节点是T; 索引entry 用E 表示；EI 表示这个索引的矩形；Ep 表示tuple-identifier或者child-pointer.

2.2 搜索算法

给定一个RTree ，找出所有的索引记录，这些索引的矩形与搜索矩形S （这个搜索矩形是指定的，可以考虑为一个参数）有重叠的部分。

S1. 搜索子树。如果T 不是叶节点，检查每一个entry ，看EI 是否与S 有重叠，如果有，则递归调用search ，用于搜索以EP 为根节点的子树。

S2. 搜索叶节点。如果T 是叶节点，检查所有的entry E ，看EI 是否与S 有重叠，如果有，E就是一个满足条件的entry.

2.3 插入

为一个新的数据 tuple 插入一个索引记录，是指在叶节点增加一个新的索引记录，如果这个节点溢出（子节点数目大于 M ），则将这个节点进行 split ，然后更新树。

2.4 插入算法

  1. 为新记录找一个合适的位置。调用 ChooseLeaf 来选择一个叶节点 L 用于存放 E；
  2. 将记录增加到叶节点。如果 L 有空间（既它的子节点个数小于 M ），将 E 放大 L 中。否则，调用 SplitNode 获得 L 和 LL （其中 L 和 LL 是将 L 进行 split 后的结果，这 2 个新节点中包含了 L 中原来的所有节点和新节点 E ）；
  3. 在节点 L 上调用 AdjustTree 。如果进行了 split ， LL 也作为一个参数；
  4. 如果节点的 split 导致了根节点的 split ，则创建一个新的根节点，这个节点的子节点是原来的根节点和 split 后的节点；

2.5 选择叶节点算法

选择一个叶节点，用于存放新的索引记录 E：

  1. 将 N 作为根节点；
  2. 如果 N 是叶节点，则返回 N；
  3. 如果 N 不是叶节点，选择 N 的子节点 F 。选择的 F 具有这样的性质。如果将 EI 包含到 FI中， FI 的面积增加的最少；
  4. 将 N 作为子节点，重复调用 CL2 和 CL3；

2.6 调整树算法

从叶节点 L 到根节点，进行调整：

  1. 令 N=L ，如果 L 之前进行过 split ，令 NN 作为另外一个新的节点（ LL ）；
  2. 如果 N 是根节点，停止；
  3. 调整父节点的覆盖矩形。让 P 作为节点 N 的父节点，并且让 EN 作为 P 中 N 的 entry 。调整 ENI ，使其能够恰好 ( 不要有太多没用的空间 ) 包含矩形 N 中所有的 entry ；
  4. 如果 L 进行了 split ，创建一个新的 entry ENN ， ENNP 指向 NN ， ENNI 包含 NN 中所有的矩形。如果 N 的父节点 P 有空间，则将 ENN 放入到 P 中；否则，调用 SplitNode 算法，将 P 进行 split ，得到 P 和 PP ，他们包含了 ENN 和 P 中原来的所有 entry；
  5. 令 N=P NN=PP （如果有 split ），重复从 AT2 的过程；

2.7 节点 split 算法

为了在一个已经满的节点中增加一个新的节点，必须将这个节点进行 split 。 Split 就是将这M+1 个子结点从新进行分配到 2 个新的节点中。进行 split 后的结果应该这样，在后面对某个节点的搜索中，尽可能不要在两个新父节点中都进行搜索（既 split 后，尽量保证原来的每个节点只属于其中的某一个父节点）。

在搜索中是否搜索某一个节点，是有这个节点的矩形是否和待搜索矩形有重叠来决定的，因此，split 后的两个矩形的覆盖面积应该最小。

2.8 Split 算法

一是穷举法。显然不合适。

二是时间复杂度为平方的近似算法。这个算法试图找到一个面积和最小的 split ，但不保证会找的到。算法先从 M+1 个 enrty 中挑出两个作为 2 个新 group 的第一个元素。

这两个 entry 的选择是这样的：如果将这两个 entry 放到同一个 group 的话，所需要的矩形面积最大。然后每一步再对剩余的 entry 进行分组，每个元素放到一个 group 中。在每一步中，计算将每个 entry 放入到每个group 后的面积增加值，然后将差值最大的 entry 进行分配。

2.8.1 平方级 split

将 M+1 个 entry 分配到两个 group 中：

  1. 为每个 group 选择第一个 entry 。利用算法 PickSeeds 来选择最初的两个 entry ，并将他们分配到不同的 group 中；
  2. 检查是否结束。如果所有的 entry 都已经分配了，停止。如果一个 group 拥有的 entry 比较多，那么要将剩余的 entry 分配到另外一个 group( 为了保证 >=m)；
  3. 调用算法 PickNext 来将下一个 entry 进行分配。将该 entry 分配到面积增加最小的组中。重复第二步；
2.8.2 选择第一个元素算法
  1. 对于每一对 entry ： E1 和 E2 ，计算包含 E1I 和 E2I 的矩形 J 的面积，令 d=area(J)-area(E1I)-area(E2I)；
  2. 选择 d 最大的作为初始元素；
2.8.3 选择下一个元素
  1. 对于每一个没有分配到 group 中的 entry E ，计算 将 EI 放到 group1 中后的面积增加值 d1，d2 类似计算d1、d2差值的绝对值：d = |d1 - d2|
  2. 选择d最大的entry；
显示全文