Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > PHP: Для профи > Ищется самый оптимальный алгоритм по выводу дерева

Автор: webaliser 15.12.2007, 17:35

Цель вопроса: тайминги срабатывания кода или чем быстрее обрабатывается код - тем лучше!

Дано:
Если честно, речь идет о обработке $_SERVER['REQUEST_URI'] и mod_rewrite'е. Допустим поступает нам строка http://domain/pages/page_group/page_group2/page1 , соответственно, $_SERVER['REQUEST_URI'] видит /pages/page_group/page_group2/page1

Есть таблица Т в базе MySQL, в ней есть несколько полей:
- ИД (уникальный символьный ключ). В нашем случае: page1
- Парент (его предок). В нашем случае: group2
- Парентс (все предки). В нашем случае: pages/group1/group2
- Нэйм (Символическое название). В нашем случае (допустим): СТРАНИЦА1

ВОПРОС:
Нужен алгоритм (без примеров кода) как хранить или как обрабатывать данные с базы по запросу $_SERVER['REQUEST_URI'] чтобы получить вот такое:

Вход: http://domain/pages/group1/group2/page1
Выход:

Код


<a href="http://domain/">Главная</a>
-&gt;<a href="http://domain/pages">Страницы</a>
-&gt;<a href="http://domain/pages/group1">Группа1</a>
-&gt;<a href="http://domain/pages/group1/group2">Группа2</a>
-&gt;<a href="http://domain/pages/group1/group2/page1">СТРАНИЦА1</a>

или вот так: http://domain/->http://domain/pages->http://domain/pages/group1->http://domain/pages/group1/group2->http://domain/pages/group1/group2/page1

Допускаются любые модификации структуры базы и способов хранения данных в полях.

ВСЕМ УЧАСТВУЮЩИМ: Большое СПС!

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

Автор: WolfON 15.12.2007, 17:43

если прям текстом так и хранится пусть в бд, то для выбора группы почему-бы не сделать `group` LIKE 'group1/subgroup2/sasa/%' ?
хотя это и не очень эффективно

Автор: webaliser 15.12.2007, 17:53

Эффективность?! не знаю,

Я даже рассматривал вариант по генерированию кода непосредственно при создании элемента или изменения ключа ИД.?! Но это бред!

Автор: Vaulter 15.12.2007, 19:00

http://www.google.com/search?q=Nested+Tree&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:ru:official&client=firefox-a

Автор: Feldmarschall 15.12.2007, 19:16

Я тоже думаю, что лайком неэффективно.
Самое простое - это 4 рекурсивных запроса, получающих парент. Быстро и просто.

Точно такой же вопрос только что задавали в базах данных MySQL.

Автор: SelenIT 15.12.2007, 19:45

Цитата(Feldmarschall @ 15.12.2007, 19:16

)

Точно такой же вопрос только что задавали в базах данных MySQL.

Не точно такой же smile

. Там была неизвестная вложенность, тут известная. Поэтому для решения в один запрос вместо LEFT JOIN-а мы вправе воспользоваться INNER-ом и получить еще большую скорость:

Код


SELECT t0.id, t0.name, t1.id, t1.name, t2.id, t2.name, t3.id, t3.name
FROM T t0
INNER JOIN T t1 ON t1.id = t0.parent
INNER JOIN T t2 ON t2.id = t1.parent
INNER JOIN T t3 ON t3.id = t2.parent
WHERE t3.id = 'pages' AND t2.id = 'group1' AND t3.id = 'group2' AND t0.id = 'page1'

Тогда полный путь (parents) оказывается, по сути, избыточным и ненужным.

А Nested Sets, имхо, в данной конкретной задаче вряд ли даст существенное упрощение. Разве что если просто выбрать всех предков конечной страницы (это как раз в Nested Sets делается в один запрос элементарно), а уже в скрипте сравнить их состав и порядок с соответствующими элементами URI, и в случае несовпадения - редиректить на Error 404... Правда, нужно помнить, что в Nested Sets не получится легко поменять порядок вывода ветвей, и для любых модификаций дерева (добавление/удаление/перемещение) придется тем или иным образом шерстить всю таблицу...

Автор: webaliser 15.12.2007, 20:19

SelenIT, Жжешь, ща попробую... замерю и напишу smile

... а что значит известная или не известная вложенность?!

Мне может прийти запрос рода http://domain/t1/t2/t3/t4/t5/t6/t7/t8/t9 - не исключено... и мне нужно будет написать чтото вроде

Главная->Tab1->Tab2->Tab3->Tab4->Tab5->Tab6->Tab7->Tab8->Tab9

...вот так!

Автор: Feldmarschall 15.12.2007, 20:22

SelenIT, а оно надо?

Автор: webaliser 15.12.2007, 20:35

Комрады, а у мускула есть ф-ция типа как на ПХП substr ???

Автор: Feldmarschall 15.12.2007, 20:38

есть, а что?

Автор: SelenIT 15.12.2007, 20:39

Цитата(webaliser @ 15.12.2007, 20:35

)

ф-ция типа как на ПХП substr ???

Добавлено через 5 минут и 59 секунд

Цитата(webaliser @ 15.12.2007, 20:19

)

а что значит известная или не известная вложенность?!

В данном случае она всегда известная - сколько "каталогов" в URI, столько же "шагов" в "хлебных крошках". А может быть модель, когда такой однозначной зависимости нет, страница с любым URI теоретически может быть потомком кого угодно - вот там однозначно рулит Nested Sets smile

Автор: Feldmarschall 15.12.2007, 20:56

стоп.
у него же комбинированная таблица - материализованная смежность:

Цитата(webaliser @ 15.12.2007, 17:35

)

- Парентс (все предки). В нашем случае: pages/group1/group2

следовательно, даже джойны не нужны - строку на элементы разбиваша, запрос с or формироваша.

Автор: webaliser 15.12.2007, 22:23

Feldmarschall, типа где (парентс=pages/group1 энд ИД=group2) ор (парентс=pages энд ИД=group1) ор (парентс=null энд ИД=pages) ?!

Хороший вариант...