如何对使用嵌套集模型存储的树进行排序?[英] How do you sort a tree stored using the nested set model?

本文是小编为大家收集整理的关于如何对使用嵌套集模型存储的树进行排序?的处理/解决方法,可以参考本文帮助大家快速定位并解决问题,中文翻译不准确的可切换到English标签页查看源文。

问题描述

当我参考嵌套集模型时,我的意思是所描述的在这里.

我需要在用户定义的层次结构中构建一个用于存储"类别"(我想不出更好的单词)的新系统.由于嵌套集模型是针对读取而不是写入的,因此我决定使用它.不幸的是,在对嵌套集的研究和测试期间,我遇到了一个问题,即如何用分类的节点显示分层树.例如,如果我有层次结构:

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. 从层次结构中从特定节点(包括根)中拉出子树,有或没有深度极限
  7. 在树上找到任何节点的父

所以我认为#5和#6可以用来进行我想要的分类,也可以用来按排序顺序重建树.

但是,既然我已经看了所有这些事情,我看到了#3,#5和#6可以一起使用来执行排序的插入.如果我确实对插入件进行了排序,总是会分类.但是,如果我更改了排序标准,或者我想要其他排序订单,我会返回正方形.

这只是嵌套集模型的限制吗?它的使用是否抑制了输出的查询排序?

推荐答案

我认为这确实是嵌套集模型的限制.您不能轻易地对其各自的父节点中的子节点进行分类,因为结果集的排序对于重建树结构至关重要.

我认为这可能是在插入,更新或删除节点时保持树对树进行排序的最佳方法.这甚至使查询非常快,这是该数据结构的主要目标之一.如果您为所有操作实施存储过程,则非常易于使用.

您还可以扭转预分类树的排序顺序.您只需要使用ORDER BY node.rgt DESC而不是ORDER BY node.lft ASC.

如果您确实需要支持其他类型的标准,则可以通过向每个节点添加第二个lft和rgt索引来实现它,并在每个插入/update/delete上保留其他标准./p>

其他推荐答案

我经常使用嵌套集,我经常遇到相同的问题.我要做的以及建议的是不要对数据库中的项目进行排序.相反,将它们在用户界面中进行排序.无论如何,在从数据库中提取所有节点后,您可能必须将它们转换为一些分层数据结构.在该结构中,对所有包含节点孩子的阵列进行排序.

例如,如果您的前端是Flex应用程序,并且节点的孩子存储在IcollectionView中,则可以使用Sort属性以使它们显示为您想要的方式.

另一个示例,如果您的前端是来自PHP脚本的某些输出,则可以将每个节点的儿童放在数组中,并使用PHP的数组排序函数执行您的排序.

当然,这仅在您不需要实际的DB条目进行排序的情况下才起作用,但是您吗?

其他推荐答案

我刚刚完成了以下内容,这些内容适合我对整个嵌套集树进行排序.

排序(理想情况下)需要一个视图,该视图列出了树中每个节点的当前级别以及一个交换两个节点的过程 - 两者都包括下面,兄弟姐妹交换代码来自Joe Celkos的Tree&Hierarchies的书籍,我强烈建议使用嵌套集的任何人.

可以在"插入到@t"语句中更改排序,这是"名称"

的简单字母数字排序

这可能是一种糟糕的方法,尤其是使用光标用于基于集的代码,但是正如我所说的那样,希望它能有所帮助.

更新:

代码下面的代码现在显示不使用Cusor的版本.我看到大约有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

本文地址:https://www.itbaoku.cn/post/597490.html

问题描述

When I refer to nested set model I mean what is described here.

I need to build a new system for storing "categories" (I can't think of better word for it) in a user defined hierarchy. Since the nested set model is optimized for reads instead of writes, I decided to use that. Unfortunately during my research and testing of nested sets, I ran into the problem of how do I display the hierarchical tree with sorted nodes. For example if I have the hierarchy:

root
    finances
        budgeting
            fy08
    projects
        research
        fabrication
        release
    trash

I want that to be sorted so that it displays as:

root
    finances
        budgeting
            fy08
    projects
        fabrication
        release
        research
    trash

Notice that the fabrication appears before research.

Anyway, after a long search I saw answer such as "store the tree in a multi-dimensional array and sort it" and "resort the tree and serialized back into your nested set model" (I'm paraphrazing...). Either way, the first solution is a horrible waste of RAM and CPU, which are both very finite resources... The second solution just looks like a lot of painful code.

Regardless, I was able to figure out how to (using the nested set model):

  1. Start a new tree in SQL
  2. Insert a node as a child of another node in tree
  3. Insert a node after a sibling node in the tree
  4. Pull the entire tree with the hierarchy structure from SQL
  5. Pull a subtree from a specific node (including root) in the hierarchy with or without a depth limit
  6. Find the parent of any node in the tree

So I figured #5 and #6 could be used to do the sorting I wanted, and it could also be used to rebuild the tree in sorted order as well.

However, now that I've looked at all of these things I've learned to do I see that #3, #5, and #6 could be used together to perform sorted inserts. If I did sorted inserts it always be sorted. However, if I ever change the sort criteria or I want a different sort order I'm back to square one.

Could this just be the limitation of the nested set model? Does its use inhibit in query sorting of the output?

推荐答案

I think this is indeed a limitation of the nested set model. You can not easily sort the child nodes within their respective parent node, because the ordering of the result set is essential to reconstruct the tree structure.

I think it is probably the best approach to keep the tree sorted when inserting, updating or deleting nodes. This even makes queries very fast, which is one of the main goals of this data structure. If you implement stored procedures for all operations, it is very easy to use.

You can also reverse the sort order of a presorted tree. You just have to use ORDER BY node.rgt DESC instead of ORDER BY node.lft ASC.

If you really need to support another sort criteria, you could possible implement it by adding a second lft and rgt index to each node and keep this sorted by the other criteria on every insert/update/delete.

其他推荐答案

I have used Nested Sets a lot and I have faced the same problem often. What I do, and what I would recommend, is to just not sort the items in the database. Instead, sort them in the user interface. After you pulled all the nodes from the DB, you likely have to convert them into some hierarchical data structure, anyway. In that structure, sort all the arrays containing the node's children.

For example, if your frontend is a Flex app, and the children of a node are stored in an ICollectionView, you can use the sort property to have them display the way you want.

Another example, if your frontend is some output from a PHP script, you could have the children of each node in an array and use PHP's array sorting functions to perform your sorting.

Of course, this only works if you don't need the actual db entries to be sorted, but do you?

其他推荐答案

I have just finished writing the following which works for me in sorting an entire nested set tree.

The sort (ideally) requires a view that lists the current level of each node in the tree and a procedure for swapping two nodes - both are included below, the sibling swap code comes from Joe Celkos ' Tree & Hierarchies' book which I strongly recommend to anyone using nested sets.

The sort can be altered in the 'INSERT INTO @t' statement, here it is a simple alphanumeric sort on 'Name'

This may be a poor way of doing it especially using the cursor for set based code but as I say it works for me, hope it helps.

UPDATE:

Code below now shows version without using cusor. I see about 10x speed improvements

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