php - 以有效和简单的方式实现层次结构、亲子关系

Question

我有一张像

create table site
(
site_Id int(5),
parent_Id int(5),
site_desc varchar2(100)
);

字段的意义：

site_Id ：网站的 ID
parent_Id ：网站的父 ID
site_desc ：虽然与问题无关，但它有网站的描述

要求是，如果我有一个 site_id 作为输入，并且我需要在站点下方标记的所有 id。例如：

所有节点都是 site_Id。

该表包含如下数据：

Site_id  | Parent_ID  |  site_desc
_________|____________|___________
 A       |   -1       |   
 B       |    A       |
 C       |    A       |
 D       |    B       |
 E       |    B       |
 F       |    B       |
 I       |    D       |
 J       |    D       |

……

A 是 B 和 C 的父级，依此类推。

如果 B 是给定的输入，则查询需要获取 D、E、I、F、J

它目前是通过循环中的多个查询来实现的，但我想用最少的查询来实现这一点。

我目前正在做的是::

否决票

算法是这样的：

Initially create a data set object which you will populate, by fetching data from the data base. 
Create a method which takes the parent id as parameter and returns its child nodes if present, and returns -1, if it doesnt have a child. 
Step1: Fetch all the rows, which doesn't have a parent(root) node. 
Step2: Iterate through this result. For example if prod1 and prod2 are the initial returned nodes, in the resultset. 
Iterating this RS we get prod1, and we insert a row in our DataSET obj. 
Then we send the id of prod1 to getCHILD method, to get its child, and then again we iterate the returned resultset, and again call the getCHILD method, till we dont get the lowest node.

我需要在我的数据模型约束中使用最佳优化技术。如果您有任何建议，请随时回答。
请提出任何建议。提前致谢。

score 10 · Accepted Answer

不幸的是，如果您无法更改数据模型，并且您使用的是 MySQL，那么您就会陷入需要递归查询并且使用不支持递归查询的 DBMS 的情况。

Quassnoi 写了一系列有趣的博客文章，展示了查询分层数据的技术。他的解决方案非常聪明，但也非常复杂。 http://explainextended.com/2009/03/17/hierarchical-queries-in-mysql/

PostgreSQL 是另一个开源 RDBMS，它确实支持递归查询，因此您可以获取以您显示的方式存储的整个树。但是如果你不能改变数据模型，我会假设你不能切换到不同的 RDBMS。

有几种替代数据模型可以更轻松地获取任意深度的树：

封闭表
嵌套集又名修改的预序树遍历
路径枚举又名物化路径

我在我的演讲Models for Hierarchical Data with SQL and PHP和我的书SQL Antipatterns: Avoiding the Pitfalls of Database Programming中介绍了这些内容。

最后，我在Slashdot的代码中看到了另一种解决方案，用于他们的注释层次结构：他们像在邻接列表中一样存储“parent_id”，但他们也存储“root_id”列。给定树的每个成员都具有相同的 root_id 值，它是其树中最高的祖先节点。然后很容易在一个查询中获取一整棵树：

SELECT * FROM site WHERE root_id = 123;

然后您的应用程序将所有节点从数据库中取回到一个数组中，您必须编写代码来循环遍历该数组，将节点插入内存中的树数据结构中。如果您有许多单独的树，并且每棵树的条目相对较少，这是一个很好的解决方案。这对 Slashdot 的情况有好处。

score 8 · Accepted Answer

昨天，我已经回答了这个与您描述的问题完全相关的问题：在给定的邻接列表中，您想要获取特定父节点的所有子节点- 并且可能在一维数组中，您可以轻松地迭代。

您可以只使用一次对数据库的调用来做到这一点，但有一个问题：您必须返回表中的所有行。MySQL 不支持递归查询，因此，您实际上必须SELECT在应用程序代码中执行 ing。

我只是要重申我在上面链接到的答案，但基本上如果您以PDOStatement->fetchAll(PDO::FETCH_ASSOC)如下格式返回结果集（可能来自或其他方法）：

