Вложенные множества в MySQL
Каждому программисту рано или поздно приходится столкнуться с вложенным множеством (известным как дерево или иерархия) в реляционных базах данных. В данной заметке я опишу частный случай работы с таким множеством — модель Nested Sets (далее просто Nested Sets).
Nested Sets (Вложенные множества) подразумевает присвоение каждому узлу в дереве двух дополнительных ключей left key и right key. Для заполнения этих ключей нам придется полностью обойти всё дерево дважды посещая каждый из узлов. В результате выборка из дерева будет происходить довольно быстро. С другой стороны изменение структуры требует пересчета всех ключей в узлах следующих за изменяемым узлом.
Плюсы
В базах, которые не поддерживают рекурсивные запросы (например, MySQL) выборка из дерева происходит быстрее, чем если бы она делалась с помощью хранимой процедуры.
Минусы
Изменения в базе занимают много времени, так как приходится обновлять все левые и правые ключи в записях, идущих после изменяемой.
На схеме представлен простой пример Nested sets:
| Название | Left key | Right key |
|---|---|---|
| Коктейли | 1 | 30 |
| Алкогольные | 2 | 15 |
| С бренди | 3 | 8 |
| Дракон | 4 | 5 |
| Рэднор | 6 | 7 |
| С виски | 9 | 14 |
| Квадро | 10 | 11 |
| Соблазн | 12 | 13 |
| Безалкогольные | 16 | 17 |
| Молочные | 18 | 29 |
| С мороженым | 19 | 22 |
| Комета | 20 | 21 |
| Со сливками | 23 | 28 |
| Чикита | 24 | 25 |
| Килт | 26 | 27 |
Какие выборки можно сделать?
- Все узлы дерева
SELECT * FROM tree ORDER BY left_key - Выбор дочерних узлов
SELECT * FROM tree WHERE left_key >= $left_key AND right_key - Выбор всех родительских узлов
SELECT * FROM tree WHERE left_key = $right_key ORDER BY left_key - Выбор ветки, в которой учавствует узел
SELECT * FROM tree WHERE right_key > $left_key AND left_key < $right_key ORDER BY left_key
Подробнее о работе с деревом Nested sets написано в статье Сергя Томулевича. Очень рекомендую к прочтению.
Конкретные примеры
На работе передо мной встала задача загрузить в MySQL базу классификатор ОКДП который содержит больше 44 тысяч позиций и обязательным условием было использование модели Nested sets. Классификатор распространяется в виде архива, который содержит около 15 файлов в формате XML.
Мною был написан парсер, который загружал категории в MySQL базу и сразу строил ключи. На этом примере отлично видно падение производительности на большом количестве данных в таблице. Первый файл у меня попал в базу меньше, чем за 10 минут, а последний загружался целый час. А классификатор регулярно обновляется 😉
Стало ясно, что гораздо эффективнее будет просто загрузить классификатор в базу, а уже потом строить левые и правые ключи. Для этого была написана следующая процедура, которая отработала у меня минут за 15:
— Схема таблицы, в которой будет располагаться классификатор — Для удобства я буду хранить уровень вложенности level и код родителя parent_code CREATE TABLE ` classifier ` ( ` id ` int( 10 ) unsigned NOT NULL AUTO_INCREMENT, ` level ` int( 11 ) NOT NULL , ` left_key ` int( 11 ) NOT NULL , ` right_key ` int( 11 ) NOT NULL , ` code ` varchar( 45 ) NOT NULL , ` parent_code ` varchar( 45 ) DEFAULT NULL , ` chang_data_time ` timestamp NULL DEFAULT NULL , ` start_data_active ` timestamp NULL DEFAULT NULL , ` name ` text NOT NULL , PRIMARY KEY ( id ), UNIQUE KEY ` id_UNIQUE ` (` 1 `), UNIQUE KEY ` 1 ` ( code ), KEY right_key ( right_key ), KEY left_key ( left_key ) ) ENGINE=InnoDB AUTO_INCREMENT= 1 DEFAULT CHARSET=utf8 COMMENT= ‘Классификатор ОКДП’ ; delimiter $$ DROP PROCEDURE IF EXISTS rebuild_nested_set_tree$$ CREATE PROCEDURE rebuild_nested_set_tree() BEGIN — Изначально сбрасываем все границы UPDATE classifier SET level = 0 , left_key = 0 , right_key = 0 ; — Устанавливаем границы корневым элементам SET @i := 0 ; UPDATE classifier SET left_key = (@i := @i + 1 ), right_key = (@i := @i + 1 ) WHERE parent_code IS NULL ; SET @parent_code := NULL ; SET @parent_right := NULL ; forever: LOOP — Находим элемент с минимальной правой границей — самый левый в дереве SET @parent_code := NULL ; SELECT t.` code `, t.` right_key ` FROM ` classifier ` t, ` classifier ` tc WHERE t.` code ` = tc.` parent_code ` AND tc.` left_key ` = 0 AND t.` right_key ` <> 0 ORDER BY t.` right_key `, t.` code ` LIMIT 1 INTO @parent_code, @parent_right; — Выходим из бесконечности, когда у нас уже нет незаполненных элементов IF @parent_code IS NULL THEN LEAVE forever; END IF ; — Сохраняем левую границу текущего ряда SET @current_left := @parent_right; — Вычисляем максимальную правую границу текущего ряда SELECT @current_left + COUNT (*) * 2 FROM ` classifier ` WHERE ` parent_code ` = @parent_code INTO @parent_right; — Вычисляем длину текущего ряда SET @current_length := @parent_right — @current_left; — Обновляем правые границы всех элементов, которые правее UPDATE ` classifier ` SET ` right_key ` = ` right_key ` + @current_length WHERE ` right_key ` >= @current_left ORDER BY ` right_key `; — Обновляем левые границы всех элементов, которые правее UPDATE ` classifier ` SET ` left_key ` = ` left_key ` + @current_length WHERE ` left_key ` > @current_left ORDER BY left_key; — И только сейчас обновляем границы текущего ряда SET @i := @current_left — 1 ; UPDATE ` classifier ` SET ` left_key ` = (@i := @i + 1 ), ` right_key ` = (@i := @i + 1 ) WHERE ` parent_code ` = @parent_code ORDER BY ` code `; END LOOP ; — Дальше заполняем поля level — Устанавливаем 1-й уровень всем корневым категориям классификатора UPDATE ` classifier ` SET ` level ` = 1 WHERE ` parent_code ` IS NULL ; SET @unprocessed_rows_count = 100500 ; WHILE @unprocessed_rows_count > 0 DO UPDATE ` classifier ` top, ` classifier ` bottom SET bottom.` level ` = top.` level ` + 1 WHERE bottom.` level ` = 0 AND top.` level ` <> 0 AND top.` code ` = bottom.` parent_code `; SELECT COUNT (*) FROM ` classifier ` WHERE ` level ` = 0 LIMIT 1 INTO @unprocessed_rows_count; END WHILE ; END $$ CALL rebuild_nested_set_tree()$$ DROP PROCEDURE IF EXISTS rebuild_nested_set_tree$$
Источник
Работа с MySQL. Деревья
Необходимость вывода данных структурированных в форме деревьев возникает при написании собственного форума или каталога сайтов. Готовых каталогов и форумов в сети можно найти предостаточно, однако иногда чужое в готовом не годится, а переделывать написанное другим займёт гораздо больше времени, чем написать своё.
Структуру данных лучше взять общепринятую — в записи сообщения или рубрики форума содержится идентификатор родителя. Для организации вывода дерева напрашивается рекурсивная функция. Именно так сделано в Phorum’е [http://phorum.org]. Файл include/multi-threads.php содержит функцию thread, которая строит вызывается для каждого корневого сообщения и рекурсивно вызывает себя для ответов на них:
Но вызов рекурсивной функции при выводе вызывает у меня сомнения: повторять построение дерева сообщений при каждом выводе нерационально. Структура дерева меняется только при добавлении, изменении и удалении сообщений. Данную процедуру лучше было бы вызывать при таких действиях, хранить структуру в таблице и при выводе дерева не делать никаких вычислений.
Для построения дерева достаточно знать последовательность вывода рубрик и их уровень в дереве. Добавим два поля с этими данными в таблицу: 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 и родительской рубрики мы знаем и номер каждой из них в данном списке. Выровняем эти номера до нужной длины, добавив слева нули. После этого для каждой рубрики сделаем текстовую строку с номерами всех её родителей от самого корня:
------------------------------ 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 ------------------------------
При сортировке по полю sortorder мы получим именно то, что нам нужно:
------------------------------ 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"])). ")"); Конечно же, в отличие от дерева рубрик каталога, в большом форуме много сообщений. Передёргивать их всех при добавлении одного нового нет смысла.
Источник