如何使用嵌套集模型对存储的树进行排序？

Question

当我提到嵌套集模型时，我指的是描述这里。的内容

我需要在用户定义的层次结构中构建一个新的系统来存储“类别”(我想不出更好的词)。由于嵌套的set模型是为读而不是写而优化的，所以我决定使用它。不幸的是，在我对嵌套集的研究和测试中，我遇到了如何用排序节点显示分层树的问题。例如，如果我有层次结构：

root
    finances
        budgeting
            fy08
    projects
        research
        fabrication
        release
    trash

我希望对其进行排序，使其显示为：

root
    finances
        budgeting
            fy08
    projects
        fabrication
        release
        research
    trash

请注意，这种捏造出现在研究之前。

无论如何，经过长时间的搜索，我看到了这样的答案：“将树存储在多维数组中并对其进行排序”和“使用树并将其序列化回嵌套的集合模型”(我正在对.)。不管怎样，第一种解决方案是对RAM和CPU的可怕浪费，它们都是非常有限的资源.第二个解决方案看起来就像很多痛苦的代码。

无论如何，我能够弄清楚如何(使用嵌套的集合模型)：

1. 在SQL中启动一棵新树
2. 插入节点作为树中另一个节点的子节点
3. 在树中的兄弟节点之后插入节点
4. 从SQL中用层次结构拉出整个树。
5. 在有或没有深度限制的情况下，从层次结构中的特定节点(包括根)中提取子树。
6. 查找树中任何节点的父节点。

因此，我认为#5和#6可以用来进行我想要的排序，也可以用来按排序顺序重建树。

但是，现在我已经学习了所有这些事情，我看到#3、#5和#6可以一起使用来执行排序插入。如果我做了排序插入，它总是排序。但是，如果我改变了排序标准，或者我想要一个不同的排序顺序，我就回到原点。

这仅仅是嵌套集模型的局限性吗？在输出的查询排序中，它的使用是否受到抑制？

Answer 1

我认为这确实是嵌套集模型的一个限制。您无法轻松地对子节点在其各自的父节点中进行排序，因为结果集的排序对于重构树结构至关重要。

我认为这可能是在插入、更新或删除节点时保持树排序的最佳方法。这甚至使得查询速度非常快，这是这种数据结构的主要目标之一。如果为所有操作实现存储过程，则非常容易使用。

您还可以反转预先设定的树的排序顺序。您只需使用ORDER BY node.rgt DESC而不是ORDER BY node.lft ASC。

如果确实需要支持另一种分类条件，则可以通过向每个节点添加第二个lft和rgt索引来实现它，并在每个insert/update/delete上按照其他条件对其进行排序。

Answer 2

我经常使用嵌套集，而且经常遇到同样的问题。我所做的，以及我所建议的，就是不要对数据库中的项目进行排序。相反，在用户界面中对它们进行排序。在您从DB中提取所有节点之后，您可能必须将它们转换成某种分层的数据结构。在该结构中，对包含节点子节点的所有数组进行排序。

例如，如果您的前端是Flex应用程序，并且节点的子节点存储在ICollectionView中，则可以使用排序属性让它们以您想要的方式显示。

另一个例子是，如果您的前端是来自PHP脚本的一些输出，则可以在数组中包含每个节点的子节点，并使用PHP的数组排序函数来执行排序。

当然，只有在不需要对实际的db条目进行排序的情况下，才能这样做，但您会这样做吗？

Answer 3

我刚刚完成了对整个嵌套集树排序的下列工作。

排序(理想情况下)需要一个视图，列出树中每个节点的当前级别，以及交换两个节点的过程--这两个步骤都包括在下面，兄弟交换代码来自Joe Celkos的tree &Hierarchies书，我强烈推荐给任何使用嵌套集的人。

可以在‘InsertInto@t’语句中更改排序，这里是'Name‘上的简单字母数字排序。

这可能是一种糟糕的方法，尤其是对基于集合的代码使用游标，但正如我所说的，希望它对我有帮助。

更新：

