Вложенные множества в MySQL

Каждому программисту рано или поздно приходится столкнуться с вложенным множеством (известным как дерево или иерархия) в реляционных базах данных. В данной заметке я опишу частный случай работы с таким множеством — модель Nested Sets (далее просто Nested Sets).

Nested Sets (Вложенные множества) подразумевает присвоение каждому узлу в дереве двух дополнительных ключей left key и right key. Для заполнения этих ключей нам придется полностью обойти всё дерево дважды посещая каждый из узлов. В результате выборка из дерева будет происходить довольно быстро. С другой стороны изменение структуры требует пересчета всех ключей в узлах следующих за изменяемым узлом.

Плюсы

В базах, которые не поддерживают рекурсивные запросы (например, MySQL) выборка из дерева происходит быстрее, чем если бы она делалась с помощью хранимой процедуры.

Минусы

Изменения в базе занимают много времени, так как приходится обновлять все левые и правые ключи в записях, идущих после изменяемой.

На схеме представлен простой пример Nested sets:

Дерево MySQL

Табличное представление:

НазваниеLeft keyRight key
Коктейли130
Алкогольные215
С бренди38
Дракон45
Рэднор67
С виски914
Квадро1011
Соблазн1213
Безалкогольные1617
Молочные1829
С мороженым1922
Комета2021
Со сливками2328
Чикита2425
Килт2627

Какие выборки можно сделать?

  • Все узлы дерева
    SELECT * FROM tree ORDER BY left_key
  • Выбор дочерних узлов
    SELECT * FROM tree WHERE left_key >= $left_key AND right_key <= $right_key ORDER BY left_key
  • Выбор всех родительских узлов
    SELECT * FROM tree WHERE left_key <= $left_key AND right_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$$