圖形遍歷效率低？試試 R 樹
大家好，我是前端西瓜哥。
今天我們來看看 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 樹除了處理二維，還可以處理更高維度的數據，相比四叉樹更適合范圍查詢。
