How can I update a nested set tree structure?

Question

I've looked at Managing Hierarchical Data in MySQL, but it really only deals with adding and deleting nodes in a Nested Set Model.

I need to be able to move nodes with and without child nodes.

How would I do this?

Answer 1

The Nested Sets design isn't a good choice for this kind of change to a tree. It's really complicated to recalculate the right/left numbers as you move nodes around.

The Adjacency List is the easiest tree design for moving subtrees:

UPDATE TreeTable
SET parent = $newparent
WHERE id = 123;

The Path Enumeration design also makes it easy to relocate a node and its children:

UPDATE TreeTable
SET path = REPLACE(path, 'A/B/C/', 'A/D/F/') -- MySQL function
WHERE path LIKE 'A/B/C/%';

Answer 2

Moving with child nodes:

In classic nested sets where the ‘left’ and ‘right’ values are all in a contiguous block of 0..n*2 values, there will be a range of rows that moves either ‘x’ places to the left or ‘x’ places to the right when the subtree is moved, where ‘x’ is the number of left/right values being moved. eg.

A: 1,6
   B: 2,3
   C: 4,5
D: 7,8
E: 9,10

If you moved ‘A’ with descendents to between ‘D’ and ‘E’, everything to the right of ‘A’ but to the left of ‘E’ needs to have its left/right indexes reduced by 6 (the size of ‘A’ with descendents):

UPDATE things
SET nsl=nsl+(
    IF nsl BETWEEN 1 AND 6 THEN 6  -- A-C go forward 6
    ELSE -6                        -- D goes back 6
), nsr=nsr+(                       -- same again
    IF nsl BETWEEN 1 AND 6 THEN 6
    ELSE -6
)
WHERE
    nsl BETWEEN 1 AND 6            -- select A-C
    OR nsl BETWEEN 7 AND 8         -- select D

Moving without child nodes is more complicated. The contained nodes have to go back one, the nodes after the removed node all have to go back two, then the nodes after the new insertion point have to go forward two to make room.

Whilst you can do this in the same style as above, it's starting to get really confusing and you might like to consider alternative approaches such as rewriting all the left/right values manually or using a different schema type that makes these kinds of operations simpler, such as a full ancestor-descendent adjacency relation.