2

假设我有一张这样的表：

CREATE TABLE IF NOT EXISTS `node_list` (
    `nid` int(11) NOT NULL AUTO_INCREMENT,
    `parent` int(11)
        COMMENT \'Node`s parent (nid).\',
    PRIMARY KEY (`nid`)
)

对于给定的节点 ID，我想计算其所有后代的数量。然而：

SELECT COUNT(*) FROM `node_list` WHERE `parent`=?

仅返回直接子级的计数。for在没有混乱循环的情况下这样做的好方法是什么？

4

4 回答 4

1

鉴于这些限制，没有办法。在这种情况下，您要么检索所有树并构建一个“山”客户端，要么执行递归查询，无论在特定情况下性能如何。

通过具有固定数量的层次结构级别的附加约束，您可以使用多个 JOIN 来执行此操作。

在一般情况下，有几个结构修改可以克服这些限制。在实践中，您放宽了“这是我的表结构”的约束，允许添加额外的字段。

例如，您可以用一个left_id值来补充节点结构，并确保在深度优先访问树时所有节点 ID 都是按顺序排列的：

1 --- 2 -+- 3 -+- 4
         |     |
         |     +- 5
         +- 6 --- 7

在这种情况下，节点 3 将存储值“5”，节点 6 将存储值“7”，节点 2 也将存储值“7”。每个节点将其子节点的 LeftID 与其自己的 ID 之间的最大值存储在 LeftID 中。

所以无子节点的 LeftID 等于它们的 ID。节点 1 的 LeftID 为 7，因为 LeftID 为 2，它是从 6 得到的。

在这种情况下，如果序列中没有空洞，则很容易计算节点；一个节点的所有后代都是那些 ID 在起始节点的 ID 和它的 LeftID 之间的节点；叶子通过 LeftID 等于 ID 来识别。

所以“从节点 id 17 下降的所有叶子”将是

SELECT child.* FROM table AS parent JOIN table AS child ON (child.id > parent.id AND child.id <= parent.leftid ) /* Descendant / WHERE child.id = child.leftid / Leaf / AND parent.id = 17; /父母 17 岁

如果您希望能够进行修剪和分支，则这种结构很难维护，因为您需要重新编号从修剪点到分支点之间的所有节点，以及移动的节点。

如果您只对计数感兴趣，另一种可能性是保留一个儿童计数器。这可以通过迭代更新它来维护，选择所有叶子并将它们的计数器设置为 0（您通过 LEFT JOIN 识别叶子）；然后所有那些有 NULL 计数器的父母有非 NULL 计数器的孩子，将他们的计数器更新SUM()为孩子的计数器加上COUNT()孩子自己的计数器；并继续直到更新的行数变为零，因为所有节点都有非 NULL 计数器。在修剪和分支之后，您只需将所有计数器设置为 NULL 并重复。

最后一种方法需要为每个层次结构级别进行反射连接。

于 2012-10-04T20:42:21.437 回答
0

再挖一点...

With Nodes As 
( 
Select s.nid, s.parent
From nodelist s
Where s.nid = @ParentID 
Union All 
Select s2.nid, s2.parent
From nodelist s2
    Join Nodes
        On Nodes.nid = s2.parent 
) 
Select Count(*)
From Nodes
于 2012-10-04T20:03:42.700 回答
0 
$tree = array();
$tree[0][1] = 'Electronics';    
$tree[0][0][1] = 'Mobile';  
$tree[0][0][0][2] = 'Samsung';  
$tree[0][0][0][0][3] = ' Toppings Flip Cover for Samsung Galaxy S6';    
$tree[0][0][0][0][0][4] = 'Maac Online Flip Cover for Samsung Galaxy S6';   
$tree[0][0][0][0][0][0][5] = 'Shine Flip Cover for Samsung Galaxy S6';  
$tree[0][0][0][0][0][0][0][6] = 'SNE Flip Cover for Samsung Galaxy S6';

print_r($tree);
于 2015-12-01T06:22:30.807 回答
-1

对于具有已知最大层数的层次结构，您可以使用级联连接执行单个查询以查找记录计数。如果层数大于三层或四层，这可能不漂亮，但应该可以。

select count(*)
from node_list n1
outer join node_list n2 on n2.parent = n1.nid
outer join node_list n3 on n3.parent = n2.nid
outer join node_list n4 on n4.parent = n3.nid

...依此类推，您可以根据需要设置多个级别。尽量不要太多，否则性能可能会受到影响。

在现实世界中，大多数等级系统的深度实际上是相当有限的。即使它们在理论上是无限的。例如，站点菜单可能允许无限级别的结构，但超过三到四个就很难使用。是否对嵌套施加限制取决于您，但这可能会使事情变得更容易。

但是，如果您确实有一个开放式层次结构，您不知道它可以走多远，或者如果上述查询太慢，那么您将需要一个循环。该循环是在 MySQL 存储过程中还是在 PHP 中都无关紧要。您将需要一种方式或另一种方式的循环。不过，它当然不需要for你担心的循环混乱。

我会用递归 PHP 函数来做。也许是这样的：

function countDescendants($db, $nid) {
    $total = 0;
    $query = "select nid from Nodes where parent = ".(int)$nid;
    $res = $db->query($query);
    foreach($res as $data) {
        $total += countDescendants($db, $data['nid']);
    }
    $total += $res->num_rows;
    return $total;
}

然后你可以调用它并用一行代码得到你的答案：

$number_of_descendants = countDescendants($starting_nid);

一个相当简单的递归函数（我假设您正在使用mysqli您的数据库，并且您的连接已经排序以传递给函数）。

当然，如果你有一个非常大的层次结构，或者你要多次查询它，它可能会有点慢，但有一些方法可以通过改进我给出的这个基本示例来加速它。例如，您可以使用准备好的语句查询，并使用不同的 nid 值填充相同的语句：这将节省大部分数据库工作。但是对于小层次结构的简单使用，上面的代码应该没问题。

使用这些技术中的任何一个的一个大缺陷是，如果您的节点结构中有一个循环——即，一个节点具有它自己的一个后代作为它的父 ID。这种情况会导致上述 PHP 代码出现无限循环，并且在嵌套连接 SQL 查询的情况下会导致记录计数严重倾斜。无论哪种情况，如果您的系统可能出现这种情况，您将需要针对它编写代码。但这确实使事情复杂化，所以我不会在这里讨论它。

希望有帮助。

（注意：上面的代码未经测试：我直接将其输入答案而没有运行它；如果有任何错别字，我们深表歉意）

于 2012-10-04T20:40:54.827 回答