From: Дмитрий Лебедев
Newsgroups: http://detail.phpclub.net
Date: Mon, 20 Dec 2004 18:21:07 +0000 (UTC)
Subject: Работа с древовидными структурами в MySQL
Необходимость вывода данных структурированных в форме деревьев
возникает при написании собственного форума или каталога сайтов.
Готовых каталогов и форумов в сети можно найти предостаточно, однако
иногда чужое в готовом не годится, а переделывать написанное другим
займёт гораздо больше времени, чем написать своё.
Структуру данных лучше взять общепринятую - в записи сообщения или
рубрики форума содержится идентификатор родителя. Для организации
вывода дерева напрашивается рекурсивная функция. Именно так сделано в
Phorum'е (http://phorum.org/). Файл include/multi-threads.php содержит
функцию thread, которая строит вызывается для каждого корневого сообщения
и рекурсивно вызывает себя для ответов на них:
Но вызов рекурсивной функции при выводе вызывает у меня сомнения:
повторять построение дерева сообщений при каждом выводе нерационально.
Структура дерева меняется только при добавлении, изменении и удалении
сообщений. Данную процедуру лучше было бы вызывать при таких
действиях, хранить структуру в таблице и при выводе дерева не делать
никаких вычислений.
Для построения дерева достаточно знать последовательность вывода
рубрик и их уровень в дереве. Добавим два поля с этими данными в
таблицу: level (TINYINT(4). 127 уровней - хватит?) и sortorder
(VARCHAR(128)).
Всё, что нам нужно для построения дерева - это идентификатор рубрики и
её родителя. Допустим, мы имеем в каталоге несколько рубрик такого
содержания:
Структура дерева, подобие которой мы хотим получить такова:
Правда, данный алгоритм позволит нарисовать дерево, но без веток виде
линий, как сделано на этом рисунке. Структура дерева будет нарисована
при помощи отступов слева.
Вернёмся ещё раз к таблице id-parent. Это рубрики, уже отсортированные
по некоторому признаку, по которому мы хотим сортировать элементы
одинакового уровня. Например, по убыванию числа сайтов. Кроме id и
родительской рубрики мы знаем и номер каждой из них в данном списке.
Выровняем эти номера до нужной длины, добавив слева нули. После этого
для каждой рубрики сделаем текстовую строку с номерами всех её
родителей от самого корня:
При сортировке по полю sortorder мы получим именно то, что нам нужно:
Важно так же отметить, что нам не нужно ничего сортировать в самом
скрипте. Для формирования полей sortorder и level нужно заблокировать
таблицу от записи (чтобы не произошло изменения структуры веток),
выбрать из базы идентификатор рубрики и её родителя, отсортировав по
нужному признаку, и записать их в простой двухмерный массив. Затем
обработать массив последовательно от первого до последнего уровня и
записать поля sortorder и level в таблицу.
Для формирования sortorder не нужно рекурсии (хотя можно, и, вероятно,
она работать будет даже быстрее). Достаточно пройтись по массиву одним
и тем же циклом. В нём, если рубрика не обработана, для неё
формируется поле sortorder из поля sort и родительского sortorder.
Если родительская рубрика ещё не обработана, поднимается флаг
$unprocessed_rows_exist и цикл запускается ещё раз.
Отмечу, что данный алгоритм не зацикливается при наличии строк с битым
полем parent и не пропускает их, а делает корневыми. Рекурсивный
алгоритм их просто пропустит.
После выполнения этого цикла мы имеем массивы "id => level" и "id =>
sortorder". Отправляем в базу всего один запрос, пользуясь внутренними
функциями MySQL ELT и FIND_IN_SET:
<?php mysql_query("UPDATE dir SET sortorder=ELT(FIND_IN_SET(id,'".
implode(",", array_keys($data["sortorder"])). "'),". implode(",",
$data["sortorder"]). "), level=ELT(FIND_IN_SET(id,'". implode(",",
array_keys($data["level"])). "'),". implode(",", $data["level"]). ")
WHERE id IN (". implode(",", array_keys($data["sortorder"])). ")"); ?>
Конечно же, в отличие от дерева рубрик каталога, в большом форуме
много сообщений. Передёргивать их всех при добавлении одного нового
нет смысла.
В форумах чаще всего используется сортировка по дате написания
сообщения. Поэтому поле sortorder можно смело делать из своего и
родительского timestamp'а, выровненного функцией str_pad до
11-значной длины.
Комментарии:
- http://dev.e-taller.net/dbtree/
- Статья (правда на английском) про два метода хранения иерархических
данных в базе:
http://www.sitepoint.com/print/1105
- Когда-то я пользовался тем, как сделано в phorum'e, но из-за того что
нельзя выбрать ветку, не пресмотрев всё дерево, перешел на ту модель,
что используется на frashmeat, sourceforge, gforge и т.п. Скрипты
администрирования конечно сложнее, на cron надо ставить, но в целом
всё горазно проще и удобнее, причем один элемент может находится в
нескольких категориях одновременно.
- этот алгоритм работает, пока нет необходимости показать все
подэлементы данному элементу.
1412 Прочтений • [Работа с древовидными структурами в MySQL (sql mysql php tree)] [08.05.2012] [Комментариев: 0]
Vova
