大家好,我是前端西瓜哥。
今天我们来看看 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.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 树除了处理二维,还可以处理更高维度的数据,相比四叉树更适合范围查询。