預購（深度優先）的封閉表

Question

的穿越我的意見一棵樹，它的closure table：

create table comment (
    id serial primary key, 
    author varchar(100) not null, 
    content text not null 
); 

create table closure (
    ancestor integer not null references comment (id), 
    descendant integer not null references comment (id) on delete cascade, 
    depth integer not null, 
    primary key (ancestor, descendant) 
); 

我想要得到的ID爲4註釋下的所有意見的子樹。這不是太難做了評論跟帖的廣度優先遍歷：

select comment.*, closure.depth 
from comment 
inner join closure on closure.descendant = comment.id 
where ancestor = 4 
order by depth asc; 

我該怎麼辦預購（深度優先）評論跟帖的穿越？

（我認識到，做一個前序遍歷很容易與嵌套集合，但我很好奇，專門對如何與閉合表做到這一點。）

Answer 1

首先，請不要考慮這個廣度優先或深度優先問題。理想情況下，您將把它看作一系列構建結果集的集合操作。 SQLy做到這一點的方法是做一些有點像廣度優先的事情，但一次只能在一個層次上進行操作。如果您嘗試先完成全幅或全幅第一種方法，則會遇到性能問題。

的最佳途徑

WITH RECURSIVE closure_tree AS (
    SELECT descendent as id, ancestor as parent_id, 0 as depth, descendent::text as path 
     FROM closure 
     WHERE ancestor = 4 
    UNION ALL 
    SELECT c.descendent, ct.id, ct.depth + 1, ct.path || ',' || descendent::text 
     FROM closure c 
     JOIN closure_tree ct ON ct.id = c.ancestor 
) 
SELECT c.*, ct.depth, string_to_array(ct.path, ',')::int[] 
    FROM comment c 
    JOIN closure_tree ct ON c.id = ct.id 
ORDER BY string_to_array(ct.path, ',')::int[]; 

沒有測試，但是，讓你的想法。基本上它會根據深度級別掃描表（索引或順序取決於註釋數量），每次掃描時都會檢索完整圖表寬度。請記住，SQL擅長管理集合，所以這是真正實現這一目標的唯一理智方法。當然，這意味着封閉表只能存儲直接的父母/子女關係。

請注意，這將首先以深度返回結果，而您的查詢首先返回寬度結果。爲了做到這一點，你需要以某種方式存儲或生成路徑，否則你不能得到真正的深度信息。所以你可以用非規範化的方式爲你的閉包表添加路徑，或者你可以只抓取父/子關係並在查詢中生成這個，就像我的例子所示。

Answer 2

我已經在我的ruby gem中執行了預先遍歷，closure_tree，以及gem生成的SQL可以同時用於MySQL和PostgreSQL。我相信我的實現是新穎的 - 但它很毛茸茸，需要兩個選擇，並且要求排序列是數字和[0-N），其中N是兄弟的數量，並且順序沒有間隙。

https://github.com/mceachen/closure_tree/blob/master/lib/closure_tree/numeric_deterministic_ordering.rb#L48