Переместить узел во вложенном множестве

Question

Мне нужен запрос MySQL, который перемещает узел и все его дочерние элементы во вложенном наборе. Я нашел этот сайт, но эта функция кажется просто нелогичной - в модели с вложенным множеством нет universeid или treeid, а сам код просто длиннее, чем требуется. Единственный дополнительный столбец, который у меня есть в таблице, это parent.

Я не мог просто удалить и снова добавить узел, так как он потеряет свой идентификатор.

Answer 1

Я вижу, что эта тема довольно старая, но все равно остается без ответа. Я пришел сюда из Google и не нашел прямого ответа на этот вопрос.

Итак, после небольшого исследования я нашел довольно простое решение.

Все, что нам нужно, чтобы переместить наш узел, это: положение узла влево и вправо, положение нового родительского узла вправо. Узел на новую позицию может быть перемещен в четыре простых шага:

1. Изменить позиции узла и всех его подузлов на отрицательные значения, которые равны текущим по модулю.
2. Переместить все позиции "вверх", которые больше, чем pos_right текущего узла.
3. Переместить все позиции «вниз», которые больше, чем pos_right нового родительского узла.
4. Изменить позиции текущего узла и всех его подузлов, так что теперь он будет точно "после" (или "вниз") нового родительского узла.

Теперь это теория - реализация этого алгоритма в MySQL (пример с использованием 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;

Пожалуйста, будьте осторожны - в коде SQL все еще могут быть некоторые синтаксические ошибки, потому что я фактически использую этот алгоритм в PHP следующим образом:

$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);
}

Обратите внимание, что код может быть оптимизирован, но я собираюсь оставить его таким, чтобы улучшить читаемость. Также рассмотрите возможность блокировки таблиц, если вы используете вложенные множества в многопользовательских системах.

Надеюсь, что мое сообщение поможет всем, кто найдет решение после меня. Любые комментарии и исправления также приветствуются.

Answer 2

Вот решение, которое позволяет вам перемещать узел в любую позицию в дереве, как в качестве родственного, так и дочернего элемента, используя только один входной параметр - новую левую позицию (newlpos) узла.

Принципиально есть три шага:

• Создать новое пространство для поддерева.
• Переместить поддерево в это пространство.
• Удалите старое пространство, освобожденное поддеревом.

В psuedo-sql это выглядит так:

//
 *  -- 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
 */

Переменная: distance - это расстояние между новой и старой позициями,: width - это размер поддерева, а: tmppos используется для отслеживания перемещения поддерева во время обновлений. Эти переменные определены как:

// 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;
}

Полный пример кода см. В моем блоге по адресу

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

Если вам нравится это решение, пожалуйста, проголосуйте.

Answer 3

Я знаю, что это старый вопрос, но я сам использовал ответ только для SQL Server. Если кто-то захочет, вот код хранимого процесса SQL Server, основанный на принятом ответе.

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

Answer 4

Перемещение поддеревьев очень дорого и сложно в дизайне Nested Sets.

Вы должны рассмотреть другой дизайн для представления деревьев.

Например, если вы используете дизайн Перечисление пути, вы сохраняете список прямых предков каждого узла в виде связанной строки.

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

Затем перемещаем поддерево (скажем, узел 3 перемещается, чтобы стать потомком узла 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, '%');

Answer 5

Уже есть много ответов, но я чувствую, что мой может быть полезен для кого-то. Основываясь на ответе Roger Keays (большое спасибо!), Я написал хранимые процедуры для базы данных mySQL:

-- to move target before specified node
CREATE DEFINER=`root`@`%` PROCEDURE `move_before`(IN target_id int, before_id int)
BEGIN
    SELECT @new_pos := lft FROM dirs WHERE  id = before_id; 
    CALL  move(target_id, @new_pos);
END

-- to move target after specified node
CREATE DEFINER=`root`@`%` PROCEDURE `move_after`(IN target_id int, after_id int)
BEGIN
    SELECT @new_pos := rgt + 1 FROM dirs WHERE  id = after_id;
    CALL  move(target_id, @new_pos);
END

-- to move target to the specified node
CREATE DEFINER=`root`@`%` PROCEDURE `move_in`(IN target_id int, parent_id int)
BEGIN
    SELECT @new_pos := rgt FROM dirs WHERE  id = parent_id;
    CALL  move(target_id, @new_pos);
END

