0

我有一个评论树及其关闭表：

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;

如何对评论线程进行预排序（深度优先）遍历？

（我意识到使用嵌套集很容易进行预订遍历，但我特别好奇如何使用闭包表进行遍历。）

4

2 回答 2

1

我已经在我的 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

于 2013-06-30T23:38:17.173 回答
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 擅长管理集合，因此这确实是唯一明智的方法。当然这意味着闭包表应该只存储直接​​的父/子关系。

请注意，这会以深度优先的方式返回结果，而您的查询会以广度优先的方式返回结果。为了做到这一点，您需要以某种方式存储或生成路径，否则您将无法获得真正的深度信息。因此，您可以以非规范化的方式将路径添加到您的闭包表，或者您可以只获取父/子关系并在查询中生成它，如我的示例所示。

于 2013-05-25T03:48:44.013 回答