基本概念
R 树的目的是尽可能缩小 MBR 的周长，其中 MBR 是能够完全包含一个空间对象或一组空间对象的最小矩形。
为什么不选择面积的原因在于，有可能会出现瘦长形式的长方形。
数据插入
当需要插入一个数据点时，从 root 向下查看。
- p 点位于 E6 中，因此直接不需要更改 MBR
- 后续 E1、E2、E3 应该插入到哪里呢？会根据增加到最小 MBR 来判断。
- E1 和 E2 MBR 增加 4， E3 增加 2，因此 p 点进入到 E3 中。
当如果一个节点容量满了后，则需要进行节点分割。
分割的方式就是使得分割后的两个 MBR 和最小。
最后不断向上迭代，直到不需要分割为止。
数据删除
数据删除同 B+ 树的数据删除，当上图的 E3 中 k 被删除后，E3 节点过少，剩下的 s 需要被合并。
删除 E3 节点后，E9 节点也只有一个 E2 节点，也需要被合并。
对需要合并的数据进行重插入，先插入 E2 再插入 s 数据。
搜索
提供区域 Q，查找存在于区域 Q 的坐标
从 root 节点开始，根据 MBR 交际进行递归的判断数据存在性。
查找距离 Q 坐标最近的数据
比较复杂，略。
Your connected workspace for wiki, docs & projects | Notion
空间连接
酒店 R-Tree、餐馆 R-Tree，寻找酒店于餐馆距离小于 N 的 pair 对。
Your connected workspace for wiki, docs & projects | Notion
R 树应用
ByteHouse技术详解：基于OLAP构建高性能GIS地理空间能力
当 OLAP + GIS 进行结合，ClickHouse 社区版直接按照 Order By latitude, longtitude 里面的纬度进行排序，再按照经度排序。ByteHouse GIS 在列式小批组织的数据结构上引入 RTree 等二维空间索引能力。
扩展内容
Java Topology Suite (JTS) 作为一个功能强大的空间数据处理库，为开发者提供了丰富的工具来处理复杂的空间问题。它在许多地理信息系统得到了广泛的应用。