概念地圖・k-d 樹
作者 山姆（謝冠生）・喵喵書評創辦人
發布
分類：系統
這一頁不只是把一個概念解釋一遍——一張自己畫的結構圖，加上拿台灣情境從頭走一次的實例演練、這個框架什麼時候會騙你，以及它接回 P.A.I.N. 之後長什麼樣。一頁必須交付的三層 →
k-d 樹：每切一刀，就排除一整塊不必算的點
一張正射影像攤開，上面十五座電塔。要找出離那棵倒下的樹最近的一座，工程師的做法通常很直接——量十五次，取最小。塔數翻到一萬座，這個做法就開始拖住整條流程。k-d 樹處理的是同一件事：先花一點力氣，把平面按座標軸輪流切開，切成一塊一塊；之後每問一次「最近的是哪一座」，都可以整塊整塊地排除。這張圖畫的就是那幾刀怎麼下、以及它們怎麼長成一棵樹。
每一層切哪一軸，切出什麼
同一張平面，每往下一層就換一根軸。換軸這個動作本身沒有什麼玄機，值錢的是每切一次，就有一半的點被掛在門外。
| 層 | 切哪一軸 | 拿哪一點當刀口 | 切完的局面 |
|---|---|---|---|
| 第 1 層 | x 軸，一條垂直線 | x 座標排第 8 的那一座 | 左邊 7 座、右邊 7 座，最粗的那一刀 |
| 第 2 層 | y 軸，兩條水平線 | 左右兩堆各自的 y 中位數 | 四塊矩形，每塊還剩 3 座 |
| 第 3 層 | 換回 x 軸，四條垂直線 | 四堆各自的 x 中位數 | 八塊矩形，每塊剩 1 座 |
| 葉子這一層 | 停手 | 沒有刀口 | 樹深 4 層；7 座當了節點、8 座躺在葉子裡——葉子切太碎，回溯的成本會反過來吃掉剪枝省下的 |
表上「每塊還剩 3 座」那一格，扣掉的正是當了刀口的那一座：中位數那個點留在節點上，其餘的才往下分。所以十五座的帳是 7 座站在七條切線上、8 座躺在八片葉子裡。至於「切到每塊剩 1 座」，那是這張圖為了讓八塊矩形跟八片葉子一眼對得上才切到底；實務上多半停得更早，葉子留十幾個點是常見設定——每多一層，查詢回頭要檢查的兄弟分支就多一組。
切第一刀之前要定下來的三件事
一、用哪一軸切。輪流切最省事：第 1 層 x、第 2 層 y、第 3 層回到 x，程式碼四行寫完。挑變異最大的那一軸比較聰明——空拍圖上的電塔常常沿著一條輸電線排成長條，東西向拉得很開、南北向擠成一片，這時候還在輪流切，等於有一半的刀落在幾乎沒有分散度的方向上，白切。代價是每一層都要先算一輪變異數，而且建樹時得把「這一層切了哪根軸」存進節點裡。自問：我的資料在各個維度上的分散程度，差距大到值得多花那一輪計算嗎？
二、切在哪裡。中位數保證左右一樣多，樹深壓得住，代價是每一層都要排序或做一次選取。平均數算得快，但空拍圖上只要有三、四座塔擠在角落的變電站旁邊，平均數就被它們拉過去，刀切歪，一邊分到十二座、另一邊三座。樹一歪，查詢要走的路就變長——而 k-d 樹沒有旋轉可以把它扳回來。自問：我的資料裡有沒有極端值？被它拉歪的那一刀，我要在哪一層察覺？
三、葉子裝幾個點才停。切到每片葉子只剩一座，樹最深、剪枝看起來最漂亮。但查一次最近鄰，除了往下走，還要往回爬——每經過一個節點，都要拿「這塊矩形的最近邊界」跟手上的最佳距離比一次。葉子切得越碎，這種比較就越多。一萬座塔的圖資，葉子留十幾個點、到了葉子就老實暴力比一輪，整體時間通常比切到底好看。自問：我這一批查詢，回溯的次數大約是往下走那幾步的幾倍？
一張空拍圖上的十五座電塔，走一遍
底下這位在台灣中部接電力巡檢空拍案的無人機測繪員阿凱，是為了把這個結構講清楚而編出來的示意情境，沒有指涉任何真實人物。
- 颱風過後那張正射影像：五百公尺見方的一塊地，十五座電塔全在裡面，倒下的那棵樹落在影像中央偏右。先確認塔位表跟影像用的是同一套座標系，後面的距離才算得準
- 老做法：量十五次：阿凱把十五座塔的座標貼進試算表，逐座算距離，排序取最小。十五筆，一分鐘內搞定。十五座的規模，這樣做完全夠用，建樹反而是多繞一圈
- 圖資擴到全縣：同一套流程，塔數變成一萬兩千座，每天還有四十張新影像要跑。逐座量距離的成本跟塔數直接成正比，這一步立刻變成整條流程的瓶頸。資料一長大，時間就跟著等比例長，沒有轉圜
- 建樹：第 1 層切 x：取 x 座標的中位數，也就是第 8 座，一條垂直線把圖切成左右各 7 座。第 2 層在左右兩塊各切一條水平的 y；第 3 層換回 x，切出八塊矩形。樹深 4 層，八片葉子各剩一座。建樹只做一次，之後每天那四十張影像都吃同一棵樹
- 查一次：走下去，再爬回來：從根一路比座標走到葉子，4 次比較，手上先有一個「暫時最近」的候選。回頭時檢查 3 個沒走過的兄弟分支——量那塊矩形離倒樹最近的邊界有多遠，比候選還遠的整塊跳過。兩塊當場整塊排除，只有一塊需要進去補算
- 帳算出來：暴力比對要算 15 次距離；走樹這一趟實際算到距離的大約 6 到 8 座，視點怎麼散而定。省下來的那幾次，每一次都是一整塊矩形被丟在原地，沒有人進去看過
- 阿凱想多塞幾個維度：他打算把塔高、掛線數、上次巡檢日期一起放進同一棵樹，湊成六維，想一次查完「又近又該檢查」的塔。維度一加，每塊矩形的邊界都離查詢點很近，剪枝開始剪不掉東西
這一趟真正值得記住的接縫，在第三步跟第四步之間——十五座塔的時候，建樹是多餘的動作；一萬兩千座的時候，建樹是整條流程能不能每天跑完的關鍵。阿凱動的其實是另一個東西：他對「一次查詢要付多少錢」的假設。逐座量距離那個做法，成本跟塔數綁在一起；建了樹之後，成本改跟「刀切得好不好」綁在一起——切得平衡，查詢走四層就到底；切歪了，回溯會把省下的通通還回去。這也是為什麼上一段那三件事非得在第一刀之前決定：樹一旦建好，它沒有旋轉可以自救。以上為說明結構用的示意情境，僅供理解框架之用。
k-d 樹什麼時候會騙你
- 維度一多，剪枝就形同虛設。k-d 樹好用的地方在二維、三維——平面上的塔、地圖上的店。維度往上疊，每一塊矩形的邊界都會離查詢點很近，於是回溯時「這塊可以整塊跳過」的判斷幾乎每次都不成立，查詢一路退化成把全部的點掃過一遍，還多背了一棵樹的維護成本。經驗上十幾維以上就要小心；真正的門檻跟資料怎麼分佈有關，沒有一個數字可以背起來當定律。
- 資料會動的話，這棵樹沒有旋轉可以救。平衡二元搜尋樹靠旋轉維持形狀，k-d 樹沒有這個工具——每個節點綁死在某一根軸上，硬轉會讓那一層的切法整個失效。插入跟刪除累積到一定程度，樹就歪成一條長鏈，查詢深度失控。業界慣用的處理很土：累積到某個比例就整棵重建，或者維護多棵小樹定期合併。資料每天都在變的場景，動手之前先算這筆重建的帳。
- 換一種距離，剪枝的條件要跟著換。剪枝那一步的根據是「查詢點到這塊矩形最近邊界的距離」，而那個「最近邊界」怎麼算，完全跟著你採用的距離定義走。改用球面距離（經緯度跨得遠的時候）、加權距離（某一維比較重要的時候），照抄歐氏版本的判斷條件，就會把該進去的分支剪掉——而且它安靜地錯：程式不報錯，只是回傳一個次近的鄰居，除非有人拿暴力比對對過一次帳，否則沒人會發現。
省下來的那一半，省在哪裡
k-d 樹的力氣，全花在事前那幾刀上。
查詢當下之所以快，是因為建樹那幾刀已經替它決定了「哪一堆不必看」。這件事搬到生意上，形狀一樣：成本在動手之前就大致定了。誰接這個案子、交什麼格式、驗收怎麼算——這幾刀切得準，後面每一張影像都省；切歪了，飛四十趟也補不回來。P.A.I.N. 那把尺問的第一件事就是這幾刀：誰在痛、痛在哪一格、痛到願意掏錢的那一格，在不在你切出來的那一塊裡。演算法只管得住一件事——哪一塊矩形離得夠遠、可以整塊跳過；至於那一塊裡面的人到底痛不痛，它沒有意見。這張圖畫得出十五座塔誰離誰近，畫不出哪一座塔的巡檢報告會讓對方明年還願意續約。今晚可以做一件很小的事：翻出最近三筆成交，各寫一行「這一筆是在哪一個動作之後就大致定了」。多半不會落在報價那一行。
常見問題
k-d 樹跟二元搜尋樹差在哪裡？
二元搜尋樹每一層都拿同一個鍵值比大小，k-d 樹每往下一層就換一根座標軸——第 1 層比 x、第 2 層比 y、第 3 層回到 x，節點裡還要記住自己切的是哪一根。這個差別帶來兩個後果：k-d 樹處理得了「最近的那一個」這種問題，因為距離要同時看好幾個維度；代價是它失去了旋轉這個工具，資料一動，形狀只能靠重建來維持。
幾個點以上才值得建樹？
沒有一條死線，但可以從兩件事推算。建樹本身要花時間——排序找中位數那幾輪，而這筆成本只有在「同一棵樹會被查很多次」的時候才攤得掉。十五個點只查一次，直接暴力比對就好。上千個點、每天查幾萬次，建樹的成本一次付清，之後每一次查詢都在賺。所以真正該估的那個數字，是查詢次數對點數的比例。
維度多高就不該用 k-d 樹？
沒有一個可以背的臨界值。經驗上十幾維以上，剪枝就開始剪不動，查詢逼近全表掃描；但真正決定的是資料怎麼分佈——假如那幾十維裡只有三、四維真的在變，實際表現會比維度數字看起來好。高維的常見替代是近似最近鄰那一路的做法，拿一點準確度換速度。要換之前，先量一次你的資料在每一維上的變異。
資料一直在新增，要怎麼維護？
三種常見做法。一是照樣插入，容忍樹慢慢歪，設一個門檻（例如深度超過理論值的某個倍數）就整棵重建。二是分層：一棵大的靜態樹配一棵小的新資料樹，查詢兩棵都查、取較近的那一個，小樹長到一定大小就合併回去。三是乾脆改用別的結構——資料每秒都在變的場景，k-d 樹的維護成本會超過它省下來的查詢時間。先量一次寫入跟查詢的比例，再決定。
維度一多，這把刀就鈍了，而那件事沒有寫在教科書的第一頁——教科書會先教你怎麼切，很久以後才提到切到第幾刀開始白費力氣。同樣在處理「不用全部掃一次」這件事的，還有磁碟上的索引結構；至於「樹歪了怎麼扳回來」，一維鍵值那一邊早有現成答案，見平衡樹的旋轉。
喜歡這篇文章嗎？
每週幫你拆二本好書，把判斷力、好書金句、好問題，直送你的信箱。
不適合你可隨時退訂 · 每週兩封，陪你把書讀進生活。
送出即表示同意我們依隱私權政策使用你的 email。