Строим дерево (флейм)

Итак.

Условия: есть 1000 категорий в виде дерева, уровни вложения не ограничены. Хранится в базе, стуктура стандартная id, name, id_parent. Связанные списки и тд не трогаем, так как структуру менять нельзя, и иначе все рухнет.

Необходимо:

- получить полное дерево для селекта поиска;

- путь до текущей категории;

- раскрытое меню до текущей категории;

- доступ к названию любой категории;

Ваши предложения. Поехали ))

А какие тут могут быть предложения? Stored procedures - это наше всё.

Ну, формулируя задачу "как в учебнике" Вы рискуете нарваться на копипаст ответа из учебника, а это неспортивно :)

Так что я кое-что уточню, а Вы поправьте. Во-первых, ограничим вложенность 5 уровнями (больше редко бывает, по крайней мере на 1000 категорий). Во-вторых, предположим относительно равномерное распределение подкатегорий.

Так вроде структура, которую Вы описали - и есть связанные списки (списки смежности, Adjacency List).

Полное дерево получается запросом "SELECT * FROM tree", и далее какой-то такой ахтунг. Про "селект поиска" не понял.

Выбираем текущую запись, добавляем в массив. Если родитель - не корень, выбираем родителя, добавляем в массив. Если не корень... и т.д.

Как Вы думаете, что эффективней: 5 запросов по primary key, или 5 джойнов таблицы на саму себя? А что доступней для понимания?

Получаем путь, далее идем по уровням, начиная с корня, если узел есть в пути - уходим в рекурсию. Соответственно, еще 5 очень легких запросов.

Не понял. SELECT name FROM tree WHERE id = 22?

Критикуйте :) Вариант с 1.500.000 записей не предлагать. Сами сказали, что их тыща :)

Про "индусский стиль" ничего не хочу слышать.

А у нас mysql4 :(

Если дерево категорий редко обновляется, то долбим селектами с последующим кешированием результата, при первом запросе ветки. Потом всё берём из кеша. :)

При редактировании категории кеш убивается и формируется заново.

При переносе веток - высчитываем все ветки, которые затронет данное изменение и убиваим их кеш.

В дереве одна из распространенных задач "искать в ветке" (искать в категории и подкатегориях) или например сосчитать рекурсивно количество элементов (которые могут часто меняться, так что кешированием здесь не спастись) в ветке, при таком типе хранения как предложите это делать ?

своего варианта решения не предлагаю, просто не могу сказать что в деревьях что-то понимаю

1. Задача не из учебника, а реальная. Проект http://www.tkat.ru

2. Связанные списки, я не математик, поэтому понимаю, что в этом случае каждая категория знает соседа и тд. Без доп выборок. Ну это оффтоп в нашем вопросе.

3. Селект - это я к тому, зачем на странице полное дерево. Например, искать в категории. А то скажут, что не нужно.

4. По большому счету и по моему мнению уровень вложенности не должен играть какую либо важную роль.

5. То что Вы описали очень реально для небольшой нагрузки, а у нас она за 100К в сутки + ботов еще почти столько же. Столкнулся с тем, что в списке процессов все эти рекурсивные запросы висели десятками минут, и шли они нарастающим итогом. Серваку было очень нехорошо, да и хостер волновался.

6. Практика показала, что доставание категорий запросом select * from category и последующий разбор пхпой, с возможным кэшированием на диске/в памяти построенного дерева, эффективней рекурсивных запросов примерно в 1000 раз - только по замеру времени, а про зависшие эти запросы в процессах под реальной нагрузкой я уже забыл. 🚬

timur-kar, для таких вещей как раз придумали Nested Sets. На такой структуре, очевидно, придется найти все айдишники подветвей и делать WHERE parent_id IN (1, 2, 3...). Подветви выбираем либо по схеме "раскрытое меню до текущей категории", либо последовательностью запросов с WHERE parent_id IN (...) по числу уровней. Но это действительно тяжелая штука. Я в итоге все-таки добавил nested sets специально под это.

да, штука тяжелая, но работает. У меня есть мысли, что по уму то надо бы у категории хранить инфу о подкатегориях, то есть использовать некую таблицу связок. Возможно это будет быстрее, чем IN (500 категорий), не проверял, хотя тут по индексам нормально.

Да, забыл что еще необходимо: в любой момент каждая категория должна знать своих потомков. Всех.

А про доступ к каждой категории. Предположим есть список статей с категоризацией. Если мы уже построили дерево для поиска в категориях, неужели мы будет опять выбирать названия категории, к которой относится каждая статья?

Я правильно понимаю что у вас nested sets "поверх" первоначальной структуры ? т.е. дополнительные поля в БД, которые не определяют иерархию а просто копируют её в этом виде

AndreM, а, вот тут-то мы и добрались до самого интересного, бишь до кеширования. Тогда внимание вопрос: если мы кэшируем дерево целиком, нам не пофигу, как его выбирать? Хоть тыщей запросов :) И еще вопрос: а зачем кэшировать промежуточно-абстрактное "дерево целиком", если можно закешировать результаты?

Насчет зависающих процессов - это надо смотреть на Вашу конкретную систему. Убейте, не пойму, где должен повиснуть запрос, достающий 1 запись по primary :)

ОК, а как Вы решаете задачу поиска в категории?

timur-kar, да, именно так. Ну, с небольшими хитростями.