Работа с 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"])). ")"); ?>

Статьи по теме

Оптимизация и тюнинг производительности MariaDB MySQL сервера внутри Docker

Содержание: Установка и знакомство с MySQLTuner Установка MySQL Tuning Primer Script Первичная оптимизация MySQL сервера ...

2023-11-08

Работа с базами данных MySQL в ISPManager 5 + Docker

В ISPManager 5 добавлена контейнерная виртуализация Docker для использования альтернативных версий MySQL. Цитата из документации ISPManager 5: ...

2023-10-27

«Облачные» хранилища данных: в ожидании доверия

Информационные технологии активно мигрируют в сторону «облаков». Эксперты прогнозируют, что одним из главных приоритетов для CIO в ближ...

2011-11-05

ГОСТ 34.602-89. на Техническое задание по разработке web проекта

ТЕХНИЧЕСКОЕ ЗАДАНИЕ НА СОЗДАНИЕ АВТОМАТИЗИРОВАННОЙ СИСТЕМЫ Information technology. Set of standards for automated systems. Technical directions ...

2010-12-28

Orange color: теория и практика

Знаете ли Вы, чем оранжевый цвет отличается от других ? Если нет, то знайте, что разница в скорости восприятия глазом отдельных цветов ра...

2010-12-27

FAQ по MS SQL 7.0

11. Как запускать-останавливать SQL Server через командную строку? Мне это нужно для использования в скриптах.Остановка:NET STOP MSSQLSERVERили если вы...

2010-09-17

Виртуальная реализация SQL Server 2005

Ранее в материале «Разбираем “айсберг” sql server 2005» читателям предлагалось воспользоваться опубликованной в internet серией информационных...

2010-09-17

SQL Server в вопросах и ответах

В: У меня на разных компьютерах установлено два sql server 7.0. Для обмена данными между ними я использовал data transformation services (dts), чтобы импортиро�...

2010-09-17

Один из вариантов соглашения об именах объектов MS SQL Server

Помните, что имена объектов sql сервера не могут превышать 30 символов. Не используйте зарезервированные слова, специальные символы, и не н...

2010-09-17

Создание и удаление БД в MS SQL Server

В sql server'е базы данных хранятся в виде обычных файлов на диске. Как минимум на одну БД приходится таких файлов 2: *.mdf и *.ldf. В первом хранятся...

2010-09-17

Создание и удаление таблиц в MS SQL Server

Все данные в БД sql server хранятся в таблицах.Таблицы состоят из колонок, объединяющих значения одного типа, и строк - записей в таблице. В од�...

2010-09-17

Единая аутентификация Windows NT/2000 и Oracle

При использовании Windows NT/2000 как платформы для работы Oracle, и на стороне сервера и на стороне клиентов, имеется возможность использовать ед...

2010-09-17

Oracle / PHP FAQ

Что такое PHP и что необходимо иметь для работы с Oracle?PHP - рекурсивный акроним "PHP Hypertext Preprocessor". Это интерпретируемый язык программирования ...

2010-09-17

Oracle и PHP - это очень просто

ВведениеСУБД Oracle, когда против желания фирмы-изготовителя, а когда согласно – в зависимости от направления политических ветров в конкр�...

2010-09-17

Сжатие данных в целях экономии места и ускорения работы Oracle

Используйте сжатие данных таблицы для экономии места на диске и повышения производительности запросов. В большинстве систем поддержки ...

2010-09-17