存储树数据的快速关系方法(例如文章的线程注释)

我真的很喜欢 Drupal 解决了这个问题。它为每个注释分配一个线程ID。对于第一条注释,此ID从1开始。如果将答复添加到此注释中,则ID 1.1 分配给它。对评论的答复 一点一 提供了线程ID 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 (请参阅函数注释获取线程之前的大注释)。

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

它描述了4种方法:

• 相邻列表(简单父外键)
• 路径枚举(公认答案中提到的Drupal策略)
• 嵌套集合
• 关闭表(将祖先/后代事实存储在单独的关系[表]中,并带有可能的距离列)

最后一种方案与其他方案相比具有易于积垢操作的优点。成本是空间,在最坏的情况下,数字树节点的大小是O(n^2),但在实践中可能并不那么糟糕。

不幸的是,纯SQL方法的速度非常慢。

这个 NESTED SETS 提出的 @Marc W 非常优雅,但是如果你的树枝达到范围,它们可能需要更新整棵树,这可能非常慢。

在我的博客上看到这篇文章,关于如何在 MySQL :

• Hierarchical queries in 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 ,你可以使用 波斯特雷斯尔 的诡计 通过连接 并将查询包装到两个系统具有相同名称的存储过程中。

实际上,我是自己做的!我使用嵌套集模型来表示关系数据库中的分层数据。

Managing Hierarchical Data in MySQL 对我来说是纯金的。嵌套集是本文中描述的第二个模型。

您可以在相邻集模型和嵌套集模型之间进行选择。文章 Managing Hierarchical Data in MySQL 做一个很好的介绍。

有关理论讨论,请参阅Celko的 Trees and Hierarchies .

如果数据库支持窗口功能,那么实现线程列表就相当容易。您所需要的只是目标数据库表中的递归引用,例如:

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

然后可以使用递归公用表表达式来显示线程视图。有一个例子 here .

实际上,它必须在读和写之间保持平衡。

如果您可以在每次插入时更新一组行,那么嵌套集(或等效集)将为您提供简单、快速的读取。

除此之外,父级上的一个简单FK将为您提供非常简单的插入,但对于检索来说可能是一个噩梦。

我想我会使用嵌套集,但是要注意预期的数据量和使用模式(更新每个插入的两个索引列上的几行,可能很多行(用于左和右信息)在某些时候可能是个问题)。