--main procedure to move target before position 
CREATE DEFINER=`root`@`%` PROCEDURE `move`(in target_id int, in  new_pos int)
BEGIN

    SELECT @oldlft :=  lft, @oldrgt :=  rgt 
    FROM dirs 
    WHERE target_id =  id;

    SET @width := @oldrgt - @oldlft +1;
    SET @distance :=  new_pos - @oldlft;
    SET @tmppos := @oldlft;

    IF (@distance <0)
    THEN
        SELECT @distance := @distance - @width;
        SELECT @tmppos := @tmppos + @width;
    END IF;

    -- create new space for subtree
    UPDATE dirs SET lft = lft + @width WHERE lft >=  new_pos;
    UPDATE dirs SET rgt = rgt + @width WHERE rgt >=  new_pos;

    -- move subtree into new space
    UPDATE dirs SET lft = lft + @distance, rgt = rgt + @distance
        WHERE lft >= @tmppos AND rgt < @tmppos + @width;

    -- remove old space vacated by subtree
    UPDATE dirs SET lft = lft - @width WHERE lft > @oldrgt;
    UPDATE dirs SET rgt = rgt - @width WHERE rgt > @oldrgt;

END

Answer 6

# Get Left and Right offsets of both source node (Drag Node) and target node (Drop off Node).
SELECT lft,rgt INTO @sourceNodeLft,@sourceNodeRgt FROM treetest WHERE id=_sourceNodeId;
SELECT lft,rgt INTO @targetNodeLft,@targetNodeRgt FROM treetest WHERE id=_targetNodeId;

# Determine node order direction
SET @direction := IF(@targetNodeLft<@sourceNodeLft,'UP','DOWN'); 

# Determine with of source node (Drag Node)
SET @width := @sourceNodeRgt - @sourceNodeLft + 1;

# Mark all displaced nodes with negative lft and rgt
UPDATE treetest SET lft = 0-lft, rgt = 0-rgt 
                                WHERE lft >= @targetNodeLft AND rgt <= @targetNodeRgt;
UPDATE treetest SET lft = 0-lft, rgt = 0-rgt 
                                WHERE lft >= @sourceNodeLft AND rgt <= @sourceNodeRgt;


# Update left and right offsets of inner nodes between source (Drag Node)and target (Drop off) node
UPDATE treetest SET lft =   (lft + IF(@direction = 'UP',@width,0-@width)),
                                    rgt = (rgt + IF(@direction = 'UP',@width,0-@width))
                                WHERE lft > IF(@direction = 'UP', @targetNodeLft, @sourceNodeLft)
                                            AND rgt < IF(@direction = 'UP', @sourceNodeLft, @targetNodeLft);


# Update source (Drag) Node and its children offsets  
SET @sourceOffset := IF(@direction = 'UP',@targetNodeLft - @sourceNodeLft, @targetNodeRgt - @width - @sourceNodeLft+1);
UPDATE treetest SET lft = 0 - lft + @sourceOffset, 
                                        rgt = 0 - rgt + @sourceOffset
                                WHERE (0-lft) >= @sourceNodeLft AND (0-rgt) <= @sourceNodeRgt;

# Update target (Drop off) node and its children offsets
SET @targetOffset := IF(@direction = 'UP', 0 - @width,@width);
UPDATE treetest SET lft = 0 - (lft + @targetOffset),
                                        rgt = 0 - (rgt + @targetOffset)
                                WHERE (0-lft) >= @targetNodeLft AND (0-rgt) <= @targetNodeRgt;

Answer 7

Я знаю, что это сообщение старое, но я публикую это решение для всех, кто попадет сюда, чтобы увидеть решение. Я нашел этот @ sedna-soft.de. Я проверил идентификатор и работает отлично

 -- 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; 

Answer 8

Это довольно просто, сначала определите хранимую процедуру:

   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

Далее нам понадобятся локальные переменные:

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

Теперь возьмите нашу старую влево и вправо и получите ширину

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

Теперь возьмите их "из дерева", умножив на -1

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

Следующая часть не нужна, так как дерево будет работать без него, но оно аккуратно; закрыть старый пробел:

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

Теперь найдите новое местоположение:

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;

Теперь освободите место:

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

Наконец, переместите узлы, которые были смещены из дерева обратно на * -1, и, пока вы там находитесь, переместите их также в правильное местоположение:

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

Не проверено, вставлено и отрегулировано и упрощено из рабочего режима.

Answer 9

Спасибо за идею преобразования lft и rgt в их отрицательные аналоги. Я разместил более общий подход для этого здесь: Переместить узел в дереве вложенных наборов .

Функция queryBatch () заключает запрос в транзакцию.

Answer 10

$ row - это массив, представляющий строку, которую я должен переместить; должно быть так:

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

$ row2 - массив, представляющий узел судьбы;

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"]);