Перемещение узлов в Nested Sets

Avenus

Under Glory Yield
Перемещение узлов в Nested Sets

Привет, всем! :)

Перерыл весь форум на эту тему, искал в Интернете.
Самой понятной была статья:
http://www.getinfo.ru/article610.html
Все разобрал: принципы, построение, добавление, удаление...

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

Эти моменты ясны:
1. Ключи и уровень перемещаемого узла.
2. Уровень нового родительского узла.

А этот, нет:
3. Правый ключ узла за который мы вставляем узел (ветку).
Т.е. необходимо получить ключ $right_key_near, но из этого описания не разберешь ничего:

Данная переменная (я, так понимаю, $right_key_near) берется в зависимости от действия:
- При простом перемещении в другой узел;
PHP:
SELECT (right_key – 1) AS right_key FROM my_tree WHERE id = [id нового родительского узла]
Что за простое перемещение? С ветками или нет?

- При изменении порядка, когда родительский узел не меняется – правый ключ узла за которым будет стоять перемещаемый;
PHP:
SELECT left_key, right_key FROM my_tree WHERE id = [id соседнего узла с который будет(!) выше (левее)]****
**** Следует обратить внимание, что при поднятии узла вверх по порядку, узел выбирается не соседний,
а следующий, за неимением оного (перемещаемый узел будет первым) берется левый ключ родительского
узла
И какой нужно выбрать ключ: left_key или right_key?

- При переносе узла в корень дерева – максимальный правый ключ ветки;
PHP:
SELECT MAX(right_key) FROM my_tree
Этот запрос, в принципе, не нужен, если в дереве корень всегда постоянен?

- При поднятии узла на уровень выше – правый ключ старого родительского узла
PHP:
SELECT right_key FROM my_tree WHERE level = $level
Этот запрос вообще вернет много строк, какая нужная?
К тому же, при поднятии узла на уровень выше, а как же быть с тем, если нужно на уровень ниже?
И чем отличается это от перемещения в другой узел?

Спасибо всем, кто поможет понять ;)
 

Avenus

Under Glory Yield
fixxxer, конечно :)
Описания всего там много, но именно по перемещению узлов я не нашел информации.
Конечно, можно взять готовые функции из библиотек, что и придется сделать.
Но, я хотел именно понять.
 

whirlwind

TDD infected, paranoid
Avenus Попробуй тут покопаться http://code.google.com/p/prolibrary/source/browse/trunk/NS/classes/NS/DataHelper.php#131

а вот тут каменты есть http://code.google.com/p/prolibrary/source/browse/trunk/NS/classes/NS/DataMapper.php

-~{}~ 27.12.09 18:27:


PS. Если вкратце, то все перемещения по дереву выполняются сдвигом влево или вправо. Важно найти целевую позицию, которая определяется двумя ключами ближайшим левым и ближайшим правым. Эти ключи могут принадлежать одному и тому же или разным узлам. Например, если перемещение на узел ниже, значит надо взять ключи будущей родительской ноды. При вставке между узлами на одном уровне, берутся ключи правый у левого узла и левый у правого. А например при вставке первого на уровень, берутся левый ключ родителя как near left и левый родителя + 1 (те левый первого узла на уровне) как near right. И т.п. комбинации могут быть разные. По этим ключам вычисляется диапазон для изменяемых узлов. Так как узлы смежные, это всегда непрерывная последовательность, что и позволяет обработать ее одним запросом. Но там есть тонкости, что в зависимости от целевой позиции, не все ключи одних узлов надо изменять. Например, при сдвиге влево не надо менять левые ключи узлов которые меньше левого целевого. В общем без рисования схемы на словах врядли можно доходчиво объяснить. Так что ручку тетрадку и вперед. Картинку можно взять из статьи.

PPS. Сам путаюсь. ппц мутная тема :)
 

Avenus

Under Glory Yield
Т.е. то, что написано здесь - бред (по поводу перемещения узлов)?
http://www.getinfo.ru/article610.html

Я управляю деревом с помощью ajax.
Добавление и удаление работает отлично.
Полностью сделал по схеме (на которую дал ссылку).

При перемещении узла серверу передается 4 значения:
ID перемещаемого узла
PID принимающего узла
LEVEL - новый уровень для перемещаемого узла
SUB - переносится ли узел в другой = true или перемещается только внутри родителя = false

Вот, теперь застопорился, потому как в этой статье непонятно, каким образом получить $right_key_near, исходя из моих данных :)

Да, еще:
+ Перемещаемый узел у меня всегда левее принимающего PID.
+ У меня в корень узел не может переместиться. Т.е. узел с ID=1 всегда постоянен и положение его не изменяется.

Сам путаюсь. ппц мутная тема
Вот-вот... я уже 2-й день парюсь
 

