Профессиональная разработка Web-приложений.  
Боишься нашего дизайна?
Новости
PDF журнал
Участники проектa
Сотрудничество
Ссылки
Карта сайта
Комментарии
Комментарии к статье
Добавить комментарий
Обсудить на форуме
Информация об авторе
Оценка статьи

Работа с MySQL. Деревья

Построение дерева в MySQL без рекурсии.

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

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

<?php
function thread ($seed 0) {
...

    if(@
is_array($messages[$seed]["replies"])) {
        
$count count($messages[$seed]["replies"]);
        for(
$x 1;$ <= $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] == || !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-значной длины.




For comment register here
   Unknown 2002-06-04 09:46
Спасибо, как раз пару недель назад я над этим думал - прикрутить древовидную структуру к моим комментариям, и тоже пришел к выводу, что для этого достаточно ввести всего еще один парамерт - level.

   Unknown 2002-06-12 15:50
Это известная фенька: чтобы быстрее работало, нужно больше памяти для хранения, и наоборот, если важен размер базы, можно выкрутиться засчет потери скорости.

   2002-06-13 01:19
а как на счет етого???
http://dev.e-taller.net/dbtree/

   Unknown 2002-06-18 14:04
Для каталога сайтов м.б. чего попроще? Редко где больше 2-3 уровней бывает.

   2002-06-21 14:50
Подход довольно интересный, НО...

Все бы ничего, но если мне вдруг надо перенести 7 элемент с сохранением ( или без сохранения) всей структуры, скажем под 5-ый элемент. Этож сколько переправлять придется??? а если элементов структуры 7ки довольно много?

Я, естественно, имею в виду только тот случай, когда сортировка важна и ей можно управлять.

   Unknown 2002-06-24 22:34
А зачем так мучаться? по-моему, даже level'a не нужно

   Unknown 2002-06-24 23:27
В принципе - да, но лучше не считать отступ при _каждом_ выводе. Получается экономия счётных ресурсов, а объём такое поле занимает небольшой.

   2002-06-27 15:38
>>Отступ слева делается, учитывая поле level.

А зачем? Вполне возможно отступ можно рассчитать по формуле length(sortorder)/2 (для данного случая)
То есть поле level , похоже, не нужно.
А еще, для уменьшения поля sortorder, можно каждое добавляемое к строке число конвертить в другую систему счисления (напр. с основанием не 10 а 128) - строка немного уменьшится

   2003-05-30 16:02
Спасибо. Ознакомился с dbTree.

Если можете, подскажите, как изменить порядок расположения детей (Процедура помещающая заданный узел перед указанным).

   2003-12-02 06:31
Когда-то я пользовался тем, как сделано в phorum'e, но из-за того что нельзя выбрать ветку, не пресмотрев всё дерево, перешел на ту модель, что используется на frashmeat, sourceforge, gforge и т.п. Скрипты администрирования конечно сложнее, на cron надо ставить, но в целом всё горазно проще и удобнее, причем один элемент может находится в нескольких категориях одновременно.

   2003-12-09 19:42
этот алгоритм работает, пока нет необходимости показать все подэлементы данному элементу.

   2004-07-07 11:02
Всё хорошо. Едиственное, чего не хватает - вычисления переменной $max. Досадно - наверное, автор просто забыл скопировать эту строчку.. А без неё str_pad() не работает. И следовательно sortorder будет без заветных нулей. Если кто знает, как считать $max - напишите на мыло, пожалуйста.

   2004-11-07 16:30
А автоматический пронумеровать ветви дерева кто-то пробывал?
типа
1.
1.1
1.2
1.2.1
1.2.2
....... и т.д. ??

   2007-02-21 20:42
А зачем нам поле level, если это length(sortorder)/2 - 1 ?

   2007-06-26 17:02
Еще один пример Деревьев написан мною, мне кажеться что просто проще не куда
Таблица БД состоит всего из 2 обязательных полей ето ID категории и предыдущее ID, оба поля INT
но у меня для наглядности еще одно поле name(varchar)

&lt;table border=1&gt;
&lt;?

mysql_pconnect(&quot;localhost&quot;,&quot;root&quot;,&quot;&quot;);
mysql_select_db(&quot;tt&quot;);
$query = mysql_query(&quot;select * from news_group&quot;);
while ($r = mysql_fetch_array($query)) {
if ($r[p_id] == 0) {
echo &quot;&lt;td&gt;&quot;.$r[name].&quot;&lt;/td&gt;&lt;tr&gt;&quot;;
in($r[id],$r[p_id]);
}
}
function in($id,$pid) {
$query = mysql_query(&quot;select * from news_group where p_id=&quot;.$id.&quot;&quot;);
while ($r = mysql_fetch_array($query)) {
echo &quot;&lt;td&gt;&quot;;
for ($i=0; $i&lt;$pid; $i++){
echo &quot;&amp;nbsp&amp;nbsp&amp;nbsp&amp;nbsp&amp;nbsp&quot;;
}
echo $r[name].&quot;&lt;/td&gt;&lt;tr&gt;&quot;;
in($r[id],$r[p_id]);
}

}

?&gt;
&lt;/table&gt;

P.S. что, не понятно жду писем на email.

Построение дерева в MySQL без рекурсии.

 
 
 
    © 1997-2008 PHPClubTeam
[]