概念地圖・R 樹
作者 山姆（謝冠生）・喵喵書評創辦人
發布
分類：系統
這一頁不只是把一個概念解釋一遍——一張自己畫的結構圖，加上拿台灣情境從頭走一次的實例演練、這個框架什麼時候會騙你，以及它接回 P.A.I.N. 之後長什麼樣。一頁必須交付的三層 →
R 樹：大框命中後還要查什麼
抽水站值班員在地圖上框出一條巡查帶，系統先亮起幾個大框，接著才逐座核對站點。那幾個框只是搜尋入口。R 樹把空間物件的外接矩形逐層收進父框，查詢從根部往下，跳過範圍完全碰不到的分支。麻煩也在框裡：父框之間可能重疊，空白地帶也會被包進來。同一個巡查範圍，可能讓系統走兩枝，最後一筆都找不到——看懂這段路，才知道地圖轉圈圈時該量哪裡。
地圖上的框，如何接到樹節點
先把空間上的框，對回索引裡實際儲存的項目——父框包的是下一層的範圍。
| 圖上元素 | 索引中的工作 | 這次查詢的結果 |
|---|---|---|
| 金框 P | A、B 的最小外接矩形，從（1，1）到（5，5） | 與查詢相交，進入包含 A、B 的葉節點 |
| 綠框 Q | C、D 的最小外接矩形，從（3，3）到（8，7） | 與查詢相交，另一個葉節點也要讀 |
| 四個葉項 | A 為（1，1）到（3，2）；B 為（4，4）到（5，5）；C 為（3，3）到（4，3.5）；D 為（6，6）到（8，7） | 逐一比對後，全數排除 |
| 紅色查詢框 | 從（3.4，4.3）到（3.8，4.7），只碰到父框包住的空白處 | 父框通過篩選，仍可能沒有物件命中 |
R 樹是高度平衡的空間索引，所有葉節點位於同一層。每個非葉項目用外接矩形加上子節點指標，把搜尋往下帶。Guttman 原始論文容許同層矩形重疊，因此一次範圍搜尋可能進入多個子樹。上圖四個物件本身就是矩形，葉框檢查足以判定這次相交結果；換成曲線或多邊形，葉框命中後還要檢查原始幾何。這個兩階段流程也可對照 PostGIS 空間索引說明。
篩選成本要沿搜尋路徑量
一、先釘住範圍相交的意思。值班員圈巡查帶時，可能要找帶內站點，也可能要找服務區碰到巡查帶的抽水站。前者比較點座標，後者得比較面範圍；同一座站，兩種查法會給出不同名單。先把資料代表什麼、邊界接觸算不算命中寫清楚——索引加速的是你指定的判斷。自問：我要回答的問題，是否真的需要範圍相交？
二、把分枝數和候選數一起記下。巡查帶穿過父框重疊區，兩個分支都要走；若父框包了大片空白，走到底還會丟掉許多候選。拿值班常用的幾個區域回放，記錄讀過多少節點、送出多少葉項候選、最後留下多少站。每段時間分開看——樹長得矮，只說明層數少，搜尋展開的寬度仍可能很大。自問：父框重疊多少，查詢又多帶出多少候選？
三、確認最後一道幾何檢查還在。站點若是單純的點，落在矩形內可以直接核對座標。巡查帶若彎曲，或資料換成站區邊界，外框就會把彎角外的空白也包起來。把幾個靠近邊界的測試物件放進驗收資料，核對候選如何進、如何出——最後名單的正確性要有自己的證據。自問：通過外框篩選後，是否保留符合查詢定義的精確檢查？
抽水站巡查帶的候選站點
底下這位在台灣中部管理抽水站地圖的值班員，是為了把這個結構講清楚而編出來的示意情境，沒有指涉任何真實人物。八個站點與座標也全為虛構，座標使用教學單位。
- 先放入八個站點：甲群是甲一（1，1）、甲二（2，2）、甲三（4，4）、甲四（5，1）；乙群是乙一（3，3）、乙二（6，6）、乙三（8，7）、乙四（7，3）。這次分組先固定，方便追蹤每一筆資料。
- 替兩群各取最小外接框：甲框從（1，1）到（5，4），乙框從（3，3）到（8，7）。兩群的東西、南北極值決定框邊——任何一邊縮進去，都會漏包站點。一個父框，一次概括四筆。
- 把巡查範圍簡化成矩形：查詢從（0.5，0.5）到（2.5，2.5）。它與甲框相交，和乙框完全分離，所以只往甲群走。乙群四筆整群略過。
- 逐站核對甲群：甲一、甲二落在查詢內；甲三超出橫縱上界，甲四超出橫向上界，最後返回兩站。甲群通過父框檢查後，四個點仍得逐項比較。候選四站，結果兩站。
值班員最後看到兩個站名，索引先替系統省下了乙群的四次點位核對。這個例子只演示搜尋路徑，八筆資料不足以支持效能優劣的結論。資料量、快取、節點容量都會影響耗時；清單上的兩站也只表示空間條件相符，現場能否到達、機組狀態如何，都要另有資料回答。交班時值得保留的，是查詢範圍與每一層的淘汰紀錄——下一班看到相同結果，還能知道它怎麼來。以上為說明結構用的示意情境，僅供理解框架之用。
外接矩形什麼時候會騙你
- 細長物件把空白一起帶進候選。一條斜向、彎曲的巡查帶，放進軸對齊矩形後，框內可能留著大片空地。查詢碰到那片空白，仍會觸發後續檢查。候選暴增時，要先量物件外框相對於幾何形狀的鬆散程度——換更快的讀取設備，也得繼續付那些多出來的幾何運算。
- 同一批物件，可以長出不同的重疊。逐筆插入的順序、節點滿載時的分裂策略，都會改變物件分組與父框形狀。招牌圖只安排一組容易看懂的分群，沒有最佳分裂的承諾。比較索引方案時，要使用同一批資料和查詢範圍，連更新工作量一起記錄——只比兩張漂亮的樹狀圖，缺少實際代價。
- 座標處理錯了，外框也會跟著錯。圖上的抽象平面可以直接比較上下界。真實地理資料則要先確認座標系、軸順序、單位與幾何運算的語意；經緯度資料碰到跨日期線範圍時，更須依系統支援的方式處理包覆邊界。先拿已知位置驗算查詢——錯誤的座標進入再整齊的樹，查詢結果照樣失準。
候選清單也有服務成本
多走一枝，等待就多留一段。
值班員不會看到父框重疊面積。他看到的是框選後滑鼠停住，隔壁的人問了一次，清單還沒出來。這張圖畫得出查詢走過哪些框，畫不出等候的人正被哪件事催促。把《痛點》的 P.A.I.N. 放進這裡，先追那個被打斷的動作：他是否需要重畫範圍、是否因空白畫面重按一次、是否把候選站點誤當完成核對的清單。系統端的候選數，應該接到使用端的完成時間，才知道優化幫到了誰——少讀一個節點是技術訊號，一次框選就拿到可理解的結果，才接上工作。今晚錄下一次常用範圍查詢，從按下滑鼠計時到名單顯示，再把那段等待對上節點走訪與候選淘汰紀錄。
R 樹，常見問題
R 樹為什麼允許父框重疊？
父框由同一子節點內各物件的最小、最大座標決定。兩組物件在平面上交錯分布，外接框自然可能相交；R 樹容許這種重疊。搜尋時必須檢查每個相交父框，避免漏掉任何符合條件的物件。代價是多走分支、多讀節點——重疊增加走訪工作；逐層相交檢查維持完整搜尋。
父框命中，裡面的站點就全部符合嗎？
父框與查詢相交，只表示該分支仍有可能包含結果。本文招牌圖的兩個父框都通過，四個葉項卻全部被排除。實例中的甲群也是先留下四站，逐點比較後才返回兩站。若葉項存的是不規則物件的外框，還要接著用原始幾何驗證——候選清單必須走到查詢定義要求的最後一步。
R 樹只適合有面積的物件嗎？
點也能用外接框表示，只是每個維度的上下界相同，框退化成一個點。因此八個站點能按同樣的父框結構收納。至於哪種索引最合適，還得看常見查詢是範圍、距離或其他條件，以及資料更新頻率。先留下代表性查詢再測——這篇的分組與八筆資料用來理解路徑，沒有替任何產品做效能背書。
範圍查詢常同時走好幾枝，空間切分若改成 k-d 樹，分枝的理由也會跟著換；大量索引的層數則能再對照 B＋樹。接著看軸向切分的點索引與平衡多路索引，把同一筆查詢沿各自的路徑走一次。
喜歡這篇文章嗎？
每週幫你拆二本好書，把判斷力、好書金句、好問題，直送你的信箱。
不適合你可隨時退訂 · 每週兩封，陪你把書讀進生活。
送出即表示同意我們依隱私權政策使用你的 email。