whirlwind

TDD infected, paranoid
Корень да, корень нельзя переместить, он же как бы замыкает множество.

Насчет остального я ниче не понял зачем ты это рассказываешь. Чего я непонятно объяснил? Берешь ноду которую перемещаешь - ключи известны? известны. Берешь целевую позицию левый и правый ключ между которыми будешь вставлять перемещаемую ноду. Дальше примерно так: left перемещаемой - target right (near right) получиль дельту, на которую надо уменьшить ключи перемещаемой ноды. А все ключи между near right и moving left увеличиваешь на количество перемещаемых узлов. Колво узлов дочерней ноды (right - left) / 2 тоже объяснять?

У тебя узел принимает только в случае если ты родителю добавляешь первую дочернюю ноду. В остальных случаях у тебя 2 ноды и два ключа от разных соседних нод. Переведи айдишки в ключи и работай с ключами. А про ноды забудь ваще пока не поймешь что у тебя косяк с левыми ключами при сдвиге влево и с правыми при сдвиге вправо. Правый ключ определяется частным образом. Смотри примеры кода которые я давал выше там все по-русски. Рисуй на бумаге дерево до и после перемещения.
 

Avenus

Under Glory Yield
whirlwind, буду пытаться, спасибо :)

-~{}~ 27.12.09 21:21:

Рисовал, рисовал и нашел решение.
Получается, что в статье ошибочка есть.
...если $right_key_near больше, то узел перемещается в облась вышестоящих узлов, иначе - нижестоящих...
И еще с изменением уровня не так что-то.
В общем, на моем примере:
PHP:
$right_key_near = SELECT right_key FROM tree WHERE id=PID
$skew_level=$level_up - $level + (SUB?1:0)
Теперь перемещение узлов работает правильно, но только в пределах уровня и при увеличении уровня.
Зато при перемещении наверх косяки, результат непредсказуемый...
В общем, дальше нужно думать.
 

Sad Spirit

мизантроп (Старожил PHPClub)
Команда форума
На самом деле, перемещение узла раскладывается на два этапа:
а) Удаление узла на старом месте;
бэ) Добавление узла на новом месте.

Для каждого из этапов UPDATE'ы пишутся достаточно просто. Остаётся только их объединить правильно.

Если же пытаться написать сразу, то запутываешься мгновенно, по себе помню.
 

Avenus

Under Glory Yield
Взял готовый класс "Joe Celko Nested Sets"
http://www.phpclasses.org/browse/file/5191.html
...
Попробую его доработать под себя, т.к. он не позволяет перемещать узлы внутри родителя без изменения родительского узла.

-~{}~ 28.12.09 14:16:

Sad Spirit, спасибо! :)
Я тоже думал, что не пойдет сразу обновлять узлы.
И в классе по ссылке сделано также: удаляется ветка и потом вставляется в другой узел.

-~{}~ 15.01.10 05:51:

Все сделал, ошибок не было.
Но, иногда все-таки слетает структура почему-то и всё, нужно восстанавливать.
...
Я в одной таблице храню структуру, а в отдельной таблице id страниц и всего прочего.
Не рушатся id родителей и уровень.
А левые и правые ключи нереально подправить, только вручную сделал.

Подскажите, есть для Nested Sets какой-нибудь способ восстановить автоматически структуру?
 

dimagolov

Новичок
Avenus, видимо Rin имел в виду, что в том классе нету ошибок, из-за которых нужно что-либо восстанавливать ;)
 

Avenus

Under Glory Yield
Ошибок нет и в классе, на который я ссылку дал.
При тестировании проблем не возникает, какие угодно производятся действия с деревом.

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

В классе TreeNS ничего особенного нет по сравнению с классом Joe Celko (кстати, он кажется, придумал такой метод). Разве, что в Dklab добавили проверку целостности дерева.

Только, как я посмотрел, эта проверка ни на что не влияет - просто проверяет и возвращает 1 или 0. Если бы откат хотя бы был. Т.е. их класс получается, тоже подразумевает, что могут быть сбои... разве что быстро это можно определить :)
 

Rin

*
dimagolov
верно


Avenus
Кроме проверки целостности дерева TreeNS умеет ещё изменять позицию узлов, вставлять несколько узлов за один вызов и добавлять оси XPath относительно заданного узла
 

Sad Spirit

мизантроп (Старожил PHPClub)
Команда форума
Автор оригинала: Avenus
По оценке что получилось, делаю вывод, что проблема с транзакциями.
Мыши плакали, кололись, но продолжали кушать MyISAM?..
 

Avenus

Under Glory Yield
Sad Spirit, спасибо :)
Только сейчас понял, что не тот тип таблицы использую.
 
Сверху