sql - 使用自下而上或自上而下的搜索从分层数据中找到最佳路径

Question

我有以下表结构，

Create Table Nodes
(
    NodeID int,
    ParentNodeID int, // null if root node
    NodeText nvarchar(100),
    NodeCost int
)

现在我需要做一些复杂的事情。从此表中找出最佳路径（成本最高的路径）的成本。

有两种方法，我不确定使用哪一种：

1. 自下而上搜索：如果我选择它，我需要isLeaf在表中添加一列并使用完成这项工作的 CTE。
2. 自上而下搜索：不需要isLeaf字段，但很难想出完成这项工作的 SQL 语句。

给定的两种替代方法的优缺点是什么？在性能等方面哪个是更好的做法？

Answer 1

在看到没有指定使用哪个 RDBMS 之前，我已经写了答案。如果对于 SQL Server，相同或类似的东西应该在 Postrge 和 Oracle 中工作，但在 MySQL 中不行。

无论如何，无论哪种方式（自下而上或自上而下）都可以，而且您不必添加isLeaf级别列，因为您可以简单地找到具有 NOT IN 或 NOT EXISTS 子查询的叶级节点 - 如果您需要两种方式的信息您只对从上到下的路径感兴趣。

以下是自上而下搜索的示例查询：

;WITH rCTE AS 
(
    SELECT  NodeID ,
            ParentNodeID ,
            CAST(NodeID AS NVARCHAR(MAX)) AS PathIDs,
            CAST(NodeText AS NVARCHAR(MAX)) AS PathText,
            NodeCost AS PathCost
    FROM Nodes WHERE ParentNodeID IS NULL
    UNION ALL
    SELECT  n.NodeID ,
            n.ParentNodeID ,
            r.PathIDs  + '-' + CAST(n.NodeID AS NVARCHAR(10)) AS PathIDs,
            r.PathText + '-' + n.NodeText AS PathText,
            r.PathCost  + n.NodeCost AS PathCost
    FROM rCTE r
    INNER JOIN dbo.Nodes n ON n.ParentNodeID = r.NodeID
)
SELECT  PathIDs ,
        PathText ,
        PathCost     
FROM rCTE r
WHERE NOT EXISTS (SELECT * FROM Nodes n WHERE r.NodeID = n.ParentNodeID)
ORDER BY PathCost

以下是自下而上的示例：

;WITH rCTE AS 
(
    SELECT  NodeID ,
            ParentNodeID ,
            CAST(NodeID AS NVARCHAR(MAX)) AS PathIDs,
            CAST(NodeText AS NVARCHAR(MAX)) AS PathText,
            NodeCost AS PathCost
    FROM Nodes r WHERE NOT EXISTS (SELECT * FROM Nodes n WHERE r.NodeID = n.ParentNodeID)
    UNION ALL
    SELECT  n.NodeID ,
            n.ParentNodeID ,
            r.PathIDs  + '-' + CAST(n.NodeID AS NVARCHAR(10)) AS PathIDs,
            r.PathText + '-' + n.NodeText AS PathText,
            r.PathCost  + n.NodeCost AS PathCost
    FROM rCTE r
    INNER JOIN dbo.Nodes n ON r.ParentNodeID = n.NodeID
)
SELECT  PathIDs ,
        PathText ,
        PathCost     
FROM rCTE r
WHERE r.ParentNodeID IS NULL 
ORDER BY PathCost

SQLFiddle 演示 - 自上而下

SQLFiddle 演示 - 自下而上

在此示例中，两个查询的性能完全相同。一起运行时执行计划中的 50%-50%。