0

在我需要处理的事情中，在给定时间，我需要找到具有 0 个或 1 个子节点的树的所有节点（使用物化路径 + 相邻节点创建）。这些列类似于：

id int  
parent_node int  
treepath VARCHAR(255)  
deepness int

当我试图提出解决方案时，我只能想到非常复杂的查询，这些查询会使用太多的子查询或表连接。

对于具有 0 个子节点的节点，我一直在考虑搜索 parent_id 未引用且位于子树内的所有节点。

SELECT *
FROM user_tree
WHERE
    node_id NOT IN (
        SELECT parent_id
        FROM user_tree
        WHERE parent_id IS NOT NULL
    )
    AND
    treepath LIKE 
        (
            SELECT CONCAT(treepath, '/%')
            FROM user_tree
            WHERE node_id = 4
        )

使用 EXPLAIN，这对于数据库来说似乎有点痛苦，因为获取节点列表需要多长时间。

是否有一种非非常痛苦的方式（在性能方面）来进行查找我想要的查询？

编辑：
根据要求，这是表格的一些示例格式：

id      parent_id   treepath    deepness
1       NULL        1           0
2       NULL        2           0
3       1           1/3         1
4       1           1/4         1
5       4           1/4/5       2
7       3           1/3/7       2
8       3           1/3/8       2
9       7           1/3/7/11    3
4

4 回答 4

2

如果没有样本数据，这只是一个猜测：

SELECT t1.*, t2.numchildren
FROM user_tree t1
LEFT JOIN ( SELECT parent_id, COUNT(*) AS numchildren
            FROM user_tree
            GROUP BY parent_id ) t2
ON t1.id = t2.parent_id
WHERE t2.numchildren IS NULL
OR t2.numchildren = 1;

来自示例数据的 SQL-Fiddle

于 2013-09-08T12:42:49.577 回答
1

询问

SELECT parent_id, COUNT(id) AS n FROM user_tree GROUP BY parent_id HAVING n = 1

发现有一个孩子的父母。您可能需要添加 INDEX(parent_id)。

询问

SELECT id FROM user_tree WHERE id NOT IN (SELECT DISTINCT parent_id FROM user_tree)

找到叶子。相同的索引会有所帮助。

于 2013-09-08T12:41:17.297 回答
0

您的查询逻辑是正确的。我会将条件移至from子句，因为这通常可以更好地优化：

SELECT ut.*
FROM user_tree ut join
     (select CONCAT(treepath, '/%') as treepath4
      FROM user_tree
      WHERE node_id = 4
     ) node4 
     on ut.treepath LIKE node4.treepath4 left outer join
     user_tree child
     on child.parent_id = ut.node_id
WHERE ut.treepath LIKE node4.treepath4 and
      child.node_id is null;

对于 0 或 1 个孩子：

SELECT ut.*
FROM user_tree ut join
     (select CONCAT(treepath, '/%') as treepath4
      FROM user_tree
      WHERE node_id = 4
     ) node4
     on ut.treepath LIKE node4.treepath4 left outer join
     user_tree child
     on child.parent_id = ut.node_id
GROUP BY ut.node_id
HAVING count(child.node_id) in (0, 1);
于 2013-09-08T12:43:24.383 回答
0

或者，您可以将新字段添加children_count到表中。这将大大优化这个特定的查询。但是您会在添加/删除节点上浪费一些时间。

于 2013-09-08T12:45:20.343 回答