Array
(
    [0] => Array
    (
        [site_id] => A
        [parent_id] => -1
        [site_desc] => testtext
    )
    [1] => Array
    (
        [site_id] => B
        [parent_id] => A
        [site_desc] => testtext
    )
    [2] => Array
    (
        [site_id] => C
        [parent_id] => A
        [site_desc] => testtext
    )
    [3] => Array
    (
        [site_id] => D
        [parent_id] => B
        [site_desc] => testtext
    )
    [4] => Array
    (
        [site_id] => E
        [parent_id] => B
        [site_desc] => testtext
    )
    [5] => Array
    (
        [site_id] => F
        [parent_id] => B
        [site_desc] => testtext
    )
    [6] => Array
    (
        [site_id] => I
        [parent_id] => D
        [site_desc] => testtext
    )
    [7] => Array
    (
        [site_id] => J
        [parent_id] => D
        [site_desc] => testtext
    )
)

site_id您可以使用此递归函数检索任何（假设您知道 id）的所有子/孙/曾孙/等等：

function fetch_recursive($src_arr, $id, $parentfound = false, $cats = array())
{
    foreach($src_arr as $row)
    {
        if((!$parentfound && $row['site_id'] == $id) || $row['parent_id'] == $id)
        {
            $rowdata = array();
            foreach($row as $k => $v)
                $rowdata[$k] = $v;
            $cats[] = $rowdata;
            if($row['parent_id'] == $id)
                $cats = array_merge($cats, fetch_recursive($src_arr, $row['site_id'], true));
        }
    }
    return $cats;
}

例如，假设您想检索的所有子项site_id D，您将使用如下函数：

$nodelist = fetch_recursive($pdostmt->fetchAll(PDO::FETCH_ASSOC), 'D');
print_r($nodelist);

会输出：

[0] => Array
(
    [site_id] => D
    [parent_id] => B
    [site_desc] => testtext
)
[1] => Array
(
    [site_id] => I
    [parent_id] => D
    [site_desc] => testtext
)
[2] => Array
(
    [site_id] => J
    [parent_id] => D
    [site_desc] => testtext
)

请注意，我们保留了父级的信息，以及它的子级、孙子级等（无论嵌套有多深）。

score 5 · Accepted Answer

如果您希望能够在单个查询中执行此操作，请查看嵌套集模型：http: //mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

另一种选择是将所有关系包含在链接表中。因此，每个站点都会有一个指向其父级、祖父级等的链接。每个关系都是明确的。然后您只需查询该链接表以获取所有后代。

score 3 · Accepted Answer

你可能想看看闭包表模式。我发现这个网站内容丰富。据我所知，还有几个关于这个概念的 StackOverflow 问题，例如，here。

score 3 · Accepted Answer

首先，我会推荐一种不同的存储树的方法：Closure Table。如果你想了解更多，你会发现SQL Antipatterns这本书很有趣。

那就是说。在我看来，生成这种结构的最简单方法是：http: //jsbin.com/omexix/3/edit#javascript

我希望你在阅读 JavaScript 代码时没有问题。我之所以使用它，是因为在 JavaScript 中创建未分类的对象看起来并不那么骇人听闻。通过使用多维数组可以在不中继对象（或引用）的情况下实现相同的功能，但它看起来有点混乱。

这是算法的作用：

我们遍历节点列表，一次
如果节点的父节点不存在，则在数组中创建占位符
如果节点没有父节点，则将其放在根节点列表中
如果节点在数组中没有占位符，则创建占位符
来自节点的值分配给占位符
节点注册到父节点，如果它有父节点

这是关于它的。基本上你会生成两个列表：所有节点，只有根节点。

score 2 · Accepted Answer

根据您在此处的评论，我假设您不愿意更改现有的数据模型，因为数百个应用程序正在使用它（如果用其他东西替换它会中断）。

问题的根源在于，对于任何站点，我们只知道它是直接父站点，因此我们需要递归查找该父站点的父站点，直到找到根站点。

