使用自下而上或自上而下的搜索从分层数据中找到最佳路径 [英] Using bottom-up or top-down search to find the best path from hierarchical data

问题描述

我具有以下表格结构，

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

现在我需要做一些复杂的事情.从此表中找到最佳路径的成本(具有最佳成本的路径).

Now I need to do a sort of complex thing. Find the cost of the best path (path which has the best cost) from this table.

有两种方法，我不确定要使用哪种方法:

There are two ways, I am not sure which one to use:

1. 自下而上的搜索::如果选择该选项，则需要在表中添加isLeaf列，并使用可以完成此任务的CTE.
2. 自上而下的搜索:不需要isLeaf字段，但是很难提出完成该任务的SQL语句.

1. Bottom-up search: If I choose that, I need to add a isLeaf column to the table and use a CTE which does the job.
2. Top-down search: There is no need of isLeaf field, however hard to come up with the SQL statement which does the job.

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

What are the pros and cons of the given two alternative methods? Which is the better practice in terms of performance etc.?

推荐答案

在未指定使用哪个RDBMS之前，我已经写了答案.如果是SQL Server，则在Postrge和Oracle中应该使用相同或相似的东西，而在MySQL中则不能.

I've wrote the answer before seeing it's no specified which RDBMS is used. This if for SQL Server, same or something similar should work in Postrge and Oracle, but not in MySQL.

无论如何，任何一种方式(自下而上或自上而下)都可以，并且两种方式都不必添加isLeaf级别列，因为您可以使用NOT IN或NOT EXISTS子查询轻松找到叶级别节点-并且您需要如果您只对从上到下的路径感兴趣，则可以通过两种方式查看该信息.

Anyway, either way (Bottom-Up or Top-Down) is fine, and neither way you have to add isLeaf level column because you can simply find leaf level nodes with NOT IN or NOT EXISTS subquery - and you need that info in both ways if you are interested in only paths that go from top to bottom.

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

Here is a sample query for top-down search:

;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

以下是自下而上的示例:

Here is example for Bottom-Up:

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

SQLFiddle演示-自底向上

SQLFiddle DEMO - Bottom-Up

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

In this examples, performance of both queries are exactly the same. 50%-50% in execution plans when run together.

这篇关于使用自下而上或自上而下的搜索从分层数据中找到最佳路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！