查看“树：R树”的源代码

[[category:数据结构]]

== 关于 ==


== 空间数据 ==
基于实体的模型：
# 0-dimensional objects：一般使用点point来表示那些对于不需要使用到形状信息的实体。
# 1-dimensional objects or linear objects：用于表示一些路网的边，一般用于表示道路road。 (polyline)
# 2-dimensional objects or surfacic objects：用于表示有区域面积的实体。 (polygon)


常用的空间数据查询方式：
# 窗口查询：给定一个查询窗口（通常是一个矩形），返回与查询窗口相重叠的物体。
# 点查询：给定一个点，返回包含这个点的所有几何图形。

=== 空间数据获取的方法 ===
通常，我们不选择去索引几何物体本身，而是采用“最小限定箱”（MBB：minimum bounding box）作为不规则几何图形的 key 来构建空间索引：
# 二维：称之为“'''最小限定矩形'''”（'''MBR'''：minimum bounding retangle）。
#: [[File:“最小限定矩形”（MBR：minimum bounding retangle）.png|200px]]
# 三维：称之为“最小限定箱”（MBB：minimum bounding box）。
#: [[File:“最小限定箱”（MBB：minimum bounding box）.png|200px]]


通过索引操作对象的 MBB 进行查询，步骤：【？？？】
# Filtering：过滤掉 MBB 不相交的数据集，剩下的 MBB 被索引到的称为一个数据的超集。
#: [[File:通过索引操作对象的 MBB 进行查询：Filtering.png|200px]]
# Refinement：测试实际的几何形状会不会满足查询条件，精确化。
#: [[File:通过索引操作对象的 MBB 进行查询：Refinement.png|200px]]


使用：
# 用数据表示一个 MBR：
#: 通常，只需要两个点就可限定一个矩形，也就是矩形某个对角线的两个点（“左下右上”或“左上右下”）就可以决定一个唯一的矩形。
#: [[File:用数据表示一个 MBR.png|200px]]
## 表示一个点的数据：
#: <syntaxhighlight lang="mysql">
　　　　public class Point{ //用一个类来表示一个点
　　　　    public Float x;
　　　　    public Float y
　　　　}
</syntaxhighlight>
## 表示一个 MBR 的数据：
#: <syntaxhighlight lang="mysql">
　　　　public class MBR{
　　　　    public Point BottomLeft;
　　　　    public Point TopRight;
　　　　}
</syntaxhighlight>
# 判断两个 MBR 是否相交：
#:  如果一个MBR的TopLeft或者BottomRight的（x，y）位于另一个MBR的 xRange 和 yRangle 里面，则说明这两个MBR相交。
#:  [[File:判断两个MBR是否相交.png|200px]]

== R树 ==
=== 简介 ===
R树 是 B树 在高维空间的扩展：采用 B树 分割空间的思想，并在添加、删除操作时采用合并、分解结点的方法，保证树的平衡性。因此，R树就是一棵用来'''存储高维数据的平衡树'''。
: 每个 R树 的叶子结点包含了多个指向不同数据的指针，这些数据可以是存放在硬盘中的，也可以是存在内存中。
: 根据 R树 的这种数据结构，当需要进行一个高维空间查询时，只需要遍历少数几个叶子结点所包含的指针，查看这些指针指向的数据是否满足要求即可。

<pre>
1984年，加州大学伯克利分校的Guttman发表了一篇题为“R-trees: a dynamic index structure for spatial searching”的论文，向世人介绍了R树这种处理高维空间存储问题的数据结构。
* Guttman, A.; “R-trees: a dynamic index structure for spatial searching,” ACM, 1984, 14
</pre>

R树在现实领域中能够解决的例子：查找20英里以内所有的餐厅。
# 如果没有 R树 怎么解决？
#: 一般情况下我们会把餐厅的坐标“(x,y)”分为两个字段存放在数据库中，一个字段记录经度，另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息，然后计算是否满足要求。
#: 如果一个地区有100家餐厅的话，我们就要进行100次位置计算操作了，如果应用到谷歌地图这种超大数据库中，这种方法便必定不可行了。
# R树 的解决？
#: R树采用了一种称为“'''MBR'''”（Minimal Bounding Rectangle，即'''最小边界矩形'''）的方法对空间进行分割……
#: R树 使我们不必遍历所有数据即可获得答案，效率显著提高。
#: 如下：

=== 引子 ===
R树 示例：
:[[File:R树：一个实例1.png|300px]]
R树 采用了一种称为“MBR”对空间进行分割：从叶子结点开始用矩形（rectangle）将空间框起来，结点越往上，框住的空间就越大，以此对空间进行分割。


