在嵌套集中移动节点

Question

我需要一个MySQL查询,它将一个节点及其所有子节点移动到一个嵌套集中.我发现这个网站,但该功能似乎只是如此不合逻辑-没有universeid或treeid嵌套集模型,代码本身只是感觉比什么需要更长的时间.我在表中唯一的额外列是parent.

我不能再删除并添加节点,因为它将丢失其ID.

Answer 1

我知道,这个话题已经很老了,但无论如何它仍然没有答案.我从谷歌来到这里,并没有找到这个问题的直接答案.

因此,经过一番研究后,我发现了很容易的解决方案.

一切,我们需要移动节点的是:节点左右位置,新父节点右位置.然后可以通过四个简单的步骤移动到新位置的节点:

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

如果你喜欢这个解决方案,请投票.