采用自下而上或自上而下搜索从分层数据

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 DEMO - Top-Down

SQLFiddle DEMO - Bottom-Up

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