|
Деревья в 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
---------
30
50
70
103
117
125
133
16 10
21 16
26 11
303
477
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 и родительской рубрики мы знаем и номер каждой
из них в данном списке. Выровняем эти номера до нужной длины, добавив
слева нули. После этого для каждой рубрики сделаем текстовую строку
с номерами всех её родителей от самого корня:
------------------------------
id sort parent sortorder level
------------------------------
3 10 010
5 20 020
7 30 030
10 43 0104 1
11 57 0305 1
12 65 0206 1
13 73 0107 1
16 8 10 010408 2
21 9 16 010408093
26 10 11 030510 2
30 113 0111 1
47 127 0312 1
60 13 10 010413 2
73 14 13 010714 2
75 15 47 031215 2
------------------------------
При сортировке по полю sortorder мы получим именно то, что нам нужно:
------------------------------
id sort parent sortorder level
------------------------------
3 10 010
10 43 0104 1
16 8 10 010408 2
21 9 16 010408093
60 13 10 010413 2
13 73 0107 1
73 14 13 010714 2
30 113 0111 1
5 20 020
12 65 0206 1
7 30 030
11 57 0305 1
26 10 11 030510 2
47 127 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"])). ")");
Конечно же, в отличие от дерева рубрик каталога, в
большом форуме много сообщений. Передёргивать их всех при добавлении
одного нового нет смысла.
В форумах чаще всего используется сортировка по дате написания сообщения.
Поэтому поле sortorder можно смело делать из своего и родительского
timestamp'а, выровненного функцией str_pad до 11-значной длины.
http://www.phpclub.net
|
