How do you sort a tree stored using the nested set model?

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_viewASSELECT t2.NodeID,t2.lft,t2.rgt ,t2.Name, COUNT(t1.NodeID) AS level  FROM dbo.tree t1,dbo.tree t2WHERE t2.lft BETWEEN t1.lft AND t1.rgtGROUP BY t2.NodeID,t2.lft,t2.rgt,t2.NameGO----------------------------------------------  DECLARE @CurrentNodeID intDECLARE @CurrentActualOrder intDECLARE @CurrentRequiredOrder intDECLARE @DestinationNodeID intDECLARE @i0 intDECLARE @i1 intDECLARE @i2 intDECLARE @i3 intDECLARE @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 = RequiredOrderWHILE 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 = RequiredOrderEND