logo标签列表

移动嵌套集树中的节点

mysqltreenestedhierarchical-datanested-sets
4

我正在使用MySQL处理邻接列表，但是我自己无法思考出足够好的查询来移动一组节点（以及可能存在的子节点）。

该表格具有以下列：

 id     name     left     right

非常感谢！

5个回答
8

以下是一种解决方案，它可以让您通过一个输入参数 - 节点的新左位置（newpos）将节点移动到树中的任何位置。

基本上有三个步骤：

  • 为子树创建新的空间。
  • 将子树移动到这个空间。
  • 删除子树腾出的旧空间。

在伪 SQL 中，它看起来像这样：

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

:distance 变量是新位置和旧位置之间的距离，:width 是子树的大小，:tmppos 用于在更新期间跟踪正在移动的子树。这些变量被定义为：

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

完整的代码示例请参见我的博客：

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

如果您喜欢这个解决方案，请点赞。

你的例子真的帮助我理解了算法，但是每次你把所有方法体都放到 try 块中，上帝就会杀一只小猫，你知道的 :) - asavartsov
4
使用嵌套集模型（具有左右列）在类别树中移动子树的步骤如下： 1.将所需移动的类别及其子类别的lft和rgt列转换为它们的负数形式（这将“暂时”从树中删除子树） 2.如果您向上移动子树（或在嵌套集表示中向“左”移动），请将新父级和旧左限制之间的所有类别都向右移动，否则（当向下移动子树时）向右移动。这需要将这些类别的左右列设置为它们的值加上（或减去，在第二种情况下）子树（或要移动的类别）的左右列之间的距离。 3.之后，您只需将左右列还原为正值，并同时减去（或添加，在第二种情况下）其左限制与新父级左列之间的差异（或在第二种情况下，父级左侧和右限制之间的差异）。
这一切看起来很复杂，因此我将其分解为两种情况。
$step = 1+ $this->_categoriesTable->rgt
                - $this->_categoriesTable->lft;
$lft = $this->_categoriesTable->lft;
$rgt = $this->_categoriesTable->rgt;
$id = $this->_categoriesTable->id;
$distance = $lft - $parentLeft - 1;
                $query = '
                    UPDATE %s SET lft=-lft, rgt=-rgt
                        WHERE lft>=%d AND lft<=%d;
                    UPDATE %s SET lft=lft+%d WHERE lft>%d AND lft<%d;
                    UPDATE %s SET rgt=rgt+%d WHERE rgt>%d AND rgt<%d;
                    UPDATE %s SET lft=-lft-%d, rgt=-rgt-%d WHERE lft<=-%d
                        AND lft>=-%d;
                    UPDATE %s SET parent_id=%d, title=%s, description=%s,
                        metadescription=%s WHERE id=%s';

                $query = sprintf($query,
                    $this->_db->nameQuote('#__categories'),
                        $lft, $rgt,
                    $this->_db->nameQuote('#__categories'), $step,
                        $parentLeft, $lft,
                    $this->_db->nameQuote('#__categories'), $step,
                        $parentLeft, $lft,
                    $this->_db->nameQuote('#__categories'), $distance,
                        $distance, $lft, $rgt,
                    $this->_db->nameQuote('#__categories'),
                        $data['parent_id'], 
                        $this->_db->Quote($this->_categoriesTable->title),
                        $this->_db->Quote($this->_categoriesTable->description),
                        $this->_db->Quote(
                            $this->_categoriesTable->metadescription),
                        $this->_db->Quote($id));

// and for the moving to the "right" case
$step = 1+ $this->_categoriesTable->rgt
                - $this->_categoriesTable->lft;
$distance = $parentLeft - $this->_categoriesTable->rgt;

// Memorize this because we bind and we need the old values
$lft = $this->_categoriesTable->lft;
$rgt = $this->_categoriesTable->rgt;
$id = $this->_categoriesTable->id;

$query = sprintf($query,
                    $this->_db->nameQuote('#__categories'),
                        $lft, $rgt,
                    $this->_db->nameQuote('#__categories'), $step,
                        $rgt, $parentLeft,
                    $this->_db->nameQuote('#__categories'), $step,
                        $rgt, $parentLeft,
                    $this->_db->nameQuote('#__categories'), $distance,
                        $distance, $lft, $rgt,
                    $this->_db->nameQuote('#__categories'),
                        $data['parent_id'],
                        $this->_db->Quote($this->_categoriesTable->title),
                        $this->_db->Quote($this->_categoriesTable->description),
                        $this->_db->Quote(
                            $this->_categoriesTable->metadescription),
                        $this->_db->Quote($id));
4
我很确定这个表格使用的是嵌套集设计，而不是相邻列表。如果它使用相邻列表，它将有一个像parent_id这样的列，而不是left和right。
在嵌套集中移动节点非常麻烦。您必须重新编号每个移动的节点的左右值。
如果移动子树，最简单的方法是逐个删除节点，每次节点删除后重新编号左右字段。然后，一旦您删除了整个子树（并在应用程序中以某种方式保留了子树的结构），请重新插入子树到树中的目标位置，再次按插入重新编号左右字段。

更新：我最近写了一篇关于如何在不同的分层数据设计中移动子树的博客，这个设计比嵌套集更好。我将这个设计称为闭包表。
请参见http://www.mysqlperformanceblog.com/2011/02/14/moving-subtrees-in-closure-table/

3

我有一个更简单易读的 SQL 查询语句，对于典型的嵌套集结构表格，包含 id、rgt、lft 和 level 字段（没有 level 也可以使用），它效果非常好：

#Set IDs
SET @dirId := :dirId; #folder (subtree) you wanna move
SET @targetId := :folderId; #target

#get datas
SELECT rgt, lft, rgt-lft+1, level INTO @dir_rgt, @dir_lft, @dir_size, @dir_level FROM files WHERE id = @dirId;

#put the moving tree aside (lft and rgt columns must allow negative int)
UPDATE files SET lft = 0-lft, rgt = 0-rgt WHERE lft BETWEEN @dir_lft AND @dir_rgt;

#fill the empty space        
UPDATE files SET rgt = rgt-@dir_size WHERE rgt > @dir_rgt;
UPDATE files SET lft = lft-@dir_size WHERE lft > @dir_rgt;

#get datas of the target-folder      
SELECT lft, level INTO @target_lft, @target_level FROM files WHERE id = @targetId;

#create space in the target-folder        
UPDATE files SET rgt = rgt+@dir_size WHERE rgt >= @target_lft;
UPDATE files SET lft = lft+@dir_size WHERE lft > @target_lft;

#edit all nodes in the moving-tree
UPDATE files SET
   lft     = 0 - lft - (@dir_lft - @target_lft - 1), #this formula fits for all moving directions
   rgt     = 0 - rgt - (@dir_lft - @target_lft - 1), 
   level   = level - (@dir_level - @target_level) + 1

WHERE 
   lft < 0; #that could be more precise...
非常感谢。经过6个小时的搜索和测试许多解决方案，终于找到了适合我的需求的一个。 - Kunal Dethe
0

从数学角度来看，您可以使用单个UPDATE语句完成所有操作。对于任何移动操作，当您知道节点的LEFT和RIGHT以及要将其插入的位置时，可以一次重新计算树中所有LEFT和RIGHT。您只需要确保新位置不在移动节点本身内，这可以通过简单的WHERE子句完成：

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

请查看https://sedna-soft.de/articles/nested-sets-move-subtree/

你的回答可以通过提供更多支持信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的答案是正确的。您可以在帮助中心找到有关如何编写良好答案的更多信息。 - Community
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接