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

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

实际上，它必须在读和写之间取得平衡。

如果您愿意在每次插入时更新一堆行，那么嵌套集（或等效的）将为您提供轻松、快速的读取。

除此之外，父级上的简单 FK 将为您提供超简单的插入，但很可能对检索来说是一场噩梦。

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

Answer 2

事实上，我自己就是这么做的！ 我使用嵌套集模型来表示关系数据库中的分层数据。

在 MySQL 中管理分层数据对我来说简直就是黄金。 嵌套集是该文章中描述的第二个模型。

Answer 3

您可以在邻接模型和嵌套集合模型之间进行选择。 管理 MySQL 中的分层数据一文提供了很好的介绍。

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

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

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

然后您可以使用递归公共表表达式来显示线程视图。 此处提供了一个示例。

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 贡献并将查询包装到两个系统具有相同名称的存储过程中。

Answer 5

我知道答案有点晚了，但是对于树数据使用闭包表，这是正确的关系方式。
http://www.slideshare.net/billkarwin/models-for-hierarchical- data

它描述了 4 种方法：

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

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

Answer 6

我真的很喜欢 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码高于数字）来解决。 您可以通过检查 评论模块（请参阅函数comment_get_thread之前的大评论）。