如何在遞歸SQL查詢中查找子樹中的所有節點？

Question

我有一個定義節點之間的父子關係的表：

CREATE TABLE node (       ' pseudo code alert 
    id  INTEGER PRIMARY KEY, 
    parentID INTEGER, ' should be a valid id. 
) 

如果parentID總是指向一個有效現有節點，那麼這自然會定義一個樹狀結構。

如果parentID是NULL那麼我們可以假設該節點是根節點。

我怎麼會：

1. 找到所有這些都是給定節點的decendents的節點？
2. 查找給定節點下的所有節點到特定深度？

我想做的每個這些作爲單個SQL（我期望它必然是遞歸）或兩個相互遞歸查詢。

我在ODBC上下文中這樣做，所以我不能依賴任何供應商特定的功能。

編輯

• 沒有表寫呢，因此增加額外的列/表是完全可以接受的。
• 該樹將潛在地更新並添加到相當頻繁;輔助數據結構/表格/列將是可能的，儘管需要保持最新。 如果您有任何有關這類查詢的魔法書，我想知道。

非常感謝。

Answer 1

This link提供兩個鄰接表模型（如問題所述），和嵌套集模型的教程。它是作爲MySQL文檔的一部分編寫的。

那篇文章中沒有討論的是這兩種方法的插入/取消時間和維護成本。例如：

• 使用嵌套集模型似乎需要一些維護，以保持嵌套動態成長樹（例如重新編號所有左，右集數）的鄰接表模型
• 移除節點至少需要更新另一行。

Answer 2

一些方法進行了本文前面介紹：

SQL - how to store and navigate hierarchies

Answer 3

如果您有任何魔法書你達到了這種查詢的，我想知道。

Celko的樹木和層次結構在SQL for Smarties一

Answer 4

將根節點ID中的整個「路徑」存儲在一個單獨的列中，確保在開始和結束時也使用分隔符。例如。假設1是5的父親，它是17的父親，並且您的分隔符是破折號，您可以將值-1-5-17-存儲在路徑列中。

我們找到5所有的孩子，你可以簡單地選擇記錄中，其中路徑包括-5-

在兩端的隔離是必要的，所以你並不需要擔心的ID是在最左邊或最當您使用LIKE時，該字段的最右端。

至於你的深度問題，如果你添加一個深度列到表指示當前嵌套深度，這容易爲好。您查找起始節點的深度，然後向其中添加x，其中x是要搜索的深度級別數，並且篩選出的記錄深度大於此深度。