Как я могу обновить древовидную структуру вложенных множеств? - PullRequest
Новая
       9

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

2 голосов
/ 11 апреля 2009

Я смотрел на Управление иерархическими данными в MySQL , но на самом деле он касается только добавления и удаления узлов в модели вложенного набора.

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

Как бы я это сделал?

Ответы [ 4 ]

1 голос
/ 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

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

1 голос
/ 11 апреля 2009

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

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

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

Конструкция Path Enumeration также позволяет легко перемещать узел и его дочерние элементы: 

UPDATE TreeTable
SET path = REPLACE(path, 'A/B/C/', 'A/D/F/') -- MySQL function
WHERE path LIKE 'A/B/C/%';
1 голос
/ 11 апреля 2009

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

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

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

Если вы переместили букву «А» с потомками между «D» и «E», то все справа от «А», но слева от «Е», нужно уменьшить его левый / правый индексы на 6 ( размер «А» с потомками): 

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

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

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

0 голосов
/ 11 апреля 2009

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

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

...