Дерево nested sets. Проверить существует ли ветка.

[stiff]

Дерево nested sets. Проверить существует ли ветка.

Имеется дерево, которое лежит в базе в виде nested sets. Дополнительно есть поля parent и level.
Допустим в дереве храниться структура каталогов. В узлах храниться название директории.

Задача. На входе мы получаем некий путь.
Каким образом быстрее всего проверить есть ли этот путь в базе. Если нет, то выяснить какая начальная часть заданного пути присутствует в базе.

 

[zerkms]

Дополнительно есть поля parent и level

level - это часть алгоритма NS
а parent - лишнее

Каким образом быстрее всего проверить есть ли этот путь в базе.

хранить избыточно в отдельном поле путь до узла

 

[stiff]

2zerkms, а без хранения избыточной информации?

Что будет правильнее
* получить все дерево и в цикле его обежать
* делать множество запросов на получение потомков узла
?

 

[zerkms]

stiff
у тебя и так уже хранится избыточная инфа в виде parent которую ты не юзаешь (скорее всего), или которую юзаешь вместо того чтобы пользоваться нативными средствами NS

каждый из этих двух вариантов имеет свои плюсы и приемлем в конкретной ситуации

1. если объём дерева небольшой
2. -- // -- большой

но хранение пути предпочтительнее

 

[Alexos]

Не надо никакой путь хранить.
stiff
Смотри. Ты имеешь на входе некий путь. Достаешь из него айди самого младшего детеныша, делаешь ВСЕГО ОДИН запрос к базе для определения правильного пути к этому детенышу. Затем сравниваешь два пути. Все.

 

[stiff]

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

2zerkms, юзаю. может неправильно, но мне кажется так экономится один запрос к БД (я получаю доступ к полю по id).
темболее оно уже храниться, а полный путь нужно делать. + путь это не int (или не один int), в отличие от parent.

Пока сделал цикл. Объем небольшой. (это разделы сайта)

 

[Alexos]

stiff

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

И какие проблемы? У тебя ж есть ещё в базе уровень. Не мудри - всё очень просто! И не мешай в кучу все алгоритмы. Парент_айди тебе тут совсем не нужен.

 

[zerkms]

Alexos

Ты имеешь на входе некий путь. Достаешь из него айди самого младшего детеныша

т.е. ты предлагаешь выбирать все узлы у которых одинаковый левел и одинаковое имя?
а если их много?
да и придётся их в итоге в пхп собирать

 

[Alexos]

т.е. ты предлагаешь выбирать все узлы у которых одинаковый левел и одинаковое имя?
а если их много?
да и придётся их в итоге в пхп собирать

Хорошо бы иметь в пути ещё и айдишники А вообще задача довольно странная. Если бы stiff объяснил подробнее нафига ему это нужно, я думаю, мы бы нашли разумное решение.

 

[zerkms]

Alexos
задача вполне обычная. есть путь, есть дерево. нужно по пути найти элемент.

 

[stiff]

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

* путь полностью совпадает
* совпадает только часть вначале пути
* путь не совпадает не с одной веткой

Alexos у меня в дереве лежит дерево сайта для реализации красивых ссылок при помощи Rewrite.

Автор оригинала: zerkms
т.е. ты предлагаешь выбирать все узлы у которых одинаковый левел и одинаковое имя?
а если их много?
да и придётся их в итоге в пхп собирать

Впринципе это будет быстрее, чем парсить все дерево... имхо

 

[ПРЕВЕД]

Можно делать self-join на каждый уровень.
Например, для пути /foo/bar/hello/world будет так:
[sql]
SELECT * FROM sitetree tree0 /* root */
LEFT JOIN sitetree tree1 ON (tree1.parent_id = tree0.id AND tree1.name = "foo")
LEFT JOIN sitetree tree2 ON (tree2.parent_id = tree1.id AND tree2.name = "bar")
LEFT JOIN sitetree tree3 ON (tree3.parent_id = tree2.id AND tree3.name = "hello")
LEFT JOIN sitetree tree4 ON (tree4.parent_id = tree3.id AND tree4.name = "world")
WHERE tree0.parent_id = 0
[/sql]

 

[regi]

В цикле проверять, есть ли такой путь в базе, если нет, отрезать от него все после последнего слеша и опять проверять =)