架構面試題 #3, RDBMS 處理樹狀結構的技巧
摘要提示
- Tree 與 RDBMS 落差: 樹狀資料在關聯式模型中不自然，遞迴與階層查詢是瓶頸，需要取捨語法可讀性與效能。
- 測試情境與資料規模: 以檔案系統為例，針對查詢、遞迴搜尋、建立、搬移、刪除五類操作，使用含 22 萬目錄、110 萬檔的大型資料集。
- 方案一 Self-Join/CTE: 以 parent_id 表示父子關係，查詢直覺、異動簡單，但遞迴查詢效能差且跨 DBMS 可攜性不佳。
- 方案二 多欄位層級索引: 以 ID01~ID20 固定欄位攤平成階層索引，遞迴查詢極快，但搬移複雜、維運與可讀性差、層級上限受限。
- 方案三 Nested Set Model: 以 left/right 範圍索引表徵包含關係，非限定階層查詢快、語法簡潔標準；異動需批次位移 index。
- 效能對比重點: 遞迴搜尋方案三≈極快，方案二最快，方案一最慢；大量刪除三者差距縮小，方案三整體最佳。
- 語法可攜與維護: 避免依賴特定 DB 方言（如 CTE/CONNECT BY）可提升可攜性；方案三與標準 SQL 相容度高。
- 異動與查詢取捨: 以額外索引換取查詢效能（特別是遞迴搜尋），將成本前移至建置/更新階段。
- 實務建議混搭: 可混合 parent_id、層級欄位、left/right 深化索引，視系統瓶頸與業務操作頻率選型。
- 基礎知識價值: 正確的資料模型與演算法選擇遠勝於工具；面試可辨識基礎功與靈活應用能力。
全文重點
本文以「如何在 RDBMS 內妥善處理樹狀結構」為題，從實務的檔案系統情境出發：包含目錄/檔案清單查詢、非限定階層的遞迴搜尋、建立目錄、搬移目錄、刪除目錄等五類操作，在一組大型真實資料（約 22 萬目錄、110 萬檔，深度至 18 層）上逐一驗證三種資料建模法的語法與效能，並總結取捨原則。
方案一以 parent_id 表示父子關係，符合教科書 tree 結構，自然支援建立、搬移、刪除等異動；但遇到遞迴查詢需多次 self-join，或倚賴各家 DB 特性（如 SQL Server CTE、Oracle CONNECT BY），雖能簡化語法卻未必改善本質效能與可攜性。方案一在單層查詢表現可接受，但在大範圍遞迴搜尋明顯落後。
方案二將每階層拆為固定欄位（ID01~ID20），預先把「路徑」索引化，讓遞迴搜尋退化為單欄位過濾，查詢極快；但搬移需整批 shift 欄位，語法醜且難抽象化、層數上限受 schema 限制、維運與安全（動態 SQL）風險較高。此法適合高度查詢導向且層級可控、幾乎無搬移的場景（如分類、選單）。
方案三採 Nested Set Model（left/right），以「範圍涵蓋」取代「階層」，對非限定階層查詢極友善，語法標準、易封裝；並可用（right-left-1)/2 快速得子節點數。其缺點是異動需批次位移索引（插入/搬移/刪除皆然），但操作可用演算法化流程處理（含暫存負區段技巧）。在本測試中，方案三在大範圍遞迴搜尋與大量刪除的綜合效能最佳，且語法可攜性高，是較均衡的選擇。
作者提出總結：在資料庫世界，正確 schema/index/algorithm 的效益遠高於工具；如能將成本前移（寫入/異動時計算索引），能換得高效搜尋與簡潔語法。實務上亦可混搭（如同存 parent_id、depth 與 left/right），但要衡量索引維護成本。最後呼應寫作動機：基礎知識是長久競爭力，能幫助在不同技術棧中做出正確選型與權衡。
段落重點
開始前的準備
以檔案系統為例建模：目錄（folder）與檔案（file）形成標準樹，排除快捷/符號連結；定義五種核心操作：單層清單、遞迴搜尋、副檔名過濾、建立、搬移、刪除。作者以工具爬取 C:\ 生成測試資料（約 22 萬目錄、110 萬檔、最大深度 18），並設計五個 T-SQL 任務模擬實境操作（如 dir/dir /s、mkdir、move、rm），以執行計畫成本與時間評估三種建模方案。
方案 1, 紀錄上一層目錄ID
以 self-referencing table（ID、PARENT_ID）表達父子關係，查單層清單極簡；遇遞迴需多層 self-join 或使用 CTE/CONNECT BY 等方言語法，語法雖簡但效能仍受遞迴本質限制，範圍擴大即顯著變慢。建立與搬移（更新 PARENT_ID）直覺且快；刪除需先遞迴找出所有子孫再刪除，成本高。小結：此法偏向「異動友善、查詢吃力」，跨 DB 可攜性與 ORM 支援亦受限於方言語法。
方案 1／需求 1：查詢指定目錄下的內容
透過尋找目標目錄 ID 後，分別過濾子目錄（PARENT_ID=root）與檔案（DIR_ID=root），可輕易產出與 dir 類似的輸出。此單層查詢效能佳，SQL 簡潔，是此模型的強項之一。
方案 1／需求 2：查詢指定目錄下的內容（遞迴）
需先確定起點目錄 ID（可用固定層級 self-join 或 CTE 查），再用 CTE 展開全子孫後 join 檔案與副檔名過濾。語法可讀但在大範圍遞迴下時間明顯上升，MAXRECURSION 可防止無限遞迴但不解決效能瓶頸。
方案 1／需求 3～5：建立、搬移、刪除
建立：insert 一筆含 PARENT_ID 即可，極快。搬移：更新目標節點之 PARENT_ID 一行完成，成本極低。刪除：需用 CTE 先展開所有後代，再分別刪檔案與目錄；在大型樹與大量檔案時時間拉長。小結：CRUD 之「U/D」受限於先找子孫的成本。
方案 2, 開欄位記錄每一層目錄ID
以 ID01~ID20 固定欄位存放路徑各層之節點 ID（最大層數預先設定），把遞迴查詢轉為單欄位或定值前綴匹配。遞迴搜尋轉化為 where IDn = 起點，效能極佳；單層清單為 where IDn = x and IDn+1 is null。缺點：搬移需整列 shift 欄位、語法冗長且難封裝；最大層級受 schema 限制，擴充需改表與重寫 SQL；維護與注入風險需小心。適合幾乎不搬移、以查詢為主且層級可控的場景（如商品分類）。
方案 2／需求 1～2：單層與遞迴查詢
單層清單以 IDn = 目標且 IDn+1 is null 快速過濾；遞迴搜尋改為匹配「前綴所在欄位」即可（如查 system32 之所有子孫為 where ID03 = system32_id），join 檔案過濾副檔名即完成。效能在三方案中表現頂尖，語法簡單，但前提是事前正確維護每層欄位。
方案 2／需求 3～5：建立、搬移、刪除
建立：需依當層填入對應欄位（其餘為 null），可用動態 SQL 或程式產生語法。搬移：必須對整棵子樹進行欄位「右移」並重寫前綴欄位，SQL 冗長、可讀性差；但執行時間仍可接受。刪除：以匹配前綴（如 where ID03 = x）選出子孫刪除，檔案數量大時 I/O 為主。小結：查詢漂亮、異動痛苦、維運成本高。
方案 3, 標記涵蓋範圍
Nested Set Model：每節點存 left/right，使用 DFS 標號，父節點範圍完全包住子孫；可用 (right-left-1)/2 快速算子孫數。非限定階層查詢轉為簡單的範圍查詢，語法標準、可攜性高。插入/搬移/刪除需批次平移 index，實作可採分步位移與暫存負區策略；雖有寫入成本，但可在應用層或批次任務中攤平，換得高效查詢。
方案 3／需求 1：單層清單
以範圍法找所有子孫後排除「中間存在其他節點」即可得直屬子節點；若輔以 parent_id 或 depth 欄位可大幅簡化且提速（實務常見混搭）。此單一需求純用範圍法較拗口，建議混用 parent_id。
方案 3／需求 2：遞迴查詢
非限定階層查詢化為「left between L and R」與檔案 join、加副檔名過濾，效能優異且語法精簡，與方案二相近甚至更穩定，對大範圍搜尋表現突出，是本模型強項。
方案 3／需求 3～5：建立、搬移、刪除
建立：在插入點右側整體 left/right +2 騰空索引，再插入新節點；需兩次批次更新。搬移：三步驟（源子樹移至負區暫存、目標範圍騰位、搬回新位）即可完成，時間穩定、邏輯清楚且可抽象為存儲程序。刪除：先依範圍刪檔案與子孫，再回收索引空間（整體平移）。此法在「搜尋+刪除」綜合場景下整體最佳。
小結: 三種方案比較
在真實大數據下比較五種操作時間：方案一遞迴查詢最慢（即便用 CTE），單層與異動尚可；方案二查詢最快但搬移代價高且層級上限受限；方案三在遞迴搜尋與大量刪除整體最佳，語法標準與可攜性佳。對 Web/雲端常見場景，最需在意「大範圍遞迴搜尋」與「大量刪除」，方案三較均衡，方案二僅在層級可控且極端追求查詢性能時可考慮。
需求 2+, 效能總評
遞迴搜尋（如 c:\windows*.dll）是關鍵負載。方案一因遞迴/多層 join 天生劣勢，效能落後一個數量級；方案二最快，但受 schema 上限與維護複雜性制約；方案三接近方案二且具可攜、可封裝優勢，實務上較建議選用。若對 10x 級效能極度苛求且能嚴控層級與維護成本，方案二才有空間。
需求 5, 效能總評
大量刪除本質受 I/O 影響，三者差距縮小；方案三仍在綜合表現勝出。由於搜尋是刪除前置，能以範圍索引快速選集、再批刪，可在大資料量下維持穩定時間。若結合批處理/離線任務整理索引，整體更穩定。
總結
正確的 schema/index/algorithm 比工具更關鍵。將成本前移（寫入/異動時計算好索引），能換取高效、標準化的查詢與易維護性。實務可混搭 parent_id、depth 與 left/right，以應對不同負載；也可把索引維護移至應用層或批處理。最終選型應回到業務特性：查詢/異動比例、層級是否可控、跨 DB 可攜需求與團隊維運能力。
寫在最後: 寫這篇文章的動機
作者強調基礎知識的重要：觀念（模型與演算法）比操作（工具與框架）更長壽、更可遷移。架構決策需看清問題本質與系統瓶頸，選擇正確模型與取捨，才能在成本、效能、可維運之間取得平衡；也能在不同技術棧間平穩過渡（如從原生 XML/NOSQL 思維轉為 RDBMS 可行實作）。本篇亦提供完整範例程式與參考資源，助讀者在實務中活用與混搭。
資訊整理
知識架構圖
- 前置知識：
- 關聯式資料庫基本概念（表格、主鍵/外鍵、索引、JOIN）
- 樹狀資料結構與常見操作（搜尋、遞迴、搬移、刪除、插入）
- SQL 方言與特性（CTE、Oracle CONNECT BY、SQL Server hierarchyid）
- 查詢效能與執行計畫（索引策略、Estimated Subtree Cost、I/O 成本）
- 核心概念：
- Adjacency List（上一層 PARENT_ID/self-join/CTE）：語法直觀、遞迴查詢需特別處理、搬移容易、效能依賴遞迴
- 固定欄位分層（ID01~ID20）：以欄位展開各層，遞迴查詢簡化為條件過濾，效能佳但可維護性差、深度受限
- Nested Set Model（LEFT/RIGHT）：以區間表示包含關係，遞迴查詢極簡高效，但插入/搬移需重編 index；可加入 PARENT_ID/DEPTH 輔助
- 索引與前置計算：以「預先維護索引」換取「查詢期高效」，在更新期支付成本
- 移動計算邊界：在應用層完成樹遍歷與索引維護，DB 僅做批量寫入與查詢
- 技術依賴：
- Adjacency List 依賴：自我關聯（self join）與遞迴語法（CTE/CONNECT BY）或應用層遞迴
- 固定欄位分層 依賴：表結構與索引設計（多列索引、條件過濾），應用層/動態 SQL 以支援不同深度
- Nested Set 依賴：正確維護 LEFT/RIGHT（更新時區間平移），可疊加 PARENT_ID/DEPTH 降低特定查詢成本
- 效能觀察：執行計畫、索引（範圍查詢適合 B-Tree）、批次更新策略、事務與鎖
- 應用場景：
- 以查詢為主、搬移少的階層資料：分類、選單、商品目錄、相簿、知識樹（推薦 Nested Set）
- 以頻繁搬移/重組為主：組織圖、檔案系統模擬（Adjacency List 或混合，視查詢負載）
- 有嚴格層數上限且查詢極致效能：樹深度可控的分類瀏覽（固定欄位分層）
- 異質/跨 DB 方言需可攜：避免依賴專屬語法（傾向 Nested Set 或混合 + 應用層計算）
學習路徑建議
- 入門者路徑：
- 理解樹狀資料與常見操作（列子節點、全子孫查詢、搬移、刪除、插入）
- 實作 Adjacency List（PARENT_ID、自我關聯），練習用 CTE 做遞迴查詢與 MAXRECURSION
- 讀執行計畫，為關鍵欄位建索引（PARENT_ID、DIR_ID、EXT）
- 進階者路徑：
- 比較三種模型的查詢與更新成本，重現文中五個操作的 SQL
- 實作 Nested Set（計算 LEFT/RIGHT：DFS 次序），加入 PARENT_ID/DEPTH 輔助
- 規劃索引與批次更新策略（區間平移、事務、鎖競爭觀察）
- 實戰路徑：
- 按業務負載選型（查詢重 vs 異動重），或混合使用（例如 Nested Set + PARENT_ID）
- 把索引維護搬到應用層（匯入/同步流程中完成 DFS 標號與 PATH 欄位）
- 建立壓測與監控（查詢延遲、刪除/搬移耗時、索引維護時間），持續優化
關鍵要點清單
- 三種樹模型選型：Adjacency、固定欄位分層、Nested Set，各自效能/維護/可攜權衡（優先級: 高)
- Adjacency List 遞迴：CTE/CONNECT BY 可讀性佳但效能常受限，注意 MAXRECURSION（優先級: 高)
- 固定欄位分層限制：層數上限、SQL 可維護性差、動態 SQL 風險（優先級: 中)
- Nested Set 核心：用 LEFT/RIGHT 區間表示包含關係，遞迴查詢化為範圍查詢（優先級: 高)
- Nested Set 更新：插入/搬移需批次區間平移，建議以應用層預計算降低 DB 複雜度（優先級: 高)
- 混合策略：Nested Set 疊加 PARENT_ID/DEPTH，直屬子節點查詢更簡潔高效（優先級: 中)
- 索引設計：針對查詢條件建索引（PARENT_ID、DIR_ID、EXT、LEFT/RIGHT），減少全掃（優先級: 高)
- 執行計畫與成本：Estimated Subtree Cost、I/O 熱點、JOIN 策略影響巨大（優先級: 中)
- 方言可攜性：避免過度依賴專屬語法（CTE/hierarchyid），ORM 遷移風險（優先級: 中)
- 批次操作與事務：大規模刪除/搬移需控制鎖、分批提交、避免長交易（優先級: 高)
- 應用層遞迴與前置計算：用 DFS 產生 LEFT/RIGHT 與 PATH 欄位，寫入時一次完成（優先級: 高)
- 實測與基準：以實際數據量驗證（百萬級 file、十萬級 dir）選型與索引（優先級: 高)
- 安全性：固定欄位分層常需要動態 SQL，需嚴格參數化以防 SQL Injection（優先級: 中)
- 維運成本：結構可讀性、SQL 可重用（SP/參數化）、表結構演進風險（優先級: 中)
- 應用場景匹配：以查詢為主選 Nested Set，以頻繁結構變更選 Adjacency/混合（優先級: 高)
