Как обновить структуру дерева вложенных множеств?

Question

Я посмотрел на Managing Hierarchical Data in MySQL, но на самом деле он имеет дело только с добавлением и удалением узлов в модели вложенного набора.

Мне нужно уметь Переместить Узлы с и без дочерних узлов.

Как мне это сделать?

Answer 1

Учтите, что перемещение узла эквивалентно удалению узла и всех его дочерних элементов, если они есть, и вставить узел и его дочерние элементы, если они есть, в новую позицию.

Теперь перечитайте техническую статью, в которой будет отображаться вся таблица, после того, как вы удалите ее, а затем добавьте обновление, которое сделает то же самое.

Answer 2

Дизайн вложенных наборов не является хорошим выбором для такого изменения дерева. Очень сложно пересчитать числа справа/слева при перемещении узлов вокруг.

Список смежности это самый простой дизайн дерева для движущихся поддеревьев:

UPDATE TreeTable 
SET parent = $newparent 
WHERE id = 123; 

Путь Перечень конструкция также позволяет легко переместить узел и его дети:

UPDATE TreeTable 
SET path = REPLACE(path, 'A/B/C/', 'A/D/F/') -- MySQL function 
WHERE path LIKE 'A/B/C/%'; 

Answer 3

Перемещение с дочерними узлами:

В классических вложенных наборах whe re «left» и «right» values ​​находятся в смежном блоке с 0..n * 2 значениями, будет ряд строк, которые перемещают либо «x» места влево, либо «x» вправо справа когда поддерево перемещается, где «x» - количество перемещаемых левых/правых значений. например.

A: 1,6 
    B: 2,3 
    C: 4,5 
D: 7,8 
E: 9,10 

Если вы переехали «A» с потомками до между «D» и «Е», все справа от «A», но левее «Е» должен иметь свои влево/вправо индексов снижается на 6 (размер «A» с потомками):

UPDATE things 
SET nsl=nsl+(
    IF nsl BETWEEN 1 AND 6 THEN 6 -- A-C go forward 6 
    ELSE -6      -- D goes back 6 
), nsr=nsr+(      -- same again 
    IF nsl BETWEEN 1 AND 6 THEN 6 
    ELSE -6 
) 
WHERE 
    nsl BETWEEN 1 AND 6   -- select A-C 
    OR nsl BETWEEN 7 AND 8   -- select D 

Перемещение без дочерних узлов является более сложным. Содержащиеся узлы должны вернуться назад, узлы после удалённого узла должны вернуться назад, а затем узлы после новой точки вставки должны идти вперед, чтобы освободить место.

Пока вы можете сделать это в том же стиле, как и выше, начинает становиться очень запутанными, и вы хотели бы рассмотреть альтернативные подходы, такие как перезапись всех/вправо значений левых вручную или с помощью другого типа схемы что упрощает эти виды операций, например, отношение полного смещения предков и потомков.

Answer 4

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

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