Move node in nested set

问题:

I'd need a MySQL query that moves a node and all its children within a nested set. I found this site, but that function just seems so illogical - there's no universeid or treeid in a nested set model, and the code itself is just longer than what feels required. The only extra column I've got in the table is parent.

I couldn't just remove and add the node again since it will loose its ID.

回答1:

I see, that this topic is quite old, but anyway it's still unanswered. I got here from Google, and found no direct answer to this question.

So, after a little research I found quite easy solution.

Everything, what we gonna need to move our node is: node left and right positions, new parent node right position. The node to the new position then can be moved in four easy steps:

1. Change positions of node and all it's sub nodes into negative values, which are equal to current ones by module.
2. Move all positions "up", which are more, that pos_right of current node.
3. Move all positions "down", which are more, that pos_right of new parent node.
4. Change positions of current node and all it's subnodes, so that it's now will be exactly "after" (or "down") of new parent node.

That's theory, now - this algorithm realization in MySQL (example using PHP):

-- step 0: Initialize parameters.
SELECT
    @node_id := 1, --put there id of moving node 
    @node_pos_left := 0, --put there left position of moving node
    @node_pos_right := 1, --put there right position of moving node
    @parent_id := 2, --put there id of new parent node (there moving node should be moved)

    @parent_pos_right := 4; --put there right position of new parent node (there moving node should be moved)
