CODEWITHSUNDEEP
sqlhierarchical-datanested-setsupdating
Andre
Andre

Reputation:

How can I update a nested set tree structure?

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?

Upvotes: 3

Views: 4465

Answers (4)

Roger Keays
Roger Keays

Reputation: 3227

Here is a solution that lets you move a node to any position in the tree with just a single input parameter - the new left position (newpos) of the node. This method can't move a node without it's children, but I'd be interested to know your use case for that.

Fundamentally there are three sets:

  • Create new space for the subtree.
  • Move the subtree into this space.
  • Remove the old space vacated by the subtree.

In psuedo-sql, it looks like this:

//
 *  -- create new space for subtree
 *  UPDATE tags SET lpos = lpos + :width WHERE lpos >= :newpos
 *  UPDATE tags SET rpos = rpos + :width WHERE rpos >= :newpos
 * 
 *  -- move subtree into new space
 *  UPDATE tags SET lpos = lpos + :distance, rpos = rpos + :distance
 *           WHERE lpos >= :tmppos AND rpos < :tmppos + :width
 * 
 *  -- remove old space vacated by subtree
 *  UPDATE tags SET lpos = lpos - :width WHERE lpos > :oldrpos
 *  UPDATE tags SET rpos = rpos - :width WHERE rpos > :oldrpos
 */

The :distance variable is the distance between the new and old positions, the :width is the size of the subtree, and :tmppos is used to keep track of the subtree being moved during the updates. These variables are defined as:

// calculate position adjustment variables
int width = node.getRpos() - node.getLpos() + 1;
int distance = newpos - node.getLpos();
int tmppos = node.getLpos();
        
// backwards movement must account for new space
if (distance < 0) {
    distance -= width;
    tmppos += width;
}

For a complete code example, see my blog at

https://rogerkeays.com/how-to-move-a-node-in-nested-sets-with-sql

If you like this solution, please up-vote.

Upvotes: 1

bobince
bobince

Reputation: 536339

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.

Upvotes: 1

Bill Karwin
Bill Karwin

Reputation: 562230

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/%';

Upvotes: 3

tpdi
tpdi

Reputation: 35141

Consider that moving a node is equivalent to deleting the node and all its children, if any, and insertig the node, and its children if any, in the new position.

Now re-read the tech article, working out what the whole table will look like after you do that delete followed by that insert, and you'll find the update that does the same thing.

Upvotes: 0

Related Questions