KD-Tree & R-Tree 空間索引：找最近的那個點

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

暴力解的極限

給你 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 很小時成立。

維度詛咒

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

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

---

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