大家好，我是前端西瓜哥。
今天我们来看看 R 树是什么？以及它为什么能够提高图形的检索速度。
R 树（R-tree）是一种 空间索引技术，能够是从大量的节点中，快速找到特定范围的元素集合，而不用一个不落地遍历所有节点。
思路和其他索引算法（比如 B 树、跳表）有点像，但 R 树针对的是高维数据的查询 。R 树的 “R” 指的是矩形（Rectangle）。
举个具体的例子，假设有一张地图，上面有几百万个节点，要快速找某个位置半径 2 公里的所有餐馆的信息。
低效的做法是遍历这几百万的节点的位置，判断距离是否小于 2 公里。
但如果用上索引技术，比如 R 树，我们就能利用索引去 空间换时间，快速拿到特定范围的节点超集，比如几千个。
接着只需要遍历这几千个节点去判断符合条件的节点就可以了，而不需要完完整整遍历所有的节点。
除此之外还可以：
- 快速检索平面中和选区矩形相交的二维图形；
- 在数据库中快速找出多维度的产品，比如价格、库存、过期时间在特定范围的商品。
R 树的数据结构
下面看一下在图形编辑器的一个场景。
我们构建了一棵图形树，图形树的图形有位置、宽高等属性，并渲染在画布上。
需要实现选择功能，绘制一个矩形选区，使和该选区矩形相交的图形高亮。
为实现这个能力，我们计算图形树上的每个图形的包围盒：一个用 minX，minY、maxX、maxY 表达的一个矩形，它刚好包围住图形。
包围盒的作用是简化碰撞算法，一些复杂的图形，比如贝塞尔曲线，如果要严格意义上判断碰撞，是要进行复杂的计算的，在有大量图形的场景下，性能非常糟糕。
所以业内常用矩形包围盒的碰撞来简化，这种算法非常简单高效，可直接用来替代原本复杂精细的碰撞检测，或是在进行复杂碰撞算法前先做一层过滤，避免无谓的复杂运算。
// 矩形是否相交
function intersects(a, b) {
return b.minX <= a.maxX &&
b.minY <= a.maxY &&
b.maxX >= a.minX &&
b.maxY >= a.minY;
}
这个包围盒特点，就很适合拿来应用 R 树来提高图形树的 检索效率。
R 树的数据结构是一个平衡树。
和其他索引树类似，R 树的叶子节点是数据节点，保存有图形信息和它的最小包围矩形（MBR）。
最小包围矩形其实就是包围盒。
结构大概类似这样：
{
minX: 20,
minY: 40,
maxX: 30,
maxY: 50,
// 保存图形数据，比如图形对象 id，或图形对象本身
data: {}
};
R 树会将距离相近的数据节点收集起来，并放到同一个父节点下。这个父节点是 索引节点，不会保存图形信息，但会记录子节点的合并的包围盒数据。
父节点如果多了，也会把它们收集起来，放到一个新的父节点下。
这样就形成了一个树的结构。
实际生产环境，推荐使用一个名为 RBush 的高性能 NPM 库。
代码用法示例：
import RBush from "rbush";
// 创建一个 R 树实例
const tree = new RBush();
// 也可以指定一个索引节点最多有几个子节点，默认是 9 个
const tree2 = new RBush(16);
R 树的检索
检索的过程如下：
提供一个选区矩形，从根节点开始，往下递归查找判断选取矩形是否和当前节点矩形相交。
- 若不相交，其下的节点也不会相交，该节点对应的子树就不需要继续递归了；
- 若相交且为数据节点（叶子节点），将其放到 result 数组；
- 若是包含关系，其下的所有数据节点放到 result 数组；
- 若相交但并不包含，则遍历其下的的子节点，重复前面的操作。
直到可能相交的节点遍历完结束，然后返回 result 数组。
RBush 的搜索写法：
const result = tree.search({
minX: 20,
minY: 20,
maxX: 80,
maxY: 70,
});
其源码实现：
class RBush {
// ...
search(bbox) {
let node = this.data;
const result = [];
if (!intersects(bbox, node)) return result;
const toBBox = this.toBBox;
const nodesToSearch = [];
while (node) {
for (let i = 0; i < node.children.length; i++) {
const child = node.children[i];
const childBBox = node.leaf ? toBBox(child) : child;
if (intersects(bbox, childBBox)) {
// 1. 遍历到数据节点
if (node.leaf) result.push(child);
// 2. 索引节点
// 2.1. 包含关系，索引节点下的所有数据节点都加进 result
else if (contains(bbox, childBBox)) this._all(child, result);
// 2.2. 相交不包含关系，继续判断相交
else nodesToSearch.push(child);
}
}
node = nodesToSearch.pop();
}
return result;
}
_all(node, result) {
const nodesToSearch = [];
while (node) {
if (node.leaf) result.push(...node.children);
else nodesToSearch.push(...node.children);
node = nodesToSearch.pop();
}
return result;
}
}
R 树的更新
1、初始化
在图形编辑器初始化的时候，我们要计算图形树所有图形的包围盒，然后插入到 R 树上。
RBush 插入单个节点的写法：
const item = {
minX: 20,
minY: 40,
maxX: 30,
maxY: 50,
graphId: '123',
};
tree.insert(item);
支持批量插入节点，RBush 针对批量添加做了优化，效率比单个插入更高。
tree.load([item1, item2, /* ... */]);
2、更新
R 数作为索引数据，是要实时更新。
为此，我们需在每次图形物理属性改变的时候，重新计算包围盒，并更新 R 树。
tree.remove(item);
tree.insert(newItem);
四叉树（Quadtree）
还有一种同样可以减少遍历节点数量的算法，叫做 四叉树（Quadtree）碰撞检测。
四叉树将视口界面分割成多个区域，每个区域记住自己包含了哪些图形。
然后移动目标图形时，判断它落在哪个区域，取出所在区域的图形，这些图形集合就是和目标图形发生碰撞图形的超集。
当一个区域的图形数量过多时，又会进行分裂，再次分成 4 个区域。
四叉树详细讲解可以看我的这篇文章：
《快速检索碰撞图形：四叉树碰撞检测》
四叉树更适合图形均匀分布的场景，如果不均匀，会产生大量空节点，且查询效率会降低。
R 树除了处理二维，还可以处理更高维度的数据，相比四叉树更适合范围查询。
结尾
我是前端西瓜哥，欢迎关注我，学习更多图形知识。
