The OpenNET Project / Index page

[ новости /+++ | форум | wiki | теги | ]

Работа с древовидными структурами в MySQL (sql mysql php tree)


<< Предыдущая ИНДЕКС Поиск в статьях src Установить закладку Перейти на закладку Следующая >>
Ключевые слова: sql, mysql, php, tree,  (найти похожие документы)
From: Дмитрий Лебедев Newsgroups: http://detail.phpclub.net Date: Mon, 20 Dec 2004 18:21:07 +0000 (UTC) Subject: Работа с древовидными структурами в MySQL Оригинал: http://detail.phpclub.net/article/2002-06-03 Работа с MySQL. Деревья Дмитрий Лебедев 2002-06-03 Построение дерева в MySQL без рекурсии. Необходимость вывода данных структурированных в форме деревьев возникает при написании собственного форума или каталога сайтов. Готовых каталогов и форумов в сети можно найти предостаточно, однако иногда чужое в готовом не годится, а переделывать написанное другим займёт гораздо больше времени, чем написать своё. Структуру данных лучше взять общепринятую - в записи сообщения или рубрики форума содержится идентификатор родителя. Для организации вывода дерева напрашивается рекурсивная функция. Именно так сделано в Phorum'е (http://phorum.org/). Файл include/multi-threads.php содержит функцию thread, которая строит вызывается для каждого корневого сообщения и рекурсивно вызывает себя для ответов на них: <?php function thread ($seed = 0) { ... if(@is_array($messages[$seed]["replies"])) { $count = count($messages[$seed]["replies"]); for($x = 1;$ x <= $count; $x++) { $key = key($messages[$seed]["replies"]); thread ($key); next ($messages[$seed]["replies"]); } } } ?> Но вызов рекурсивной функции при выводе вызывает у меня сомнения: повторять построение дерева сообщений при каждом выводе нерационально. Структура дерева меняется только при добавлении, изменении и удалении сообщений. Данную процедуру лучше было бы вызывать при таких действиях, хранить структуру в таблице и при выводе дерева не делать никаких вычислений. Для построения дерева достаточно знать последовательность вывода рубрик и их уровень в дереве. Добавим два поля с этими данными в таблицу: level (TINYINT(4). 127 уровней - хватит?) и sortorder (VARCHAR(128)). --------- id parent --------- 3 0 5 0 7 0 10 3 11 7 12 5 13 3 16 10 21 16 26 11 30 3 47 7 60 10 73 13 75 47 --------- o- 3 | +-o- 10 | | | +-o- 16 | | | | | +-o- 21 | | | +-o- 60 | +-o- 13 | | | +-o- 73 | +-o- 30 o- 5 | +-o- 12 o- 7 | +-o- 11 | | | +-o- 26 | +-o- 47 | +-o- 75 Всё, что нам нужно для построения дерева - это идентификатор рубрики и её родителя. Допустим, мы имеем в каталоге несколько рубрик такого содержания: Структура дерева, подобие которой мы хотим получить такова: Правда, данный алгоритм позволит нарисовать дерево, но без веток виде линий, как сделано на этом рисунке. Структура дерева будет нарисована при помощи отступов слева. Вернёмся ещё раз к таблице id-parent. Это рубрики, уже отсортированные по некоторому признаку, по которому мы хотим сортировать элементы одинакового уровня. Например, по убыванию числа сайтов. Кроме id и родительской рубрики мы знаем и номер каждой из них в данном списке. Выровняем эти номера до нужной длины, добавив слева нули. После этого для каждой рубрики сделаем текстовую строку с номерами всех её родителей от самого корня: При сортировке по полю sortorder мы получим именно то, что нам нужно: ------------------------------ id sort parent sortorder level ------------------------------ 3 1 0 01 0 5 2 0 02 0 7 3 0 03 0 10 4 3 0104 1 11 5 7 0305 1 12 6 5 0206 1 13 7 3 0107 1 16 8 10 010408 2 21 9 16 01040809 3 26 10 11 030510 2 30 11 3 0111 1 47 12 7 0312 1 60 13 10 010413 2 73 14 13 010714 2 75 15 47 031215 2 ------------------------------ ------------------------------ id sort parent sortorder level ------------------------------ 3 1 0 01 0 10 4 3 0104 1 16 8 10 010408 2 21 9 16 01040809 3 60 13 10 010413 2 13 7 3 0107 1 73 14 13 010714 2 30 11 3 0111 1 5 2 0 02 0 12 6 5 0206 1 7 3 0 03 0 11 5 7 0305 1 26 10 11 030510 2 47 12 7 0312 1 75 15 47 031215 2 ------------------------------ Отступ слева делается, учитывая поле level. Важно так же отметить, что нам не нужно ничего сортировать в самом скрипте. Для формирования полей sortorder и level нужно заблокировать таблицу от записи (чтобы не произошло изменения структуры веток), выбрать из базы идентификатор рубрики и её родителя, отсортировав по нужному признаку, и записать их в простой двухмерный массив. Затем обработать массив последовательно от первого до последнего уровня и записать поля sortorder и level в таблицу. Для формирования sortorder не нужно рекурсии (хотя можно, и, вероятно, она работать будет даже быстрее). Достаточно пройтись по массиву одним и тем же циклом. В нём, если рубрика не обработана, для неё формируется поле sortorder из поля sort и родительского sortorder. Если родительская рубрика ещё не обработана, поднимается флаг $unprocessed_rows_exist и цикл запускается ещё раз. <?php mysql_query("LOCK TABLES dir WRITE"); $result = mysql_query("SELECT id, IFNULL(parent,0) as parent FROM dir ORDER BY sites DESC, title"); while ($row = mysql_fetch_array($result)) { $count++; $data["parent"][$row["id"]] = $row["parent"]; $data["sort"][$row["id"]] = $count; } reset($data); $unprocessed_rows_exist = true; while($unprocessed_rows_exist) { $unprocessed_rows_exist = false; while (list($i, $v) = each($data["parent"])) { if(($data["parent"][$i] == 0 || !isset($data["sort"][$data["parent"][$i]])) && !isset($data["sortorder"][$i])) { $data["sortorder"][$i] = str_pad($data["sort"][$i], $max, "0", STR_PAD_LEFT); $data["level"][$i] = 0; } elseif(!isset($data["sortorder"][$i]) && isset($data["sortorder"][$data["parent"][$i]])) { $data["sortorder"][$i] = $data["sortorder"][$data["parent"][$i]]. str_pad($data["sort"][$i], $max, "0", STR_PAD_LEFT); $data["level"][$i] = $data["level"][$data["parent"][$i]] + 1; } elseif(!isset($data["sortorder"][$i]) && isset($data["sort"][$data["parent"][$i]])) { $unprocessed_rows_exist = true; } } reset($data); ?> Отмечу, что данный алгоритм не зацикливается при наличии строк с битым полем 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 надо ставить, но в целом всё горазно проще и удобнее, причем один элемент может находится в нескольких категориях одновременно. - этот алгоритм работает, пока нет необходимости показать все подэлементы данному элементу.

