大家好，我是前端西瓜哥。

今天我們來看看 R 樹是什么？以及它為什么能夠提高圖形的檢索速度。

R 樹（R-tree）是一種 空間索引技術(shù)，能夠是從大量的節(jié)點(diǎn)中，快速找到特定范圍的元素集合，而不用一個不落地遍歷所有節(jié)點(diǎn)。

思路和其他索引算法（比如 B 樹、跳表）有點(diǎn)像，但 R 樹針對的是高維數(shù)據(jù)的查詢 。R 樹的 “R” 指的是矩形（Rectangle）。

舉個具體的例子，假設(shè)有一張地圖，上面有幾百萬個節(jié)點(diǎn)，要快速找某個位置半徑 2 公里的所有餐館的信息。

低效的做法是遍歷這幾百萬的節(jié)點(diǎn)的位置，判斷距離是否小于 2 公里。

但如果用上索引技術(shù)，比如 R 樹，我們就能利用索引去 空間換時間，快速拿到特定范圍的節(jié)點(diǎn)超集，比如幾千個。

接著只需要遍歷這幾千個節(jié)點(diǎn)去判斷符合條件的節(jié)點(diǎn)就可以了，而不需要完完整整遍歷所有的節(jié)點(diǎn)。

除此之外還可以：

• 快速檢索平面中和選區(qū)矩形相交的二維圖形；
• 在數(shù)據(jù)庫中快速找出多維度的產(chǎn)品，比如價格、庫存、過期時間在特定范圍的商品。

R 樹的數(shù)據(jù)結(jié)構(gòu)

下面看一下在圖形編輯器的一個場景。

我們構(gòu)建了一棵圖形樹，圖形樹的圖形有位置、寬高等屬性，并渲染在畫布上。

需要實(shí)現(xiàn)選擇功能，繪制一個矩形選區(qū)，使和該選區(qū)矩形相交的圖形高亮。

為實(shí)現(xiàn)這個能力，我們計算圖形樹上的每個圖形的包圍盒：一個用 minX，minY、maxX、maxY 表達(dá)的一個矩形，它剛好包圍住圖形。

包圍盒的作用是簡化碰撞算法，一些復(fù)雜的圖形，比如貝塞爾曲線，如果要嚴(yán)格意義上判斷碰撞，是要進(jìn)行復(fù)雜的計算的，在有大量圖形的場景下，性能非常糟糕。

所以業(yè)內(nèi)常用矩形包圍盒的碰撞來簡化，這種算法非常簡單高效，可直接用來替代原本復(fù)雜精細(xì)的碰撞檢測，或是在進(jìn)行復(fù)雜碰撞算法前先做一層過濾，避免無謂的復(fù)雜運(yùn)算。

// 矩形是否相交
function intersects(a, b) {
  return b.minX <= a.maxX &&
         b.minY <= a.maxY &&
         b.maxX >= a.minX &&
         b.maxY >= a.minY;
}

這個包圍盒特點(diǎn)，就很適合拿來應(yīng)用 R 樹來提高圖形樹的 檢索效率。

R 樹的數(shù)據(jù)結(jié)構(gòu)是一個平衡樹。

和其他索引樹類似，R 樹的葉子節(jié)點(diǎn)是數(shù)據(jù)節(jié)點(diǎn)，保存有圖形信息和它的最小包圍矩形（MBR）。

最小包圍矩形其實(shí)就是包圍盒。

結(jié)構(gòu)大概類似這樣：

{
  minX: 20,
  minY: 40,
  maxX: 30,
  maxY: 50,
  // 保存圖形數(shù)據(jù)，比如圖形對象 id，或圖形對象本身
  data: {}
};

R 樹會將距離相近的數(shù)據(jù)節(jié)點(diǎn)收集起來，并放到同一個父節(jié)點(diǎn)下。這個父節(jié)點(diǎn)是 索引節(jié)點(diǎn)，不會保存圖形信息，但會記錄子節(jié)點(diǎn)的合并的包圍盒數(shù)據(jù)。

