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

Структуру данных лучше взять общепринятую - в записи сообщения или рубрики форума содержится идентификатор родителя. Для организации вывода дерева напрашивается рекурсивная функция. Именно так сделано в Phorum'е [http://phorum.org]. Файл include/multi-threads.php содержит функцию thread, которая строит вызывается для каждого корневого сообщения и рекурсивно вызывает себя для ответов на них:



Но вызов рекурсивной функции при выводе вызывает у меня сомнения: повторять построение дерева сообщений при каждом выводе нерационально. Структура дерева меняется только при добавлении, изменении и удалении сообщений. Данную процедуру лучше было бы вызывать при таких действиях, хранить структуру в таблице и при выводе дерева не делать никаких вычислений.

Для построения дерева достаточно знать последовательность вывода рубрик и их уровень в дереве. Добавим два поля с этими данными в таблицу: level (TINYINT(4). 127 уровней - хватит?) и sortorder (VARCHAR(128)).

Всё, что нам нужно для построения дерева - это идентификатор рубрики и её родителя. Допустим, мы имеем в каталоге несколько рубрик такого содержания:



Структура дерева, подобие которой мы хотим получить такова:



Правда, данный алгоритм позволит нарисовать дерево, но без веток виде линий, как сделано на этом рисунке. Структура дерева будет нарисована при помощи отступов слева.

Вернёмся ещё раз к таблице id-parent. Это рубрики, уже отсортированные по некоторому признаку, по которому мы хотим сортировать элементы одинакового уровня. Например, по убыванию числа сайтов. Кроме id и родительской рубрики мы знаем и номер каждой из них в данном списке. Выровняем эти номера до нужной длины, добавив слева нули. После этого для каждой рубрики сделаем текстовую строку с номерами всех её родителей от самого корня:



При сортировке по полю sortorder мы получим именно то, что нам нужно:



Отступ слева делается, учитывая поле level.

Важно так же отметить, что нам не нужно ничего сортировать в самом скрипте. Для формирования полей sortorder и level нужно заблокировать таблицу от записи (чтобы не произошло изменения структуры веток), выбрать из базы идентификатор рубрики и её родителя, отсортировав по нужному признаку, и записать их в простой двухмерный массив. Затем обработать массив последовательно от первого до последнего уровня и записать поля sortorder и level в таблицу.

Для формирования sortorder не нужно рекурсии (хотя можно, и, вероятно, она работать будет даже быстрее). Достаточно пройтись по массиву одним и тем же циклом. В нём, если рубрика не обработана, для неё формируется поле sortorder из поля sort и родительского sortorder. Если родительская рубрика ещё не обработана, поднимается флаг $unprocessed_rows_exist и цикл запускается ещё раз.



Отмечу, что данный алгоритм не зацикливается при наличии строк с битым полем parent и не пропускает их, а делает корневыми. Рекурсивный алгоритм их просто пропустит.

После выполнения этого цикла мы имеем массивы "id => level" и "id => sortorder". Отправляем в базу всего один запрос, пользуясь внутренними функциями MySQL ELT и FIND_IN_SET:



Конечно же, в отличие от дерева рубрик каталога, в большом форуме много сообщений. Передёргивать их всех при добавлении одного нового нет смысла.

В форумах чаще всего используется сортировка по дате написания сообщения. Поэтому поле sortorder можно смело делать из своего и родительского timestamp'а, выровненного функцией str_pad

Я бы сделал следующие комментарии к коду.

1.

У тебя используется сейчас 127 уровней - значит, под них нужно 2*127=254 байта для строки, в которую ты будешь писать цифры. А не 128.

2. Ты ограничил при этом уровень вложенности 99-ю, так как именно столько может храниться в двухцифровом числе. А делаешь ли ты эти проверки в коде? (Читать код сейчас не хочу, если делаешь, извини. Но всё равно - зачем ограничение 99? Можно, конечно, 16-ричное представление использовать...)

3. sortorder (VARCHAR(128)) я обычно заменяю на sortorder (INTEGER). Так индексировать приходится меньше данных, и меньше искусственности с методе. Обновление же данных очень просто: находим новую позицию для сущности (pos_new), и затем делаем UPDATE dir SET sortorder = sortorder + 1 WHERE sortorder > pos_new;

Экономия места и выигрыш в скорости индексации бесспорны. Но ведь и максимальный level будет не 127, а от силы 10 (при unsigned bigint и том же ограничении в 99 потомков на уровне), разве нет?

Какая-то старая тема очень... 

Нет, не десять. Потому что одному элементу дерева здесь соответствует увеличение sortorder на единицу.

-- 1
---- 2
-- 3
---- 4
------5
-- 6
-- 7

И так далее.

Естественно, это не очень оптимально при громадных деревьях.
Но в реалиях я обычно применяю этот способ для построения дерева комментариев: а комментов редко бывает больше сотни (для одной комментируемой сущности). При этом в той же таблице комментариев есть поле something_id (FK на комментируемую сущность). И сортировка в этом случае -- своя для каждой сущности. То есть запрос обновления будет выглядеть не как UPDATE dir SET sortorder = sortorder + 1 WHERE sortorder > pos_new; (что я написал выше), а UPDATE dir SET sortorder = sortorder + 1 WHERE sortorder > pos_new AND something_id = 123;

dm9,

Вроде не очень - всего полгода. Просто на этой неделе некоторый бум вопросов про деревья...


Хм... я имел в виду пример из статьи, где в поле с этим названием по сути собирался материализованный путь (по 2 разряда на уровень, оттого и ограничение в 99), и исходил из максимум 20-значного целого в MySQL. Хотя теперь до меня дошло, что если сделать его числовым, то сортировка по нему (как в статье) работать просто не будет. По-моему, Вы говорите о каком-то принципиально другом методе ;).

Ну да. Я же, вроде, описал свой подход. И даже привёл примеры.
Посмотрите внимательнее ещё раз. Если непонятно -- могу попробовать поподробнее описать.

dm9, т.е. положение элемента в дереве описывают 2 числа - номер строки при выводе и уровень вложенности ("отступ слева"), теперь я правильно понял?

И да, и нет.
Эти два числа, по сути, кэш для более быстрых выборок.
Оба они могут быть восстановлены на основе FK parent_id.

Добавлено через 10 минут и 3 секунды
Этот метод хорош для неизменяемой структуры дерева -- например, тот же список комментариев.
Если же структура дерева предполагает изменяться (например, дерево разделов сайта), то нужны другие методы -- этот слишком неоптимален при обновлении, есть у него и другие минусы. Для дерева разделов я использую parent_id, но не сохраняю level и order -- но кэширую результат рекурсивной выборки в PHP-структуру и/или XML.

dm9, спасибо за объяснение!