R 树
R 树可以用来处理高维空间信息，与B 树/B+ 树有着类似的数据结构，看起来更像是B+ 树在高维空间的扩展。笔记中除特殊说明外均以二维数据为例子。
但是笔记内容更多是R* 树。
Rectangle
在R 树中，最基本的数据结构是Rectangle 矩形（在三维空间就是Cube 立方体了）。Rectangle 通过top right bottom left四条边围成。就算是一个点，也要表示为left=right, top=bottom。
R 树中所有操作判断的依据是比较矩形面积的大小。
Node
R 树只有一个root 节点，每个节点可以包含一定数量的子节点。
- 所有的数据节点都是叶子节点
- 每个节点都对应一个矩形区域，该矩形包含所有子元素
添加元素
向R 树添加元素时会查找该元素与节点矩形合并后，矩形面积增加量最小的节点。
当某个节点的子元素/节点超过允许值时，便会触发拆分动作，将该节点一分为二
- 如果这时该节点的父元素也超过最大容量，则继续拆分父元素；
- 如果根节点元素容量也超了，则新建根节点，将旧的根节点也一分为二，加入新root（这也是RTree 始终保持平衡的原因）
- R 树并不一定是满的，但始终是平衡的
拆分节点
拆分节点时需要先确定一对种子节点，然后将原节点的元素重新插入到r树中，种子节点的选择依据：
- 一次方案：选取两个间距最远的子节点作为种子节点
- 二次方案：循环遍历所有子节点，选取两两合并后面积增加量最大的一对作为种子节点
由于拆分机制的存在并可以拆分root 节点，即使原始数据分布极不均匀，也能自动平衡，保证查询效率（总是能将稀疏的子树逐渐合并）。
删除节点
删除节点时的重新插入操作使得删除操作更加灵活：
- 删除元素；
- 当父节点中元素数量小于阈值时，则暂存父结点中的元素
- 递归向上处理
- 在删除所有符合条件的节点之后，重新插入暂存的元素
查找
- 查找最近的点：直接查找矩形合并后体积增加最小的点就好了
- 相交元素：如果矩形与节点相交，则递归查询子节点，最后返回所有的值