移动嵌套集树中的节点

Question

我正在和mySQL一起处理邻接表，但我不能(至少是我自己)进行足够好的查询，以便能够移动一组节点(以及最终的子节点)。

该表包含以下列：

 id     name     left     right

非常感谢!

Answer 1

我很确定该表使用的是嵌套集合设计，而不是邻接表。如果它使用邻接列表，则其列应该类似于parent_id，而不是left和right。

移动节点是嵌套集合中的皇家皮塔。您必须对移动的每个节点的所有left和right值进行重新编号。

如果移动子树，最简单的方法是一次删除一个节点，在每次删除节点后对left和right字段重新编号。然后，一旦删除了整个子树(并以某种方式在应用程序中保留了子树的结构)，请在树中的目标位置重新插入子树，并对每次插入的left和right字段进行重新编号。

更新:我最近写了一篇关于如何在不同的分层数据设计中移动子树的博客，我更喜欢这种设计而不是嵌套集。我称这个设计为闭包表格。

请参阅http://www.mysqlperformanceblog.com/2011/02/14/moving-subtrees-in-closure-table/

Answer 2

这里有一个解决方案，允许您仅使用一个输入参数将节点移动到树中的任何位置-节点的新左侧位置(newpos)。

从根本上讲，有三个集合：

• 为子树创建新空间。
• 将子树移入此空间。
• 删除子树腾出的旧空间。

在psuedo-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

如果您喜欢这个解决方案，请向上投票。

Answer 3

使用嵌套集合模型(具有左列和右列)在类别树中移动子树的步骤是: 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));