Переместить узел в дереве вложенных множеств - PullRequest
Новая
       69

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

4 голосов
/ 10 мая 2010

Я работаю над списком смежности с mySQL и не могу (по крайней мере, сам) подумать, чтобы сделать достаточно приличный запрос, чтобы иметь возможность перемещать набор узлов (вместе с возможными дочерними узлами) вокруг. *

В таблице есть следующие столбцы: 

 id     name     left     right

Большое спасибо!

Ответы [ 4 ]

9 голосов
/ 08 января 2012

Вот решение, которое позволяет вам переместить узел в любую позицию дерева с помощью всего лишь одного входного параметра - новой левой позиции (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;
}

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

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

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

4 голосов
/ 29 декабря 2010

Шаги для перемещения поддерева в дереве категорий с использованием модели вложенного набора (с левым и правым столбцами): 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 голосов
/ 11 мая 2010

Я почти уверен, что таблица использует дизайн Nested Sets , а не список смежности. Если бы он использовал Список смежности, он имел бы столбец, подобный parent_id вместо left и right.

Перемещение узлов - это королевская PITA во вложенных наборах. Вы должны перенумеровать все значения left и right для каждого перемещаемого узла.

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

обновление: я недавно написал блог о том, как перемещать поддеревья в другом иерархическом дизайне данных, который мне нравится больше, чем во вложенных наборах. Я называю этот дизайн Закрытие стола .
Смотри http://www.mysqlperformanceblog.com/2011/02/14/moving-subtrees-in-closure-table/

3 голосов
/ 27 февраля 2015

Мне стало проще и легче читать sql, он отлично работает для меня. Это сделано для типичной структуры вложенных множеств с id, rgt, lft, 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...
...