Search code examples
mysqltreenestedhierarchical-datanested-sets

Move node in Nested Sets tree

I am working on an adjacency list with mySQL and can not (atleast by myself) do the thinking needed to make a decent enough query to be able to move a set of nodes (together with eventual children nodes) around.

The table has following columns:

 id     name     left     right

Thanks a lot!

Solution

  • I'm pretty sure that table is using the Nested Sets design, not Adjacency List. If it were using Adjacency List, it would have a column like parent_id instead of left and right.

    Moving nodes is royal PITA in Nested Sets. You have to renumber all the left and right values for each node you move.

    If you move a subtree, the easiest way to do this is to remove the nodes one at a time, renumbering the left and right fields after each node removal. Then once you have removed the whole subtree (and preserved the structure of the subtree in your application somehow), re-insert the subtree at its destination location in the tree, again re-numbering the left and right fields per insert.

    update: I recently wrote a blog about how to move subtrees in a different hierarchical data design which I like better than nested sets. I call this design Closure Table.
    See http://www.mysqlperformanceblog.com/2011/02/14/moving-subtrees-in-closure-table/