Меню
Что нового?

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

  • Автор темы Автор темы stiff
  • Дата начала Дата начала

stiff

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

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

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

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

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

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

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

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

Пока сделал цикл. Объем небольшой. (это разделы сайта)
 
stiff
2Alexos, если полного пути нет, то необходимо выяснить какая начальная часть заданного пути присутствует в базе.
Нажмите для раскрытия...
И какие проблемы? У тебя ж есть ещё в базе уровень. Не мудри - всё очень просто! И не мешай в кучу все алгоритмы. Парент_айди тебе тут совсем не нужен.
 
Alexos
Ты имеешь на входе некий путь. Достаешь из него айди самого младшего детеныша
Нажмите для раскрытия...
т.е. ты предлагаешь выбирать все узлы у которых одинаковый левел и одинаковое имя?
а если их много?
да и придётся их в итоге в пхп собирать
 
т.е. ты предлагаешь выбирать все узлы у которых одинаковый левел и одинаковое имя?
а если их много?
да и придётся их в итоге в пхп собирать
Нажмите для раскрытия...
Хорошо бы иметь в пути ещё и айдишники ;) А вообще задача довольно странная. Если бы stiff объяснил подробнее нафига ему это нужно, я думаю, мы бы нашли разумное решение.
 
Alexos
задача вполне обычная. есть путь, есть дерево. нужно по пути найти элемент.
 
Проблема в том, что путь, приходящий на вход может не полностью соответствовать какой-то ветке в дереве. Тоесть варианты

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

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]
 
В цикле проверять, есть ли такой путь в базе, если нет, отрезать от него все после последнего слеша и опять проверять =)
 
Войдите или зарегистрируйтесь для ответа.
Сверху