Я работаю над списком смежности с mySQL и не могу (по крайней мере, сам по себе) сделать мышление, необходимое для того, чтобы сделать достаточно приличный запрос, чтобы иметь возможность перемещать набор узлов (вместе с возможными дочерними элементами узлов).Переместить узел в дереве вложенных множеств
таблица имеет следующие столбцы:
id name left right
Спасибо большое!
Я уверен, что таблица использует Вложенные наборы дизайн, а не список смежности. Если бы он использовал Adjacency List, у него был бы столбец, например parent_id, а не left и right.
Перемещение узлов является королевским PITA в вложенных наборах. Вы должны перенумеровать все значения left и right для каждого перемещаемого узла.
Если вы перемещаете поддерево, самый простой способ сделать это - удалить узлы по одному, перенумеровывая поляи right после каждого удаления узла. Затем, как только вы удалили все поддерево (и каким-то образом сохранили структуру поддерева в своем приложении), повторно вставьте поддерево в его место назначения в дереве, снова переименовав поля left и right для каждой вставки.
обновление: Я недавно написал блог о том, как двигаться поддерева в других иерархических данных, который мне нравится лучше, чем вложенные наборы. Я называю этот дизайн Закрытие Таблица.
См http://www.mysqlperformanceblog.com/2011/02/14/moving-subtrees-in-closure-table/
шагов, чтобы переместить поддерево вокруг в категории дереве с использованием вложенного набора модели (с левым и правым колонком) являются: 1. преобразования ЯПТА и 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));
Вот решение, которое позволяет переместить узел в любую позицию в дереве только с одним входным параметром - новой левой позицией (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
*/
The: переменное расстояние расстояние между новыми и старыми позициями,: ширина размера поддерева, а также: 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
Если вам нравится это решение, пожалуйста, вверх-голосования.
Ваш пример действительно помог мне понять алгоритм, но каждый раз, когда вы кладете все тело метода в блок try, Бог убивает котенка, которого вы знаете :) – asavartsov
Ive получил более простой и удобный для чтения sql, он отлично работает для меня. Это сделано для типичного вложенного набора структуры с идентификатором, РТГ, МВТ, уровень (работает без уровня тоже):
#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 = [email protected]_size WHERE rgt > @dir_rgt;
UPDATE files SET lft = [email protected]_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 = [email protected]_size WHERE rgt >= @target_lft;
UPDATE files SET lft = [email protected]_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 часов поиска и тестирования так много решений, наконец, тот, который соответствует моим потребностям. –
Вау, '= гг G' ... – mattalxndr