父節(jié)點(diǎn)如果多了，也會把它們收集起來，放到一個新的父節(jié)點(diǎn)下。

這樣就形成了一個樹的結(jié)構(gòu)。

實(shí)際生產(chǎn)環(huán)境，推薦使用一個名為 RBush 的高性能 NPM 庫。

代碼用法示例：

import RBush from "rbush";

// 創(chuàng)建一個 R 樹實(shí)例
const tree = new RBush();

// 也可以指定一個索引節(jié)點(diǎn)最多有幾個子節(jié)點(diǎn)，默認(rèn)是 9 個
const tree2 = new RBush(16);

R 樹的檢索

檢索的過程如下：

提供一個選區(qū)矩形，從根節(jié)點(diǎn)開始，往下遞歸查找判斷選取矩形是否和當(dāng)前節(jié)點(diǎn)矩形相交。

• 若不相交，其下的節(jié)點(diǎn)也不會相交，該節(jié)點(diǎn)對應(yīng)的子樹就不需要繼續(xù)遞歸了。
• 若相交且為數(shù)據(jù)節(jié)點(diǎn)（葉子節(jié)點(diǎn)），將其放到 result 數(shù)組。
• 若是包含關(guān)系，其下的所有數(shù)據(jù)節(jié)點(diǎn)放到 result 數(shù)組。
• 若相交但并不包含，則遍歷其下的子節(jié)點(diǎn)，重復(fù)前面的操作。

直到可能相交的節(jié)點(diǎn)遍歷完結(jié)束，然后返回 result 數(shù)組。

RBush 的搜索寫法：

const result = tree.search({
  minX: 20,
  minY: 20,
  maxX: 80,
  maxY: 70,
});

其源碼實(shí)現(xiàn)：

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. 遍歷到數(shù)據(jù)節(jié)點(diǎn)
          if (node.leaf) result.push(child);
          // 2. 索引節(jié)點(diǎn)
          // 2.1. 包含關(guān)系，索引節(jié)點(diǎn)下的所有數(shù)據(jù)節(jié)點(diǎn)都加進(jìn) result
          else if (contains(bbox, childBBox)) this._all(child, result);
          // 2.2. 相交不包含關(guān)系，繼續(xù)判斷相交
          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 插入單個節(jié)點(diǎn)的寫法：

const item = {
  minX: 20,
  minY: 40,
  maxX: 30,
  maxY: 50,
  graphId: '123',
};

tree.insert(item);

支持批量插入節(jié)點(diǎn)，RBush 針對批量添加做了優(yōu)化，效率比單個插入更高。

tree.load([item1, item2, /* ... */]);

2、更新

R 數(shù)作為索引數(shù)據(jù)，是要實(shí)時更新。

為此，我們需在每次圖形物理屬性改變的時候，重新計算包圍盒，并更新 R 樹。

tree.remove(item);
tree.insert(newItem);

四叉樹（Quadtree）

還有一種同樣可以減少遍歷節(jié)點(diǎn)數(shù)量的算法，叫做 四叉樹（Quadtree）碰撞檢測。

四叉樹將視口界面分割成多個區(qū)域，每個區(qū)域記住自己包含了哪些圖形。

然后移動目標(biāo)圖形時，判斷它落在哪個區(qū)域，取出所在區(qū)域的圖形，這些圖形集合就是和目標(biāo)圖形發(fā)生碰撞圖形的超集。

當(dāng)一個區(qū)域的圖形數(shù)量過多時，又會進(jìn)行分裂，再次分成 4 個區(qū)域。

四叉樹更適合圖形均勻分布的場景，如果不均勻，會產(chǎn)生大量空節(jié)點(diǎn)，且查詢效率會降低。

R 樹除了處理二維，還可以處理更高維度的數(shù)據(jù)，相比四叉樹更適合范圍查詢。