Terry Yao's Blog

algorithmsKD-Tree / R-Tree / Interval Tree 空間索引：找最近，也找重疊
algorithms

KD-Tree / R-Tree / Interval Tree 空間索引：找最近，也找重疊

閱讀時間約 9 分鐘

在一維世界，「找最近的數字」用二分搜尋；在二維、三維世界，你需要空間索引。

暴力解的極限

給你 100 萬個餐廳的 GPS 座標，用戶打開 App，你要找最近的 5 家。

暴力：計算用戶位置和 100 萬個餐廳的距離，排序，取前 5。每次查詢 O(n)，100 萬次查詢就是 10^12 次運算——不現實。

一維的問題可以用 BST 解決：把所有數排序，二分搜尋找最近。二維的問題不能直接這樣做，因為「近」是同時在 x 和 y 方向上的概念——你沒辦法用單一維度的排序表達二維的鄰近關係。

KD-Tree：交替切分空間

KD-Tree 的核心思路：把空間遞迴地切成兩半，每層輪流用不同的維度切。

2D 點集：(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)
 
深度 0，按 x 軸切（中位數 x=7）：
  左側：x < 7 → {(2,3), (5,4), (4,7)}
  右側：x ≥ 7 → {(9,6), (8,1), (7,2)}
 
深度 1，按 y 軸切（各自取中位數）：
  左側中 y 中位數 = 4，再分兩群...
 
建樹後，每個節點知道「我這邊的超平面是 x = 7」

查詢最近鄰的關鍵技巧是剪枝：

void nearestNeighbor(Node node, Point target, int depth) {
    if (node == null) return;
 
    // 更新候選最近點
    if (distance(node.point, target) < bestDist) {
        bestDist = distance(node.point, target);
        bestPoint = node.point;
    }
 
    // 先搜目標所在的那一側（較可能有近點）
    int axis = depth % k;
    Node near = target.coords[axis] < node.point.coords[axis] ? node.left : node.right;
    Node far  = (near == node.left) ? node.right : node.left;
 
    nearestNeighbor(near, target, depth + 1);
 
    // 剪枝：若超平面距離 > 當前最短距離，far 那側不可能有更近的點
    double planeDist = Math.abs(target.coords[axis] - node.point.coords[axis]);
    if (planeDist < bestDist)
        nearestNeighbor(far, target, depth + 1);
}

剪枝讓平均查詢時間從 O(n) 降到 O(log n)——但這個保證只在維度 k 很小時成立。

同一棵樹順手還能做範圍查詢（「這個矩形框裡有哪些點」）：節點的分割值整段落在範圍外就剪掉，否則遞迴兩側。複雜度攤開來是這樣：

操作平均最壞
建樹（取中位數分割）O(n log n)O(n log n)
最近鄰搜尋O(log n)O(n)
範圍搜尋（回傳 m 個點）O(√n + m)O(n)

最壞那欄不是嚇人用的——它正是下面「維度詛咒」發作時的樣子。

維度詛咒

KD-Tree 有個根本限制：維度越高，剪枝越沒效。

直覺理解：在二維空間，一個圓圈能切掉大片不相關的區域。在 100 維空間，你的「超球體」幾乎碰到每一個超平面——剪枝幾乎無效，查詢退化到 O(n)。

維度 k 和 KD-Tree 效率的關係：
  k ≤ 10：效果好，推薦使用
  k ≤ 20：可用，但效率下降明顯
  k > 20：幾乎和暴力一樣差，改用 ANN（Approximate Nearest Neighbor）

高維場景（機器學習的 embedding 搜尋、向量資料庫）通常用 HNSW 或 LSH 等近似演算法。

R-Tree：資料庫的選擇

KD-Tree 適合點資料；地理資訊系統還有另一種需求——查詢「和這個多邊形重疊的所有區域」。

R-Tree 的思路不是切分空間，而是把相鄰的物件包進 Bounding Box（最小包圍矩形），形成一棵樹：

