Переместить node во вложенный набор

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

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

Ответы

Ответ 1

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

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

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

  • Изменить позиции node и всех его узлов на отрицательные значения, которые по модулю равны текущим.
  • Переместите все позиции "вверх", которые больше, то pos_right текущего node.
  • Переместить все позиции "вниз", что больше, это pos_right нового родителя node.
  • Изменить позиции текущего node и всех его подносов, чтобы теперь он был точно "после" (или "вниз" ) нового родителя node.

Эта теория, теперь - реализация этого алгоритма в 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 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 subnodes) and update it 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` <= [email protected]_pos_left AND `pos_right` >= [email protected]_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 subnodes) and update it 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);
}

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

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

Ответ 2

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

В принципе есть три шага:

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

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

Переменная расстояния - это расстояние между новой и старой позициями, ширина: - размер поддерева, и: 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

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

Ответ 3

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

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 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 subnodes) and update it 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 <= [email protected] AND rightExtent >= [email protected];
    UPDATE Item
    SET parentId = @destinationId, updatedDate = GETDATE()
    WHERE id = @id;


END

Ответ 4

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

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

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

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

Затем перемещение поддерева (скажем, node 3 переходит в дочернее состояние 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

См. статью в моем блоге для хранения и использования иерархических данных в MySQL:

Чтобы переместить целую ветку в такую ​​таблицу, вам просто нужно обновить корневой каталог parent (одна строка)

Вам нужно создать функцию:

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

и использовать его в запросе:

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

У меня есть хранимая процедура, которая перемещает node во вложенный набор к новому родительскому node. Я использую таблицу под названием "категория" в базе данных MySQL/InnoDB, называемой "somedb". Конечно, если пункт назначения является подкатегорией категории, которую вы хотите перенести, эта процедура будет винить, поэтому убедитесь, что вы не пытаетесь внедрить node внутри себя. Я оставлю это упражнение для читателя, чтобы сделать эту процедуру безопасной для этого случая.

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

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

Цель Node (новый родительский элемент Node, который вы перемещаете) - tNode. Левое значение Target Node - tNode.L, а правое значение - tNode.R. Аналогично перемещаемый Node - это mNode, а значения left и right для mNode - mNode.L и mNode.R. Два дополнительных столбца: mNode.SL и mNode.SR

Итак, у нас есть 4 столбца для манипуляции R, L, SL и SR

Step1

вычислить

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

Step2

Сохраните исходный код mNode L и R в столбцы SL и SR

- 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

Теперь mNode отсоединен от дерева, а дерево настроено без mNode.

Step4

вычислить

delta2 = (tNode.R - mNode.SL)

Step5

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

Теперь мы скорректировали Tree (и target node), чтобы принять количество удаленных узлов.

Step6

Прикрепить mNode в tNode и reset значения столбца SL/SR

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 ;

После всех этих шагов мы должны были перемещать mNode под tNode.

Ответ 9

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

   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;

Не проверено, вставлено, отрегулировано и упрощено из рабочей процедуры.

Ответ 10

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

 -- 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 - это массив, который представляет строку, которую я должен переместить; это должно быть так:

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

$row2 - это массив, который представляет судьбу 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"]);