存储树数据的快速关系方法（例如文章的线程评论）

Question

我有一个 cms，用于存储针对文章的评论。这些评论可以是线程式的，也可以是非线程式的。尽管从技术上讲，它们是相同的，只是回复列在未线程化时留空。我的应用程序适用于 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 中。帮助我拥有闪电般快速的评论页面。

Answer 1

我真的很喜欢如何 德鲁帕尔 解决了这个问题。它为每个评论分配一个线程 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码高于数字）来解决。您可以通过检查源代码找到有关此实现的更多详细信息 评论模块 （参见函数comment_get_thread之前的大注释）。

Answer 2

我知道答案有点晚了，但是对于树数据，请使用闭包表http://www.slideshare.net/billkarwin/models-for-hierarchical-data

它描述了4种方法：

• 邻接表（简单父外键）
• 路径枚举（接受的答案中提到的Drupal策略）
• 嵌套集
• 闭包表（将祖先/后代事实存储在单独的关系[表]中，带有可能的距离列）

与其他选项相比，最后一个选项具有简单的 CRUD 操作的优点。成本是空间，在最坏的情况下，树节点数量为 O(n^2) 大小，但在实践中可能并没有那么糟糕。

Answer 3

不幸的是，纯 SQL 方法执行此操作非常慢。

这 NESTED SETS 提议者 @Marc W 非常优雅，但如果您的树枝达到范围，它们可能需要更新整个树，这可能会非常慢。

请参阅我博客中的这篇文章，了解如何快速完成此操作 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 并将查询包装到两个系统具有相同名称的存储过程中。

Answer 4

我只是做了这个我自己，居然！我用在关系数据库中表示阶层数据的组嵌套模型。

在MySQL 管理分层数据是纯金的我。嵌套集合是本文中描述的第二个模型。

Answer 5

您已经得到了邻居和嵌套集模型之间的选择。文章管理MySQL的分层数据做了很好的介绍。

有关的理论讨论，参见Celko的树木和层次结构。

这是相当容易，如果你的数据库支持窗口函数来实现线程列表。所有你需要的是你的目标数据库表中的递归引用，如：

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

然后可以使用一个递归公用表表达式显示的螺纹图。一个例子是可以 rel="nofollow noreferrer">。

Answer 6

实际上，它必须是读取之间的平衡和写入。

如果您是与在每个插入件更新一串行的行，则嵌套组（或等同）会给你简单，快速读出。

除此之外，父简单的FK会给你超简单的插入，但很可能是用于检索的噩梦。

我想我会与嵌套集合去，但要小心的预期数据量和使用模式（更新一些，也许很多，对于每次插入两个索引列行（左和右的信息）可能是在某一时刻一个问题）。