R-Tree：
  葉節點：實際的地理物件（點、線、多邊形）
  內部節點：包圍子節點的 Minimum Bounding Rectangle（MBR）
 
查詢「這個矩形範圍內有哪些物件」：
  1. 從根開始，跳過和查詢範圍不相交的 MBR
  2. 遞迴下去，只進入相交的子樹
  3. 葉節點做精確判斷

PostGIS（PostgreSQL 的地理擴展）內建 R-Tree 索引（實作為 GiST）；MySQL 的 SPATIAL INDEX 也是 R-Tree。

KD-Tree vs R-Tree

KD-TreeR-Tree
資料類型點點、線段、多邊形
查詢類型最近鄰、範圍範圍、重疊
維度k ≤ 10通常 2D-3D
適用場景KNN 搜尋、遊戲碰撞GIS、地圖查詢、資料庫

GPS app 找最近的餐廳用 KD-Tree 或 R-Tree 都行；PostGIS 的「台北市內的所有餐廳」查詢用 R-Tree 更自然，因為「台北市」本身是個多邊形，不是一個點。

Interval Tree：不是找最近，是找重疊

前面兩棵樹都在回答「哪個點離我最近」。但有一類問題長得不一樣：你手上有一堆「有頭有尾的時段」，想知道跟某個新時段撞到的是哪幾個。

最典型的就是訂會議室。你要借 9:00–10:00，系統得馬上告訴你這段跟哪些既有預約衝突。基因序列的區段重疊、線段相交偵測，本質上都是同一題。暴力做法是把 n 個區間逐一比對，O(n)；Interval Tree 能做到 O(log n) 找到第一個重疊、O(k log n) 撈出全部 k 個。

它的做法很省事：拿一棵平衡 BST（例如紅黑樹），用區間左端點當排序鍵，然後給每個節點多掛一個欄位 max——這棵子樹裡所有區間右端點的最大值。

插入 [16,21] [8,9] [25,30] [5,8] [15,23] [0,3] [6,10]
 
        [16,21] max=30
       /             \
   [8,9] max=23    [25,30] max=30
   /        \
[5,8]     [15,23]
max=10    max=23
 /  \
[0,3] [6,10]
max=3 max=10
 
key = 左端點（BST 排序依據）
max = 子樹內所有右端點的最大值

那個 max 就是整棵樹的靈魂，它讓你敢整段子樹跳過：

Interval overlapSearch(Node node, Interval q) {
    if (node == null) return null;
 
    // 和當前節點重疊就直接回傳
    if (overlaps(node.interval, q)) return node.interval;
 
    // 剪枝：左子樹的 max < q.low，左邊所有右端點都太小，不可能重疊
    if (node.left != null && node.left.max >= q.low)
        return overlapSearch(node.left, q);
 
    return overlapSearch(node.right, q);
}
 
boolean overlaps(Interval a, Interval b) {
    return a.low <= b.high && b.low <= a.high;
}

剪枝那行是關鍵：如果左子樹的 max 都還小於查詢區間的左端 q.low，代表左邊每一個區間都整段躺在 q 的左側、碰不到，直接不進去。這一刀砍掉半棵樹，就是 O(n) 掉到 O(log n) 的來源。插入或刪除後，記得從改動點沿路往上把 max 重算回去——它是 max(自己的右端, 左子樹 max, 右子樹 max)。

操作時間
插入 / 刪除O(log n)
找第一個重疊O(log n)
找所有 k 個重疊O(k log n)

放在一起看，這三棵樹其實共用一個念頭：KD-Tree 靠超平面剪、R-Tree 靠包圍盒剪、Interval Tree 靠 max 剪——差別只在資料是點、是框、還是一段區間。

🎬 互動視覺化：空間分割與區間重疊三合一 — 自己丟點看 KD-Tree 怎麼交替切軸、丟區間看 Interval Tree 的 max 怎麼一路剪掉半棵樹，「不可能是答案就別看」的手法在畫面上一目了然。

空間索引的核心思路是：不要掃全部，用分割讓「不可能是答案」的區域提前排除。

接下來往哪走

關係圖譜

反向連結