<< Предыдущая ИНДЕКС Поиск в статьях src Установить закладку Перейти на закладку Следующая >>

Обсуждение [ RSS ]
  • 1, AirWorker (?), 20:18, 24/11/2007 [ответить]  
  • +/
    А рекурсия + кеширование чем не устраивают?
    Помоему проще, надежнее и производительнее
     
     
  • 2, Дима (??), 12:20, 15/08/2010 [^] [^^] [^^^] [ответить]  
  • +/
    Например,
    1. Нужно получить всех детей для заданного узла, включая вложненные.
    2. Нужно получить всех родителей для заданного узла.
    и так далее. Эти операции осуществляются за один SQL-запрос по проиндексированным значениям левого и правого чисел.
    А при использовании рекурсии будет по одному SQL-запросу на каждой итерации.

    А кеширование всегда должно быть к месту: не всегда полезно хранить узлы дерева в кеше, если обращение к этим узлам нечастое. Или, например, кол-во узлов дерева очень большое, и хранить все дерево в кеше невозможно. Для каких-то задач правильнее будет хранить в кеше не узлы дерева (id, parentId), а их содержимое. При оптимальной мощности кеша и при частом обращении к одному и тому же содержимому узлов это будет полезно.

     

     Добавить комментарий
    Имя:
    E-Mail:
    Заголовок:
    Текст:




    Спонсоры:
    Inferno Solutions
    Hosting by Hoster.ru
    Хостинг:

    Закладки на сайте
    Проследить за страницей
    Created 1996-2021 by Maxim Chirkov
    Добавить, Поддержать, Вебмастеру