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

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

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


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 и цикл запускается ещё раз.


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:

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"])). ")"); ?>



Читать комменты и комментировать

Добавить комментарий / отзыв



Защитный код
Обновить

Работа с MySQL. Деревья | | 2010-09-11 02:01:59 | | Базы данных | | Необходимость вывода данных структурированных в форме деревьев возникает при написании собственного форума или каталога сайтов. Готовых каталогов и форумов в сети можно найти предостаточно, однако | РэдЛайн, создание сайта, заказать сайт, разработка сайтов, реклама в Интернете, продвижение, маркетинговые исследования, дизайн студия, веб дизайн, раскрутка сайта, создать сайт компании, сделать сайт, создание сайтов, изготовление сайта, обслуживание сайтов, изготовление сайтов, заказать интернет сайт, создать сайт, изготовить сайт, разработка сайта, web студия, создание веб сайта, поддержка сайта, сайт на заказ, сопровождение сайта, дизайн сайта, сайт под ключ, заказ сайта, реклама сайта, хостинг, регистрация доменов, хабаровск, краснодар, москва, комсомольск |
 
Поделиться с друзьями: