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

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

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

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

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

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

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

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

除此之外還可以：

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

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

下面看一下在圖形編輯器的一個(gè)場(chǎng)景。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

代碼用法示例：

import RBush from "rbush";

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

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

R 樹的檢索

檢索的過(guò)程如下：

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

• 若不相交，其下的節(jié)點(diǎn)也不會(huì)相交，該節(jié)點(diǎn)對(duì)應(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.初始化

在圖形編輯器初始化的時(shí)候，我們要計(jì)算圖形樹所有圖形的包圍盒，然后插入到 R 樹上。

RBush 插入單個(gè)節(jié)點(diǎn)的寫法：

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

tree.insert(item);

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

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

2.更新

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

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

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

四叉樹（Quadtree）

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

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

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

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

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

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