“MBR”分割示例：（假设所有数据都是二维空间下的点）
:[[File:R树：一个实例2.png|400px]]
# 如图，“shape of data object”所标记的是一块不规则图形，我们把它看作是多个数据围成的一个区域。为了实现“R树”结构，用一个最小边界矩形恰好框住这个不规则区域，这样就构造出了一个区域：“R8”。
#: 其他实线包围住的区域（“R8”到“R19”）同理。【这些矩形都将被存储在页子结点】
# 如图，可以发现“R8”，“R9”，“R10”三个矩形距离最为靠近，因此就可以用一个更大的矩形“R3”恰好框住这 3 个矩形。【叶子节点的父节点】
#: 同理：“R15”，“R16”被“R6”恰好框住；“R11”，“R12”被“R4”恰好框住，等等。
# 重复上一步，所有最基本的最小边界矩形被框入更大的矩形中之后，再次迭代，用更大的框去框住这些矩形。
最后，根结点存放的是两个最大的矩形，这两个最大的矩形框住了所有的剩余的矩形，当然也就框住了所有的数据。

* 下一层的结点存放了次大的矩形，这些矩形缩小了范围。
* 每个叶子结点都是存放的最小的矩形，这些矩形中可能包含有n个数据。


对应于地图的情况：
# 打开地图（也就是整个R树），先选择国内还是国外，【对应根结点】
# 然后选择华南地区（对应第一层结点），选择广州市，【对应第二层结点】
# 再选择天河区，【对应第三层结点】
# 最后选择天河城所在的那个区域。【对应叶子结点，存放有最小矩形】
如图：
: [[File:R树：对应于地图.png|400px]]

=== 定义（性质） ===
----
# 非根非叶子结点拥有“'''m/2'''”至“'''m'''”个子结点（子树）。
# 叶子结点包含有“'''m/2'''”至“'''m'''”个记录索引（条目）。
#* 作为根结点的叶子节点所具有的记录个数可以少于“m/2”。
# 对于节点（叶子、非叶子节点）的所有记录（条目），“'''I'''”是最小的可以在空间中完全覆盖这些记录所代表的点的矩形（“矩形”是可以扩展到高维空间的）。
# '''所有叶子结点都位于同一层'''，因此 R树 为平衡树。
*【条目个数 = 子结点个数】

=== 结构 ===
----
如图，“R树的节点存储结构”：
: [[File:R树：节点存储结构.png|400px]]

==== 叶子结点 ====
叶子结点所保存的数据形式为：“'''(I, tuple-identifier)'''”，其中：
# “'''I'''”：是一个 n 维空间的'''矩形'''，并可以恰好框住这个叶子结点中所有记录代表的 n 维空间中的点。【框住点的最小矩形，如引子中的“R8”】
#: 如：“I=(I0,I1,…,In-1)”。
# “'''tuple-identifier'''”：表示的是一个存放于数据库中的 tuple（'''多元组'''），也就是一条记录，它是 n 维的。【所有的点，如引子中构成“shape of data object”的'''所有点是一个条目'''】


示例，在二维空间中的叶子结点所要存储的信息：
: [[File:R树：在二维空间中的叶子结点所要存储的信息.png|400px]]
如图，
# “I”所代表的就是图中的矩形，其范围是“a<=I0<=b”，“c<=I1<=d”。
# “tuple-identifier”，在图中即表示为那两个点。
* 这种形式完全可以推广到高维空间。

==== 非叶子结点 ====
非叶子结点存放的数据结构为：“(I, child-pointer)”，其中：
# “'''I'''”：覆盖所有孩子结点对应矩形的'''矩形'''。【框住所有孩子节点矩形的最小矩形，如如引子的“R3”】
#: 如：“I=(I0,I1,…,In-1)”。
# “'''child-pointer'''”：表示指向孩子结点的'''指针'''。

== R树操作 ==
=== 搜索 ===
----
R树 的搜索操作：【搜索内容为“矩形”，判断条件是“与节点矩形是否有重合”】
* 输入一个搜索矩形。
* 返回所有符合查找信息的记录条目。


搜索过程：
# 如果当前节点是非叶子节点：
## 若当前节点的矩形（“I”）与“搜索矩形”有重合，那么对当前节点存储条目所指向的子节点进行“搜索过程”。
## 若当前节点的矩形（“I”）与“搜索矩形”没有重合，无匹配。
# 如果当前节点是叶子节点：
## 若当前节点的矩形（“I”）与“搜索矩形”有重合，返回当前节点存储条目中符合条件的记录。
## 若当前节点的矩形（“I”）与“搜索矩形”没有重合，无匹配。


