快速关系型存储树形数据的方法（例如文章中的嵌套评论）

Question

我有一个内容管理系统，用于存储文章的评论。这些评论可以是线程式的，也可以是非线程式的。尽管从技术上讲它们是相同的，只是当不是线程式时回复列留空。我的应用程序可以在sqlLite、MySQL和pgsql上运行，因此我需要相当标准的SQL。

我目前有一个评论表格。

comment_id
article_id
user_id
comment
timestamp
thread (this is the reply column)

我的问题是如何在数据库中最好地表示分层评论。也许是在支持树集而不包含内容的单独表中，再用一个简单的表来保存文本？或者已经采用的方法？或者另一种方式？

如果评论没有分层结构，我可以很容易地按时间戳排序。

如果它们有分层结构，我会这样排序。

ORDER BY SUBSTRING(c.thread, 1, (LENGTH(c.thread) - 1))

从ORDER BY可以看出，由于基于函数的索引只存在于Oracle中，因此评论查询永远不会使用索引。帮助我让评论页面快如闪电。

- Stewart Robinson

---

"最佳"的实现取决于数据结构和读写特性。对于一个全面更新的社区列表，建议考虑哪种方法最适合您：https://dev59.com/hW855IYBdhLWcg3w_5cQ - Kache

Answer 1

我非常喜欢Drupal如何解决这个问题。它为每个评论分配一个线程ID。该ID从第一个评论开始为1。如果在此评论中添加回复，则将ID 1.1 分配给它。对于评论1.1的回复被赋予线程ID 1.1.1。评论1.1的同级被赋予线程ID 1.2。您明白了。当添加评论时，可以轻松地使用一次查询来计算这些线程ID。

当呈现线程时，所有属于线程的评论都会通过单个查询获取，并按线程ID排序。这使您按升序获取线程。此外，使用线程ID，您可以找到每个评论的嵌套级别，并相应地缩进。

1
1.1
1.1.1
1.2
1.2.1

有一些问题需要解决：

• 如果线程 ID 的某个组件增长到 2 位数字，按线程 ID 排序将无法产生预期的顺序。一个简单的解决方案是确保线程 ID 的所有组件都通过零填充来具有相同的宽度。
• 按降序线程 ID 排序不会产生预期的降序。

Drupal 通过使用称为 vancode 的编号系统以更复杂的方式解决了第一个问题。至于第二个问题，在按降序排序时，在线程 ID 后添加反斜杠（其 ASCII 代码高于数字）。您可以通过检查 comments module 的源代码（请参见函数 comment_get_thread 前面的大注释）了解有关此实现的更多详细信息。

- Ayman Hourieh

Answer 2

我知道回答有点晚，但对于树形数据，请使用闭包表，这是适当的关系型方式。 http://www.slideshare.net/billkarwin/models-for-hierarchical-data 它描述了4种方法： - 相邻列表（简单的父外键） - 路径枚举（在已接受的答案中提到的Drupal策略） - 嵌套集 - 闭包表（在单独的关系[表]中存储祖先/后代事实，并可能具有距离列）

与其他选项相比，最后一种选择具有易于进行CRUD操作的优点。成本是空间，在最坏情况下为O(n^2)大小的树节点数，但在实践中可能不会那么糟糕。

- Timo Huovinen

---

非常酷！闭包表看起来很有前途。原始答案可能应该提供来自资源的实际信息，而不仅仅是链接到资源。我已经编辑以包括关键要点。 - acjay

Answer 3

你可以选择邻接模型或嵌套集模型。这篇文章《在MySQL中管理分层数据》为一个很好的介绍。

如果需要理论讨论，可以参考Celko的书《树和层次结构》。

如果你的数据库支持窗口函数，实现线程列表相当容易。你只需要在目标数据库表中进行递归引用，例如：

create Tablename (
  RecordID integer not null default 0 auto_increment,
  ParentID integer default null references RecordID,
  ...
)

您可以使用递归的公共表达式来显示分级视图。这里有一个示例 （点击此处）。

- Vincent Buck

Answer 4

很不幸，纯SQL方法做这件事情相当慢。

@Marc W 提出的 NESTED SETS 方法相当优雅，但如果你的树枝触及到范围，可能需要更新整个树，这会相当慢。

在我的博客中查看如何在 MySQL 中快速完成它：

• MySQL 中的分层查询 - 模拟 Oracle 的 CONNECT BY

您需要创建一个函数：

CREATE FUNCTION hierarchy_connect_by_parent_eq_prior_id(value INT) RETURNS INT
NOT DETERMINISTIC
READS SQL DATA
BEGIN
        DECLARE _id INT;
        DECLARE _parent INT;
        DECLARE _next INT;
        DECLARE CONTINUE HANDLER FOR NOT FOUND SET @id = NULL;

        SET _parent = @id;
        SET _id = -1;

        IF @id IS NULL THEN
                RETURN NULL;
        END IF;

        LOOP
                SELECT  MIN(id)
                INTO    @id
                FROM    t_hierarchy
                WHERE   parent = _parent
                        AND id > _id;
                IF @id IS NOT NULL OR _parent = @start_with THEN
                        SET @level = @level + 1;
                        RETURN @id;
                END IF;
                SET @level := @level - 1;
                SELECT  id, parent
                INTO    _id, _parent
                FROM    t_hierarchy
                WHERE   id = _parent;
        END LOOP;
END

并在查询中使用它，如下所示：

SELECT  hi.*
FROM    (
        SELECT  hierarchy_connect_by_parent_eq_prior_id(id) AS id, @level AS level
        FROM    (
                SELECT  @start_with := 0,
                        @id := @start_with,
                        @level := 0
                ) vars, t_hierarchy
        WHERE   @id IS NOT NULL
        ) ho
JOIN    t_hierarchy hi
ON      hi.id = ho.id

当然，这是针对 MySQL 的具体实现，但速度很快。

如果你想让它在 PostgreSQL 和 MySQL 之间可移植，可以使用 PostgreSQL 的 CONNECT BY 扩展，并将查询封装到同名的存储过程中，适用于两个系统。

- Quassnoi

Answer 5

其实我刚刚做过这个！我使用了关系型数据库中表示层次数据的嵌套集模型。

在MySQL中管理分层数据对我非常有帮助。该文章中介绍了两种模型，其中嵌套集是第二种。

- Marc W

---

嵌套集合的糟糕之处在于以任何方式修改树结构都是代价高昂的。 - acjay

Answer 6

实际上，读写之间必须保持平衡。

如果您可以接受在每次插入时更新大量行，则嵌套集（或等效物）将为您提供简单快速的读取。

除此之外，在父级上使用简单的FK将为您提供超级简单的插入，但可能会成为检索的噩梦。

我认为我会选择嵌套集，但要注意预期的数据量和使用模式（每次插入更新两个索引列（左侧和右侧信息）中的多个甚至大量行可能会在某些时候成为问题）。

- Denis Troller