SELECT
    @node_size := @node_pos_right - @node_pos_left + 1; -- 'size' of moving node (including all it's sub nodes)

-- step 1: temporary "remove" moving node

UPDATE `list_items`
SET `pos_left` = 0-(`pos_left`), `pos_right` = 0-(`pos_right`)
WHERE `pos_left` >= @node_pos_left AND `pos_right` <= @node_pos_right;

-- step 2: decrease left and/or right position values of currently 'lower' items (and parents)

UPDATE `list_items`
SET `pos_left` = `pos_left` - @node_size
WHERE `pos_left` > @node_pos_right;
UPDATE `list_items`
SET `pos_right` = `pos_right` - @node_size
WHERE `pos_right` > @node_pos_right;

-- step 3: increase left and/or right position values of future 'lower' items (and parents)

UPDATE `list_items`
SET `pos_left` = `pos_left` + @node_size
WHERE `pos_left` >= IF(@parent_pos_right > @node_pos_right, @parent_pos_right - @node_size, @parent_pos_right);
UPDATE `list_items`
SET `pos_right` = `pos_right` + @node_size
WHERE `pos_right` >= IF(@parent_pos_right > @node_pos_right, @parent_pos_right - @node_size, @parent_pos_right);

-- step 4: move node (ant it's subnodes) and update it's parent item id

UPDATE `list_items`
SET
    `pos_left` = 0-(`pos_left`)+IF(@parent_pos_right > @node_pos_right, @parent_pos_right - @node_pos_right - 1, @parent_pos_right - @node_pos_right - 1 + @node_size),
    `pos_right` = 0-(`pos_right`)+IF(@parent_pos_right > @node_pos_right, @parent_pos_right - @node_pos_right - 1, @parent_pos_right - @node_pos_right - 1 + @node_size)
WHERE `pos_left` <= 0-@node_pos_left AND `pos_right` >= 0-@node_pos_right;
UPDATE `list_items`
SET `parent_item_id` = @parent_id
WHERE `item_id` = @node_id;

Please beware - there still may be some syntax errors in SQL code, because I actually use this algorithm in PHP like this:

$iItemId = 1;
$iItemPosLeft = 0;
$iItemPosRight = 1;
$iParentId = 2;
$iParentPosRight = 4;
$iSize = $iPosRight - $iPosLeft + 1;
$sql = array(

    // step 1: temporary "remove" moving node

    'UPDATE `list_items`
    SET `pos_left` = 0-(`pos_left`), `pos_right` = 0-(`pos_right`)
    WHERE `pos_left` >= "'.$iItemPosLeft.'" AND `pos_right` <= "'.$iItemPosRight.'"',

    // step 2: decrease left and/or right position values of currently 'lower' items (and parents)

    'UPDATE `list_items`
    SET `pos_left` = `pos_left` - '.$iSize.'
    WHERE `pos_left` > "'.$iItemPosRight.'"',
    'UPDATE `list_items`
    SET `pos_right` = `pos_right` - '.$iSize.'
    WHERE `pos_right` > "'.$iItemPosRight.'"',

    // step 3: increase left and/or right position values of future 'lower' items (and parents)

    'UPDATE `list_items`
    SET `pos_left` = `pos_left` + '.$iSize.'
    WHERE `pos_left` >= "'.($iParentPosRight > $iItemPosRight ? $iParentPosRight - $iSize : $iParentPosRight).'"',
    'UPDATE `list_items`
    SET `pos_right` = `pos_right` + '.$iSize.'
    WHERE `pos_right` >= "'.($iParentPosRight > $iItemPosRight ? $iParentPosRight - $iSize : $iParentPosRight).'"',

    // step 4: move node (ant it's subnodes) and update it's parent item id

    'UPDATE `list_items`
    SET
        `pos_left` = 0-(`pos_left`)+'.($iParentPosRight > $iItemPosRight ? $iParentPosRight - $iItemPosRight - 1 : $iParentPosRight - $iItemPosRight - 1 + $iSize).',
        `pos_right` = 0-(`pos_right`)+'.($iParentPosRight > $iItemPosRight ? $iParentPosRight - $iItemPosRight - 1 : $iParentPosRight - $iItemPosRight - 1 + $iSize).'
    WHERE `pos_left` <= "'.(0-$iItemPosLeft).'" AND i.`pos_right` >= "'.(0-$iItemPosRight).'"',
    'UPDATE `list_items`
    SET `parent_item_id` = "'.$iParentItemId.'"
    WHERE `item_id`="'.$iItemId.'"'
);

foreach($sql as $sqlQuery){
    mysql_query($sqlQuery);
}

Please note also, that code may be optimized, but I going to leave it like that for better readability. Also consider table locking if you are using nested sets in multi-user systems.

Hope that my message will help to anyone, who will search for a solution after me. Any comments and corrections are also welcome.

回答2:

Here is a solution that lets you move a node to any position in the tree, either as a sibling or a child with just a single input parameter - the new left position (newlpos) of the node.

Fundamentally there are three steps:

• 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 >= :newlpos
 *  UPDATE tags SET rpos = rpos + :width WHERE rpos >= :newlpos
 * 
 *  -- 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 = newlpos - 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

http://www.ninthavenue.com.au/how-to-move-a-node-in-nested-sets-with-sql

If you like this solution, please up-vote.

回答3:

I know this is an old question, but I've just used the answer myself but for SQL Server. Should anyone want it, here is the code for a SQL Server Stored Proc based on the accepted answer.

CREATE PROCEDURE [dbo].[Item_Move] 
    @id uniqueidentifier, 
    @destinationId uniqueidentifier
AS
BEGIN

    SET NOCOUNT ON;

    declare @moverLeft int,
            @moverRight int,
            @destinationRight int,
            @node_size int

    -- step 0: Initialize parameters.
    SELECT 
        @moverLeft = leftExtent, 
        @moverRight = rightExtent 
    FROM 
        Item 
    WHERE 
        id = @id

    SELECT 
        @destinationRight = rightExtent 
    FROM 
        Item 
    WHERE 
        id = @destinationId

    SELECT
        @node_size = @moverRight - @moverLeft + 1; -- 'size' of moving node (including all it's sub nodes)

    -- step 1: temporary "remove" moving node
    UPDATE Item
    SET leftExtent = 0-(leftExtent), rightExtent = 0-(rightExtent), updatedDate = GETDATE()
    WHERE leftExtent >= @moverLeft AND rightExtent <= @moverRight;

    -- step 2: decrease left and/or right position values of currently 'lower' items (and parents)
    UPDATE Item
    SET leftExtent = leftExtent - @node_size, updatedDate = GETDATE()
    WHERE leftExtent > @moverRight;
    UPDATE Item
    SET rightExtent = rightExtent - @node_size, updatedDate = GETDATE()
    WHERE rightExtent > @moverRight;

    -- step 3: increase left and/or right position values of future 'lower' items (and parents)
    UPDATE Item
    SET leftExtent = leftExtent + @node_size, updatedDate = GETDATE()
    WHERE leftExtent >= CASE WHEN @destinationRight > @moverRight THEN @destinationRight - @node_size ELSE @destinationRight END;
    UPDATE Item
    SET rightExtent = rightExtent + @node_size, updatedDate = GETDATE()
    WHERE rightExtent >= CASE WHEN @destinationRight > @moverRight THEN @destinationRight - @node_size ELSE @destinationRight END;

    -- step 4: move node (and it's subnodes) and update it's parent item id
    UPDATE Item
    SET
        leftExtent = 0-(leftExtent) + CASE WHEN @destinationRight > @moverRight THEN @destinationRight - @moverRight - 1 ELSE @destinationRight - @moverRight - 1 + @node_size END,
        rightExtent = 0-(rightExtent) + CASE WHEN @destinationRight > @moverRight THEN @destinationRight - @moverRight - 1 ELSE @destinationRight - @moverRight - 1 + @node_size END, 
        updatedDate = GETDATE()
    WHERE leftExtent <= 0-@moverLeft AND rightExtent >= 0-@moverRight;
    UPDATE Item
    SET parentId = @destinationId, updatedDate = GETDATE()
    WHERE id = @id;


END

回答4:

Moving subtrees around is very expensive and complex in the Nested Sets design.

You should consider a different design for representing trees.

For example, if you use the Path Enumeration design, you store the list of direct ancestors of each node as a concatenated string.

id path
 1  1/
 2  1/2/
 3  1/3/
 4  1/3/4/
 5  1/3/5/

Then moving a subtree (say node 3 moves to be a child of node 2):

UPDATE Tree t
 JOIN Tree node2 ON (node2.id = 2)
 JOIN Tree node3 ON (node3.id = 3)
SET t.path = CONCAT(node2.path, REPLACE(t.path, node3.path, node2.path))
WHERE t.path LIKE CONCAT(node3.path, '%');

回答5:

See the article in my blog for storing and using hierarchical data in MySQL:

• Hierarchical queries in MySQL

To move a whole branch in such a table, you'll just need to update the root's parent (a single row)

You'll need to create a function:

CREATE FUNCTION hierarchy_connect_by_parent_eq_prior_id(value INT) RETURNS INT
NOT DETERMINISTIC
READS SQL DATA
BEGIN
        DECLARE _id INT;
        DECLARE _parent INT;
        DECLARE _next INT;
        DECLARE CONTINUE HANDLER FOR NOT FOUND SET @id = NULL;

        SET _parent = @id;
        SET _id = -1;

        IF @id IS NULL THEN
                RETURN NULL;
        END IF;

        LOOP
                SELECT  MIN(id)
                INTO    @id
                FROM    t_hierarchy
                WHERE   parent = _parent
                        AND id > _id;
                IF @id IS NOT NULL OR _parent = @start_with THEN
                        SET @level = @level + 1;
                        RETURN @id;
                END IF;
                SET @level := @level - 1;
                SELECT  id, parent
                INTO    _id, _parent
                FROM    t_hierarchy
                WHERE   id = _parent;
        END LOOP;
END

and use it in a query:

SELECT  CONCAT(REPEAT('    ', level - 1), CAST(hi.id AS CHAR)) AS treeitem, parent, level
FROM    (
        SELECT  hierarchy_connect_by_parent_eq_prior_id(id) AS id, @level AS level
        FROM    (
                SELECT  @start_with := 0,
                        @id := @start_with,
                        @level := 0
                ) vars, t_hierarchy
        WHERE   @id IS NOT NULL
        ) ho
JOIN    t_hierarchy hi
ON      hi.id = ho.id

回答6:

I have a stored procedure that moves a node in a nested set to a new parent node. I am using a table called "category" in a MySQL / InnoDB database called "somedb". Of course, if the destination is a subcategory of the category you want to move this procedure will screw things up, so make sure that you aren't trying to embed a node inside of itself. I will leave it as an exercise to the reader to make this procedure safe for that case.

CREATE PROCEDURE `somedb`.`moveCatParent` (IN cat_a VARCHAR(45), IN cat_b VARCHAR(45))
BEGIN
    START TRANSACTION;

    /* cat_b.lft + 1 is the destination. */
    SELECT @destination := (lft + 1)
    FROM category
    WHERE name = cat_b;

    SELECT @cat_a_width := ((rgt - lft) + 1)
    FROM category
    WHERE name = cat_a;

    /* Rip this table a new cat_a sized hole inside cat_b. */  
    UPDATE category SET rgt = rgt + @cat_a_width WHERE rgt >= @destination;
    UPDATE category SET lft = lft + @cat_a_width WHERE lft >= @destination;

    SELECT @cat_a_lft := lft, @cat_a_rgt := rgt
    FROM category
    WHERE name = cat_a;

    SELECT @diff := @destination - @cat_a_lft;

    /* Move cat_a and all inhabitants to new hole */  
    UPDATE category SET rgt = rgt + @diff WHERE rgt BETWEEN @cat_a_lft AND @cat_a_rgt;
    UPDATE category SET lft = lft + @diff WHERE lft BETWEEN @cat_a_lft AND @cat_a_rgt;

    /* Close the gap created when we moved cat_a. */
    UPDATE category SET rgt = rgt - @cat_a_width WHERE rgt >= @cat_a_lft;
    UPDATE category SET lft = lft - @cat_a_width WHERE lft >= @cat_a_lft;

    COMMIT;
END

回答7:

I believe that with two extra columns to store the original Node right and left values (and all subsequent subnodes) the algorithm can be simplified. I have worked the examples with pencil and paper so if you find any holes in the algorithm please let me know.

The target Node (The new parent of Node that you are moving) is tNode. Left value of Target Node is tNode.L and right value is tNode.R. Similarly the node you are moving is mNode and left and right values for mNode are mNode.L and mNode.R. The two extra columns are mNode.SL and mNode.SR

So all in all we have 4 columns for manipulation R,L, SL and SR

---

Step1

calculate

delta1 = (mNode.R - mNode.L) + 1 

Step2

Save the mNode original L and R into SL and SR columns

- For All L between mNode.L and mNode.R 
   mNode.SL = mNode.L ; mNode.L = 0 ;
 - For All R between mNode.L and mNode.R 
   mNode.SR = mNode.R ; mNode.R = 0 ;

Step3

Do For all Nodes
IF L > mNode.SR 
   L = L + delta1
IF R > mNode.SR
   R = R + delta1

Now the mNode is detached from Tree and Tree is adjusted without mNode.

Step4

calculate

delta2 = (tNode.R - mNode.SL)

Step5

Do for all Nodes
  IF L >= tNode.R
    L = L + delta1
  IF R >= tNode.R
    R = R + delta1

Now we have adjusted the Tree (and target node) to accept the number of nodes that were deleted.

Step6

Attach mNode at tNode and reset SL/SR column values

Do for all Nodes
 IF SL between mNode.SL and mNode.SR
    L = mNode.SL + delta2 ; mNode.SL = 0  ;
 IF SR between mNode.SL and mNode.SR
    R = mNode.SR + delta2 ; mNode.SR = 0 ;

After all these steps we should have moved mNode under the tNode.

回答8:

Thanks for the idea of transforming the lft and rgt to their negative counterparts. I posted a more general approach for this here: Move node in Nested Sets tree.

The queryBatch() function encloses the query in a transaction.

回答9:

It is quite simple, first define a stored procedure:

   CREATE DEFINER=`root`@`localhost` PROCEDURE `move_item`(
        IN itemId BIGINT, IN kind SMALLINT, 
        IN newSiblingId BIGINT UNSIGNED, IN newSiblingKind SMALLINT, IN newParentId BIGINT UNSIGNED,
        IN jobId BIGINT UNSIGNED, IN companyId BIGINT UNSIGNED,
        OUT outSucess SMALLINT UNSIGNED)
proc_label:BEGIN

next we need some local variables:

DECLARE oldLeft, oldRight, newLeft, newRight, itemWidth, moveBy INT UNSIGNED DEFAULT 0; 
set outSucess =0;

Now get our old left & right and get the width

SELECT `LFT`, `RGT` into oldLeft, oldRight from `nodes` where `ID`=itemId LIMIT 1;
SET itemWidth = oldRight - oldLeft + 1;

Now take them "out of the tree" by multiplying by -1

UPDATE `nodes` SET `RGT`=`RGT`* -1, `LFT`=`LFT`* -1 WHERE ``LFT` BETWEEN oldLeft and oldRight;

The next part is not necessary as the tree will work without it, but it is neat; close the old gap:

-- Update right
UPDATE `nodes` SET `RGT` = `RGT` - itemWidth WHERE `RGT` > oldRight;
-- Update left
UPDATE `nodes` SET `LFT` = `LFT` - itemWidth WHERE `LFT` > oldRight;

Now find the new location:

SELECT (`RGT`+1) into newLeft from `nodes`  where `ID`=newSiblingId LIMIT 1;

-- No sibling, so make it last in parent
IF (newLeft = 0) AND (newParentId != 0) THEN
  SELECT `RGT` into newLeft from `nodes` WHERE `ID`=newParentId LIMIT 1;
END IF;

 -- If no previous sibling or parent, set to first item in tree
IF (newLeft=0) OR (newLeft=NULL) THEN SET newLeft=1;
END IF;

Now make some space:

 -- Update right
UPDATE `nodes` SET `RGT` = `RGT` + itemWidth WHERE `RGT` >= newLeft;
-- Update left
UPDATE `nodes` SET `LFT` = `LFT` + itemWidth WHERE `LFT` >= newLeft;

Finally move the nodes that where shifted out of the tree back in by * -1, and while you are at it, move them to the correct location as well:

SET moveBy = OldLeft - NewLeft;
UPDATE `nodes` SET `RGT`=(`RGT`* -1)-moveBy, `LFT`=(`LFT`* -1)-moveBy WHERE `LFT` < 0;
set outSucess =1;

Not tested, pasted and adjusted and simplified from a working routine.

回答10:

I know this post is old but im posting this solution for every one else that will get here to see a solution.I found this @ sedna-soft.de . I tested id and works perfectly

 -- moves a subtree before the specified position
 -- if the position is the rgt of a node, the subtree will be its last child
 -- if the position is the lft of a node, the subtree will be inserted before
 -- @param l the lft of the subtree to move
 -- @param r the rgt of the subtree to move
 -- @param p the position to move the subtree before




 SET @r: , @l: , @p: 

 update tree
 set
 lft = lft + if (@p > @r,
    if (@r < lft and lft < @p,
        @l - @r - 1,
        if (@l <= lft and lft < @r,
            @p - @r - 1,
            0
        )
    ),
    if (@p <= lft and lft < @l,
        @r - @l + 1,
        if (@l <= lft and lft < @r,
            @p - @l,
            0
        )
    )
),
rgt = rgt + if (@p > @r,
    if (@r < rgt and rgt < @p,
        @l - @r - 1,
        if (@l < rgt and rgt <= @r,
            @p - @r - 1,
            0
        )
    ),
    if (@p <= rgt and rgt < @l,
        @r - @l + 1,
        if (@l < rgt and rgt <= @r,
            @p - @l,
            0
        )
    )
        )
  where @r < @p or @p < @l; 

回答11:

$row is an array that represents the row I have to move; it must be like this:

Array ( [lft] => 5 [rgt] => 10 [width] => 6 ) 

$row2 is an array that represents the destiny node;

Array ( [id] => 5 [lft] => 2 [rgt] => 17 [width] => 16 ) 

...

mysql_query("UPDATE entryCategory SET rgt = rgt + %d - %d, lft = lft + %d - %d WHERE rgt <= %d and lft >= %d;",$row2["rgt"],$row["lft"],$row2["rgt"],$row["lft"],$row["rgt"],$row["lft"]);
mysql_query("UPDATE entryCategory SET rgt = rgt + %d WHERE id=%d;",$row["width"],$row2["id"]);
mysql_query("UPDATE entryCategory SET rgt = rgt - %d, lft = lft - %d  WHERE rgt > %d and lft > %d;",$row["width"],$row["width"],$row["rgt"],$row["rgt"]);