如果您可以摆脱对站点可以嵌套的深度/级别的限制，那么您可以编写一个出色的查询来为您完成所有工作，并且启动速度可能不会那么慢。触发查询的大部分开销来自设置连接、网络带宽等。MySQL 可以非常快。

触发多个查询会使所有开销成倍增加，所以我们不希望这样。执行 SELECT * 然后在应用程序逻辑中计算意味着您每次都会获取所有数据，从而最大化网络开销，所以我们不希望这样。

如果可以接受树的深度限制，您可以将多个查询组合成一个巨大的查询，该查询完成所有工作并返回您需要的确切结果集。作为示例，我使用了您的数据，但将 A、B、C 等替换为 1、2、3（因为您的列是 int）。

要获取根节点的所有直接子节点（site_id = 1），请执行以下操作：

select site_id from site where parent_id = 1

要获取根节点的孙子节点，请执行以下操作：

select grandchild.site_id 
from site grandchild, site child 
where grandchild.parent_id = child.site_id 
and child.parent_id = 1

要获取根节点的曾孙，请执行以下操作：

select greatgrandchild.site_id 
from site greatgrandchild, site grandchild, site child 
where greatgrandchild.parent_id = grandchild.site_id 
and grandchild.parent_id = child.site_id 
and child.parent_id = 1

要获取根节点的所有后代，只需将上述查询组合成一个巨大的查询，如下所示：

select site_id
from site
where site_id in (
    select site_id 
    from site 
    where parent_id = 1
)
or site_id in (
    select grandchild.site_id 
    from site grandchild, site child 
    where grandchild.parent_id = child.site_id 
    and child.parent_id = 1
)
or site_id in (
    select greatgrandchild.site_id 
    from site greatgrandchild, site grandchild, site child 
    where greatgrandchild.parent_id = grandchild.site_id 
    and grandchild.parent_id = child.site_id 
    and child.parent_id = 1
)

我想你明白这是如何工作的。对于每个额外的级别，创建一个查询来查找与您正在搜索后代的站点相距那么多级别的节点，并将该查询添加到带有额外的“或 site_id in ()”的超级查询中......

现在如您所见，仅针对三个级别，这已经成为一个大查询。如果您需要支持 10 个级别，则此查询将变得巨大，并且其中的所有 OR 和 IN 都会减慢它的速度……但是，它仍然可能比获取所有内容或使用多个查询更快。如果您需要支持任意数量的可能级别，则此查询无法为您提供帮助。它必须变得无限大。在那种情况下，剩下的就是使用更好的方法......

也就是说，在您复制粘贴并开始编码之前，有一种方法可以避免如此庞大的查询，支持任意深度并且不会破坏向后兼容性。它确实需要对数据模型进行更改，但它是一个小改动，不会损害使用此数据模型的其他程序。简而言之...

更好的方法

添加一个额外的列 parent_paths，使用他的回答中提到的 ravnur 之类的东西来编码从每个节点一直到根的完整路径

使用插入、更新和删除触发器动态填充该列。您现在正在维护冗余数据。它不会损害其他程序，但可以为您的程序带来显着的性能优势。确保您的触发器是防弹的（这可能是最难的部分），因为额外列中的数据应始终与表中的常规数据同步

使用一个简短而甜蜜的查询，就像一个 ravnur 显示的那样，它在 parent_paths 列中的任何位置查找 site_id 的出现，以直接获取具有该 site_id 的站点的所有后代，而无需任何递归。

score 2 · Accepted Answer

您可以为此创建一个存储过程。

这是我在mysql中的实现

DROP PROCEDURE IF EXISTS SearchTree;
DELIMITER go

CREATE PROCEDURE SearchTree( IN root CHAR(1) )
BEGIN
  DECLARE rows SMALLINT DEFAULT 0;
  DROP TABLE IF EXISTS reached;
  CREATE TABLE reached (
    site_Id CHAR(1) PRIMARY KEY
  ) ENGINE=HEAP;
  INSERT INTO reached VALUES (root);
  SET rows = ROW_COUNT();
  WHILE rows > 0 DO
    INSERT IGNORE INTO reached 
      SELECT DISTINCT s.site_Id 
      FROM site AS s 
      INNER JOIN reached AS r ON s.parent_Id = r.site_Id;
    SET rows = ROW_COUNT();
    DELETE FROM reached 
      WHERE site_Id = root;
  END WHILE;
  SELECT * FROM reached;
  DROP TABLE reached;
