miksoft,

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

Попробую для начал сделать так:
Тестовая машина - обычный комп с 2.5Ггц, древним Athlon-32, и 2 гектарами оперативки. LAMP-server.
Тестовые деревья: 500 деревьев с 3 ветками в каждом узле, глубина вложения узлов = 5 (всего 182000 записей) 100%заполнение узлов. В каждом дереве 363 потомка. Время парсинга мускулем запросов и прочие накладные расходы - в районе 50мсек. Включено в результаты тестирований (не вычиталось!)

1. Способы представления деревьев в реляционных БД и конкретно, применяемых на практике:

а) поле ссылки на родительский элемент в той же таблице (parent_id):
Достоинства:
- Наиболее компактный способ - расходы только дополнительное поле номера записи. Можно улучшить (например для сортировки), добавляя поле уровня текущего узла в дереве.

- , легко получаются выборки всех родителей от заданного узла: достаточно части WHERE parent_id = const. При нормально построенных индексах время выборки (описание условий выше) в районе 0.1сек.

- , легко ищутся прямые потомки и внуки узла: достаточно объединить табличку саму с собой. Время выборки в районе 0.1-0.12сек.

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

-, Проблемы вызывает поиск ВСЕХ потомков от заданного узла. Типовые, предлагаемые решения через последовательные JOIN и UNION -- или громоздки в построении, или предполагают знание или ограничение уровней вложенности. В тестовом примере выше (ограничена глубина дерева = 5), время выполнения составного union и последовательных Join - в районе 0.15 - 0.2сек.

-, При наличии поля level и неограниченной глубине и "ветвистости" дерева, можно, поизвращавшись с переменными Мускуля, посторить один запрос (на одном само-join), который будет вытаскивать всех потомков. Время работы на тестовом примере 0.7сек. Показывает ещё более лучшее время при росте глубины деревьев при небольшой "ветвистости" узлов. Особенно в вырожденных случаях, когда большая часть узлов на разных уровнях не имеет потомков (время выборок в районе 0.25сек и меньше). Хуже при широких и не глубоких деревьях.
На тестовом примере из 21844 узлов для 4-х деревьев (ветвистость=4, глубина=6, всего узлов в одном дереве 5460), показал примерно такую же скорость - 0.5сек.

б) Построение дерева на таблице связи "parent, child, level". Понятно что поиск по индексам дает наибольшую скорость выборок. Тестовый пример - 0.12сек. Для тестового примера таблица индесков разрослась до 820500 записей (без связей узлов "сам с собой" - ищем только потомков заданного без самого узла. Его и так знаем. :)

- ?!? Как ни странно, основным доводом "против" приводят именно размер таблицы связи... от базовой отличается всего в 4 раза, а если учесть, что в базовой таблице никаких полей хранить НЕ требуется, то потери итого меньше. А если учесть, что на практике деревья редко бывают 100% заполненными - потери становятся несущественными.

В реальности на каждый добавляемый узел расходуется depth-1 запись в таблице. Операции вставки требуют дополнительного добалвения такого количества записей "вручную" (за этим надо следить!), операция удаления в ситуации внешних ключей - проблем не вызывает. Операция переноса требует изменения всех связанных записей с этим узлом...

Итого: для широких (с большим числом ветвей) и не глубоких деревьев - решение с таблицей связи оказалось наиболее оптимальным для меня в большинстве применений.

в) Nested Sets... я ваще как-то слабо понял где оно полезно. С точки зрения выборок оно нисколько не лучше таблиц связи. На каждый узел хранится номер, левый, правый интервал и уровень - 4 числа. Таблицы связи с глубиной 3 - ещё и компактнее.
Добавить 3 узла в тестовый пример в середину дерева - я просто не дождался, когда оно кончит крутить винт... больше 30сек - получилось всяко. Может я его неправильно готовил?!?

г) Список всех потомков узла в дополнительном поле родителя. При выборках в 2 приема - выбираем узел и используем строку этого поля как часть запроса IN(...). Время выборки по тестовому примеру тоже в районе 0.15сек.
Выборка в 2 этапа бывает чаще чем кажется при ООП, особенно при организации в иерархию разнородных объектов (из разных таблиц БД с разной структурой): подгрузили activeRecord об узле в одном методе (например ещё на этапе инициализации ответа на запрос) а в нужном месте тупо ищем потомков.

Недостаток - много места, для хранения небольшого количества узлов. При 6 значных номерах узлов - в 256 умещается 32 узла... маловато.
Вторая проблема - перемещения узлов... требуется корректировка списка у всех родительских узлов данного потомка...

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

Недостаток: имхо Like - это плохо, перенос узла требует тщательной перенумерации оставшихся (перенос средней ветки) или учета "дыр" в нумерации. Опять же, можно применять для небольших (не глубоких, и не широких) деревьев. И не сравнивал, но для деревьев такого типа, насколько догадываюсь - проиграет таблице связей по размерам.

Ну вот. На скорую руку, пока всё. Код не приводил сознательно - он может быть разным. Кому что нужнее от деревьев.

Ещё раз ИМХО: деревья, созданные на таблицах связи - лучшее решение для большинства применений. Плохо только с большим количеством сильно глубоких (depth > 10..100) и неветвистых(childs < 10) деревьев. В таких случаях вариант "а" - самое то.