示例：
: [[File:R树：搜索操作：示例.png|400px]]
红色查询区域，与“P3”子树“P4”子树相重叠，所以根据“缩小空间”的思想，只需要遍历“P3”和“P4”所在子树就行而无需遍历“P1”，“P2”。

=== 插入 ===
----
R树 的插入操作也同 B树 的插入操作类似：
: 当新的数据记录需要被添加入叶子结点时，若叶子结点溢出，那么我们需要对叶子结点进行分裂操作。
* 叶子结点的插入操作会比搜索操作要复杂。
* 插入操作需要一些辅助方法才能够完成。


插入过程：
# 查找合适插入的叶子结点：（从根节点开始）
## 如果当前节点不是叶子节点：则遍历节点的子节点，找到“添加新条目时，节点矩形增量最小”的节点。
##*（如果有多个这样的结点，那么选择面积最小的结点）
## 如果当前节点为叶子结点，则直接返回当前叶子节点。
# 插入新条目至叶子节点：
## 如果叶子节点条目个数 < 最大值（“M”）：
### 插入：插入条目。
### 调整：（如果需要）
#### 扩大叶子节点矩形“I”为所有条目的“MBR”。
#### 扩大父节点矩形“I”为所有条目的“MBR”。
## 如果叶子节点条目个数 = 最大值（“M”）：
### '''分裂'''：将该叶子节点分裂为两个新的叶子节点，用于包含已有条目与新插入条目；
### 调整：（如果需要）
#### 扩大叶子节点矩形“I”为所有条目的“MBR”。
#### 扩大父节点矩形“I”为所有条目的“MBR”。
* 【如果父节点条目数引起“分裂”，则向上迭代“调整父节点矩形”过程】


示例：
# 插入空间足够，且不需扩大矩形：
#: [[File:R树：插入操作：“插入空间足够，且不需扩大矩形”.png|400px]]
# 插入空间足够，但需要扩大矩形：
#: [[File:R树：插入操作：“插入空间足够，但需要扩大矩形”.png|400px]]
# 插入空间不足，需要分裂该节点：
#: [[File:R树：插入操作：“插入空间不足，需要分裂该节点”.png|400px]]
#: 由于插入的“w”所在的区域“P1”的数据条目空间不足，所以采用'''分裂算法'''将结点“P1”分裂为“P1”（包含“A”，“B”）和“P5”（包含“k”，“w”）两个结点；
#: 分裂之后导致父节点条目数过多，需要向上传递，最终导致生成新的根结点“Q1”，“Q2”。

==== 分裂算法 ====
分类算法有多种：
: [[File:R树：常见的分裂算法.png|400px]]


以“Quadratic”方案为例，其算法：
# 选取种子条目seed：
#: [[File:R树：分裂算法“Quadratic”：选取种子条目.png|400px]]
## 从节点所有条目中挑选两个条目（E1、E2）；
## 计算两个条目的 MBR 增量：“d = MBR(E1, E2) - E1 - E2”；
## 重复以上步骤，计算每一对条目的增量，并选取增量 d 最大的一对作为种子条目。
##* 【选择增量最大，则种子条目的矩形对角线最远，分裂之后的新节点重叠可能最小】
##*: [[File:R树：分裂算法“Quadratic”：增量与分裂.png|200px]]
# 将剩下条目分配与这两个seed，使其各成为一组。
#* 【分配的原则就是离谁比较“近”就和谁一组：用增量“d1=MBR(E,seed1)-E-seed1”）与增量“d2=MBR(E,seed2)-E-seed2”的大小判断哪个近】
#*: [[File:R树：分裂算法“Quadratic”：距离判断.png|400px]]


除了上述“Quadratic”的分裂算法之外还有其他的分裂算法，但是分裂的效果都不如“'''R*树'''”（R树的改进版）的算法好。

=== 删除 ===
----

== 参考 ==
# [https://www.cnblogs.com/cmi-sh-love/p/kong-jian-shud-ju-suo-yinRTree-wan-quan-jie-xi-jiJa.html 空间数据索引RTree（R树）完全解析及Java实现]
# [https://blog.csdn.net/v_JULY_v/article/details/6530142/ 从B树、B+树、B*树谈到R 树]
# [https://zhuanlan.zhihu.com/p/62639268 什么是R树？]