R树是由Antonin Guttman于1984年的论文《R-trees: a dynamic index structure for spatialsearching》中提出的一种经典的高维空间数据结构，常用作二维以上空间数据的索引结构，用以加快空间数据的查询（时间复杂度可以达到O(logN)）,目前很多树形空间索引都是基于或者参照R树。
这里同时附上论文中提到的算法的Java实现：RTree
前置概念
R树中有3个关键的前置概念，弄懂了它们基本上弄懂了R树的大半：
1.最小外接矩形 Minimum Bounding Rectangle（ 以下简称 MBR）
由于二维及以上的空间数据大多都是不规则的，如果直接对其进行数据建模和数据运算则会比较复杂，所以引入MBR的概念：MBR即能够完全包裹住空间数据对象的最小矩形,如下图(b)中的R8就是月牙形空间数据对象的最小外接矩形。
2.R Tree Node
R树节点，节点中存储得有多个R Tree Entry，R树节点的MBR是包裹该节点里面所有Entry MBR的MBR
3.R Tree Entry
R树节点中存储的数据对象，叶节点中的R Tree Entry存储的是指向具体数据的指针，非叶节点中的R Tree Entry存储的是指向其子节点的指针。
以上原图（非标红部分）来自R树论文原文
如上图所示，图（a）中 R 树节点中每一个Entry都对应着图（b）中的一个MBR
- 如果Entry指向的是具体的数据（该Entry在叶节点中），则该Entry的MBR是对应空间数据的MBR，如图（a）中Entry
R8的MBR是图（b）中月牙形二维空间数据的MBR。 - 如果Entry指向的是其子节点（该Entry在非叶节点中），则该Entry的MBR是其子节点的MBR，即包裹其子节点里面所有Entry MBR的MBR，如图（a）中Entry R3的MBR是图（b）中包裹R8、R9、R10的MBR。
利用 R 树索引进行搜索
利用 R 树索引进行搜索需要给定一个搜索矩形（即空间范围查询），如下图的红色矩形所示。
搜索算法返回MBR与搜索矩形有交叠的数据，如下图搜索示例返回被R15包裹的空间数据和被R16包裹的空间数据。
搜索算法也很简单，搜索步骤归纳如下：
1.从根节点开始，遍历R树节点并进行检查：
- 如果当前检查节点是非叶节点，检查节点内的每一个Entry MBR是否与搜索矩形相交，如果是，则继续检查该Entry指向的子节点，否则直接剪枝
- 如果当前检查节点是叶节点，检查节点内的每一个Entry MBR是否与搜索矩形相交，如果是，则将该Entry指向的数据加入结果集，否则直接跳过该Entry
2 遍历结束之后之间返回结果集即可
如上图的搜索示例，由于搜索矩形与根节点中R1的MBR就不相交，所以可以直接对R1及其子树进行剪枝，一下子就排除了R1，R3，R4，R5，R8，R9，R10，R11，R12，R13，R14这些Entry，避免了很多无效的搜索。
然后由于搜索矩形与根节点中R2的MBR相交，则继续对R2指向的子节点进行检查，R2子节点中的R6和R7的MBR都与搜索矩形相交，继续向下搜索，R15和R16与搜索矩形相交且处在叶节点，将R15和R16指向的数据加入结果集；R7指向的子节点中的R17，R18，R19都没有与搜索矩形相交叠，直接跳过，至此搜索完毕，返回结果集，结果集中包含R15和R16指向的数据。
从二维向更高维度扩展
上面使用最简单的二维数据作为示例进行讲解，那如果空间数据的维度大于二维该如何处理呢？
R树维度的扩展主要在于最小外接矩形的扩展，比如三维，还比较好理解，将最小外接矩形扩展为最小外接长方体即可，但是如果维度是4维、5维甚至更高维呢？按照上面的思路可能会难以理解三维以上的维度，所以解决三维以上维度的扩展就要从最小外接矩形的本质下手了：
在二维平面中，最小外接矩形实际上是从长和宽两个维度对二维空间数据进行了上下界的限定，如下图所示：
观察上图不难发现，对于一个n维的空间数据，如果我能在每一个维度都找到一个向量，该向量定义了该空间数据在这个维度上的上界和下界，那么我就可以找到一个最小的 “n维体” 将这个n维空间数据恰好包裹住
即如果要将R树向更高维度扩展的话，用上述方法找到n维数据对应的最小外接 “n维体” 即可，具体细节可以看我Github上的代码实现: https://github.com/Morgan279/R-Tree。
More Content
以上就是R树中最为核心的内容，如果还想继续了解R树的插入、更新、删除、节点分裂等更为细节的内容，可以阅读论文原文：《R-trees: a dynamic index structure for spatialsearching》
同时也可以参考我Github上开源的R树实现代码：RTree, 里面我用Java实现了论文中提到的所有算法。
转载：https://blog.csdn.net/qq_36456827/article/details/112632540