END;
go
DELIMITER ;
CALL SearchTree('B');

它返回预期的结果。

score 2 · Accepted Answer

如果您不site经常更新表，则可以使用以下策略：

create table site
(
site_Id int(5),
parent_Id int(5),
site_desc varchar2(100),
parents_path varchar(X)
);

parents_path等于从根到选定节点的路径。例如，对于叶子J，它应该是|A|B|D|。

优点： - 您将需要单个查询来获得结果；

缺点： - 更新期间的更多查询（但您可以明智地进行更新）；

希望能帮助到你

score 2 · Accepted Answer

其他人已经提出了如何通过对表结构进行轻微修改来做到这一点。

如果您不想修改结构（即使这是最好的），那么您可以这样做：

SELECT * FROM site ORDER BY Parent_ID, Site_id;

通常可以安全地假设，一旦分配，ID 就不会改变；如果 ID 没有被打乱，即节点 C 没有移动到节点 B 下，那么子节点的 ID 总是高于其父节点，并且上面的排序将保证所有父节点在其子节点之前被获取.

所以这些是假设：

- we prefer not to change the table layout
- we never change the IDs once assigned
- we never reorder the tree, moving IDs around

因此，可以在内存中创建树（甚至减少查询本身，添加 WHERE Site_ID >= B）。

第一个通过的节点将是 B，并将被放入树中。

所有后续节点都可能存储在它们的 Parent_ID-th 节点中，该节点之前肯定已经加载过。

这在 Python 中会很顺利（您直接修改父节点）。

请求“获取 B 的所有后代”可以在 PHP 中这样回答：

$nodes  = array( $parent_id );

$cursor = SQLQuery("SELECT * FROM site WHERE Site_ID > ? "
        .  "ORDER BY Parent_ID, Site_Id ;", $parent_id);

while ($tuple = SQLFetchTuple($cursor))
    if (in_array($tuple['Parent_ID'], $nodes))
        $nodes[] = $tuple['Site_Id'];
SQLFree($cursor);

// The first node is the global parent, and may be array_shift'ed away
    // if desired.

另一种方式
相当蛮力

另一种可能性是将“descendant_of”关系递归地存储在另一个表中：

    TRUNCATE descendants;
    INSERT INTO descendants ( node, of ) VALUES ( -1, NULL );

    INSERT INTO descendants SELECT SiteId, ParentId FROM site JOIN
           descendants ON ( site.ParentId = descendants.of );

并重复插入，直到插入的行数等于零（或后代中的总行数停止增加；在大多数数据库中查询表大小非常快）。

此时，您将存储所有一级关系。现在：

INSERT IGNORE INTO descendants SELECT s1.node, s2.of FROM
           descendants AS s1 JOIN descendants AS s2 ON (s1.of = s2.node);

...再次直到后代停止增加（它将需要插入数量等于最大级别数）。JOIN 的总数将是级别数的两倍。

现在如果要获取节点 16 的所有后代，只需查询

SELECT node FROM descendants WHERE of = 16;

score 1 · Accepted Answer

我还问自己如何递归查询关系，我的大脑产生了这个解决方案（：

SELECT * FROM
(
    SELECT t2.* FROM table t1, table t2 where t2.parent = t1.id OR t2.parent 0 GROUP BY t2.id, t2.parent
) as all_relations
WHERE all_relations.parent >= '_the_id_'

# if you dont want a subtree use only the inner select

我不是 100% 确定，但我认为只要 id 是自动递增的并且孩子永远不会有一个较小的 id 作为他的父母（这应该是正常情况），那么这可能是一个解决方案吗？

php - 以有效和简单的方式实现层次结构、亲子关系

10 回答 10

Related

Reference