下面的代码现在显示的版本没有使用垫子。我看到了大约10倍的速度提高

CREATE VIEW dbo.tree_view

AS

SELECT t2.NodeID,t2.lft,t2.rgt ,t2.Name, COUNT(t1.NodeID) AS level  
FROM dbo.tree t1,dbo.tree t2
WHERE t2.lft BETWEEN t1.lft AND t1.rgt
GROUP BY t2.NodeID,t2.lft,t2.rgt,t2.Name

GO

----------------------------------------------

  DECLARE @CurrentNodeID int
DECLARE @CurrentActualOrder int
DECLARE @CurrentRequiredOrder int
DECLARE @DestinationNodeID int
DECLARE @i0 int
DECLARE @i1 int
DECLARE @i2 int
DECLARE @i3 int

DECLARE @t TABLE (TopLft int,NodeID int NOT NULL,lft int NOT NULL,rgt int NOT NULL,Name varchar(50),RequiredOrder int NOT NULL,ActualOrder int NOT NULL)


INSERT INTO @t (toplft,NodeID,lft,rgt,Name,RequiredOrder,ActualOrder)
    SELECT tv2.lft,tv1.NodeID,tv1.lft,tv1.rgt,tv1.Name,ROW_NUMBER() OVER(PARTITION BY tv2.lft ORDER BY tv1.ColumnToSort),ROW_NUMBER() OVER(PARTITION BY tv2.lft ORDER BY tv1.lft ASC)
    FROM dbo.tree_view tv1 
    LEFT OUTER JOIN dbo.tree_view tv2 ON tv1.lft > tv2.lft and tv1.lft < tv2.rgt and tv1.level = tv2.level+1
    WHERE tv2.rgt > tv2.lft+1

    DELETE FROM @t where ActualOrder = RequiredOrder


WHILE EXISTS(SELECT * FROM @t WHERE ActualOrder <> RequiredOrder)
BEGIN


    SELECT Top 1 @CurrentNodeID = NodeID,@CurrentActualOrder = ActualOrder,@CurrentRequiredOrder = RequiredOrder
    FROM @t 
    WHERE ActualOrder <> RequiredOrder
    ORDER BY toplft,requiredorder

    SELECT @DestinationNodeID = NodeID
    FROM @t WHERE ActualOrder = @CurrentRequiredOrder AND TopLft = (SELECT TopLft FROM @t WHERE NodeID = @CurrentNodeID) 

    SELECT @i0 = CASE WHEN c.lft < d.lft THEN c.lft ELSE d.lft END,
            @i1 =  CASE WHEN c.lft < d.lft THEN c.rgt ELSE d.rgt END,
            @i2 =  CASE WHEN c.lft < d.lft THEN d.lft ELSE c.lft END,
            @i3 =  CASE WHEN c.lft < d.lft THEN d.rgt ELSE c.rgt END
    FROM dbo.tree c
    CROSS JOIN dbo.tree d
    WHERE c.NodeID = @CurrentNodeID AND d.NodeID = @DestinationNodeID

    UPDATE dbo.tree
    SET lft = CASE  WHEN lft BETWEEN @i0 AND @i1 THEN @i3 + lft - @i1
                    WHEN lft BETWEEN @i2 AND @i3 THEN @i0 + lft - @i2
            ELSE @i0 + @i3 + lft - @i1 - @i2
            END,
        rgt = CASE  WHEN rgt BETWEEN @i0 AND @i1 THEN @i3 + rgt - @i1
                    WHEN rgt BETWEEN @i2 AND @i3 THEN @i0 + rgt - @i2
            ELSE @i0 + @i3 + rgt - @i1 - @i2
            END
    WHERE lft BETWEEN @i0 AND @i3 
    AND @i0 < @i1
    AND @i1 < @i2
    AND @i2 < @i3

    UPDATE @t SET actualorder = @CurrentRequiredOrder where NodeID = @CurrentNodeID
    UPDATE @t SET actualorder = @CurrentActualOrder where NodeID = @DestinationNodeID

    DELETE FROM @t where ActualOrder = RequiredOrder

END