Введение
В своей предыдущей статье я дал краткий обзор основных моделей хранения иерархических структур в реляционных БД. Как и положено тому быть, у многих читателей стал вопрос ребром о производительности представленных алгоритмов.
В данной статье я постараюсь приоткрыть завесу над этим животрепещущим вопросом, а в следующей обещаю коснуться вопросов оптимизации и поисков нестандартных решений.
Подготовка
Итак, тестирование. Как и любое другое тестирование, наше также требует определенных действий по подготовке, анализу, выработке целей и плана действий.
Фактически, целью является проведение серии стресс-тестов различных алгоритмов на различных объемах данных. Неплохо было бы также прогнать тесты на нескольких различных аппаратных платформах, но, увы, автору это не по силам (время и деньги — всему виной).
Естественно, хорошо было бы провести тесты наиболее важных и значимых операций, которые как правило выполняются над теми или иными деревьями. После достаточно продолжительных размышлений было решено остановиться на таком списке тестируемых операций:
- Выборка всего дерева целиком
- Выборка пути к заданному узлу
- Выборка ветки заданного узла
- Поиск родителя заданного узла
- Поиск наследников заданного узла
- Добавление нового узла в конец заданного родительского узла
- Перемещение узла (или же, другими словами — смена родителя)
- Удаление узла (и всей ветки под ним)
Стоит отметить, что данные операции мы приближаем к боевым условиям, т.е. входными данными для нас будут идентификаторы узлов и их родителей. Это позволит не привязываться к конкретным реализациям каждого из алгоритмов.
Далее оговорим, что нас интересует производительность чистого SQL, поэтому мы будем делать замеры исключительно его работы.
Автор не претендует на полноту заявленного списка операций. Возможно, кто-то вспомнит об операциях поиска соседей узла или выборке всех листов дерева, да еще и в заданной ветке — пожалуйста, каждый вправе расширить и дополнить данный эксперимент. Я же пока остановлюсь на приведенной, по моему мнению, основной минимальной функциональности.
Теперь я хочу остановиться несколько подробней на реализации самих функций, тесты над которыми в дальнейшем будут проведены. Но, если вам интересны лишь голые цифры и факты, — вы можете перейти к следующему разделу статьи.
Далеко не все заявленные функции имеют тривиальные решения в разных методах, тем более на чистом SQL. Например, выбор ветки в AL-дереве — задача сугубо рекурсивная. Но стоит ли этим заниматься на уровне SQL?..
В целом, следует учесть несколько следующих положений:
— СУБД, на которой производятся тесты — MySQL версии 5.0.x. Движок — InnoDB (удобен для реализации каскадных операций для AL-Tree на уровне БД).
— Запросы на выборку выполняются с флагом SQL_NO_CACHE, чтобы оценить «чистые» затраты на выполнение запросов.
— Деревья различных типов имеют одинаковую физическую структуру узлов (т.е. случайным образом создается дерево одного типа, а остальные деревья строятся от первого).
— Алгоритмы Nested Set и Materialized Path были усилены полем level, хранящем уровень вложенности текущего узла в дереве. В частности, можно говорить о том, что это позволяет увеличить, например, производительность выборки наследников узла в MP-дереве более чем в 100 раз! Фактически, без данного поля данные алгоритмы, в некотором смысле, теряют свою привлекательность. Поэтому, можно говорить не столько об их тюнинге при добавлении данного поля, сколько о необходимом условии их функционирования. Таким образом, структура нашей тестовой базы такова:
-- Adjacency List Tree Structure
CREATE TABLE `al_tree` (
`id` bigint(20) NOT NULL auto_increment,
`parent_id` bigint(20) default NULL,
`name` varchar(50) NOT NULL,
PRIMARY KEY (`id`),
KEY `fk_tree_tree` (`parent_id`),
CONSTRAINT `fk_tree_tree` FOREIGN KEY (`parent_id`) REFERENCES `al_tree` (`id`) ON DELETE CASCADE ON UPDATE CASCADE
) ENGINE=InnoDB DEFAULT CHARSET=utf8
-- Nested Set Tree Structure
CREATE TABLE `ns_tree` (
`id` bigint(20) NOT NULL auto_increment,
`name` varchar(50) NOT NULL,
`lft` bigint(20) NOT NULL,
`rgt` bigint(20) NOT NULL,
`level` bigint(20) NOT NULL,
PRIMARY KEY (`id`),
KEY `nslrl_idx` (`lft`,`rgt`,`level`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8
-- Materialized Path Tree Structure
CREATE TABLE `mp_tree` (
`id` bigint(20) NOT NULL auto_increment,
`name` varchar(50) NOT NULL,
`path` varchar(100) NOT NULL,
`level` int(11) NOT NULL,
PRIMARY KEY (`id`),
KEY `mpp_idx` (`path`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8
* This source code was highlighted with Source Code Highlighter.— Для работы с деревьями Nested Set и Materialized Path были написаны функции и процедуры на уровне базы данных для упрощения рутинных операций работы с деревьями. В частности, добавлены функции STRFIND, REPLACE_PATH и процедуры MOVE_NODE_NS, MOVE_NODE_MP, REMOVE_NODE_MP:
STRFIND( str, delimtr)
--
-- Функция ищет количество вхождений символа delimtr в строку str.
-- Фактически эта функция используется для поиска уровня
-- вложенности узла в дереве типа MATERIALIZED PATH.
-- (Кол-во разделителей в пути узла и есть уровень вложенности)
--
-- @param str VARCHAR(255) - исходная строка
-- @param delimtr CHAR(1) - искомый символ
-- @return INT - кол-во вхождений
--
CREATE FUNCTION `STRFIND`(str VARCHAR(255), delimtr CHAR(1)) RETURNS INT
BEGIN
DECLARE _cnt INT;
DECLARE _start INT;
SET _cnt = -1;
SET _start = 1;
WHILE _start > 0 DO
SET _start = LOCATE( delimtr, str);
SET str = SUBSTRING( str, _start + 1);
SET _cnt = _cnt + 1;
END WHILE;
RETURN _cnt;
END
* This source code was highlighted with Source Code Highlighter.REPLACE_PATH( _str, _match, _replace)
--
-- Функция замещает в заданной строке _str
-- подстроку _match на строку _replace,.
-- если _match найдена начиная от начала строки _str
-- Удобна для использования в деревьях типа
-- MATERIALIZED PATH для изменения путей.
--
-- @param _str VARCHAR(255) - исходная строка
-- @param _match VARCHAR(255) - подстрока поиска
-- @param _replace VARCHAR(255) - подстрока замены
-- @return VARCHAR(255) - новыя строка
--
CREATE FUNCTION `REPLACE_PATH`( _str VARCHAR(255), _match VARCHAR(255), _replace VARCHAR(255)) RETURNS VARCHAR(255)
BEGIN
IF _str LIKE CONCAT(_match, '%') THEN
RETURN CONCAT( _replace, SUBSTRING( _str, LENGTH(_match)+1, LENGTH(_str)));
END IF;
RETURN _str;
END
* This source code was highlighted with Source Code Highlighter.Главное отличие приведенной функции от встроенной REPLACE в том, что она гарантированно изменить заданную строку только если совпадение найдено С НАЧАЛА строки и внесет изменения лишь один раз.
MOVE_NODE_NS( node_id, parent_id)
--
-- ПРОЦЕДУРА ПЕРЕМЕЩЕНИЯ ВЕТКИ В ДЕРЕВЕ ТИПА NESTED SET
--
-- @param node_id - идентификатор узла, который следует переместить
-- @param parent_id - идентификатор узла в который следует переместить
--
CREATE PROCEDURE MOVE_NODE_NS( node_id BIGINT, parent_id BIGINT)
BEGIN
DECLARE done INT DEFAULT 0;
DECLARE c_id, c_lft, c_rgt, c_lvl, nWidth, nLeft, nRight, dtKey, nLvl, pRight, addLvl, addKey BIGINT;
DECLARE c_name VARCHAR(50);
-- Создаем курсор который будет хранить всю ветку,
-- которую мы перемещаем
DECLARE mvBranch CURSOR FOR
SELECT id, name, lft - dtKey, rgt - dtKey, level - nLvl FROM ns_tree
WHERE lft >= nLeft AND rgt <= nRight;
DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1;
-- Собираем необходимые данные о выбранной ветке
SELECT rgt - lft + 1, lft, rgt, lft - 1, level INTO nWidth, nLeft, nRight, dtKey, nLvl
FROM ns_tree WHERE id = node_id;
-- Выбираем ветку в курсор
OPEN mvBranch;
-- Удаляем ветку из дерева
DELETE FROM ns_tree WHERE lft BETWEEN nLeft AND nRight;
-- Обновляем ключи в дереве
UPDATE ns_tree SET rgt = rgt - nWidth WHERE rgt > nRight;
UPDATE ns_tree SET lft = lft - nWidth WHERE lft > nRight;
-- выбираем данные о родителе в новом дереве
SELECT rgt, level + 1 INTO pRight, addLvl FROM ns_tree WHERE id = parent_id;
SELECT MAX(node.rgt) INTO addKey FROM ns_tree node, ns_tree parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt AND node.level = parent.level + 1 AND parent.id = parent_id;
-- создаем в дереве пространство, куда будет
-- помещена выбранная ранее ветка
UPDATE ns_tree SET rgt = rgt + nWidth WHERE rgt >= pRight;
UPDATE ns_tree SET lft = lft + nWidth WHERE lft > pRight;
-- преобразуем ветку должным образом и вставляем.
-- в новое дерево
REPEAT
FETCH mvBranch INTO c_id, c_name, c_lft, c_rgt, c_lvl;
IF NOT done THEN
INSERT INTO ns_tree VALUES (c_id, c_name, c_lft + addKey, c_rgt + addKey, c_lvl + addLvl);
END IF;
UNTIL done END REPEAT;
CLOSE mvBranch;
END
* This source code was highlighted with Source Code Highlighter.MOVE_NODE_MP( node_id, parent_id)
--
-- ПРОЦЕДУРА ПЕРЕМЕЩЕНИЯ ВЕТКИ В ДЕРЕВЕ ТИПА MATERIALIZED PATH
--
-- @param node_id - идентификатор узла, который следует переместить
-- @param parent_id - идентификатор узла в который следует переместить
--
CREATE PROCEDURE MOVE_NODE_MP( node_id BIGINT, parent_id BIGINT)
BEGIN
DECLARE done, m_cnt, m_rows, p_cnt, p_rows INT DEFAULT 0;
DECLARE c_id, p_id, n_pos, n_lvl, np_id, np_lvl, new_pos, dt_lvl, ch_id, ch_pos BIGINT;
DECLARE c_path, p_path, n_path, np_path, ch_path, new_path VARCHAR(100);
-- Создаем курсор, в который выбираем ветку,
-- которую следует переместить
DECLARE mvBranch CURSOR FOR
SELECT SQL_CALC_FOUND_ROWS node.id, node.path FROM mp_tree node, mp_tree parent
WHERE node.path LIKE CONCAT(parent.path, '%') AND parent.id = node_id;
-- Создаем курсор, в который вибираем все ветки справа
-- от перемещаемой, находящиеся с ней на одном уровне
DECLARE pChildren CURSOR FOR
SELECT SQL_CALC_FOUND_ROWS node.id, node.path,
CAST(SUBSTRING(REVERSE(node.path), 1, LOCATE('.', node.path)-1) AS UNSIGNED) as pos
FROM mp_tree node, mp_tree parent
WHERE node.path LIKE CONCAT(parent.path, '%') AND node.level = parent.level + 1
AND CAST(SUBSTRING(REVERSE(node.path), 1, LOCATE('.', node.path)-1) AS UNSIGNED) > n_pos
AND parent.id = p_id
ORDER BY pos;
DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1;
-- Собираем необходимые данные
SELECT path, CAST(SUBSTRING(REVERSE(path), 1, LOCATE('.', path)-1) AS UNSIGNED), level INTO n_path, n_pos, n_lvl FROM mp_tree
WHERE id = node_id;
SELECT parent.id, parent.path INTO p_id, p_path FROM mp_tree node, mp_tree parent
WHERE parent.path = SUBSTRING( node.path, 1, (LENGTH(node.path) - LOCATE('.', REVERSE(node.path))))
AND node.id = node_id;
SELECT id, path, level INTO np_id, np_path, np_lvl FROM mp_tree WHERE id = parent_id;
-- Находим разницу в уровнях между уровнями перемещаемых узлов
-- и новым родителем:
SET dt_lvl = np_lvl - n_lvl + 1;
SELECT MAX(CAST(SUBSTRING(REVERSE(node.path), 1, LOCATE('.', node.path)-1) AS UNSIGNED)) + 1
INTO new_pos FROM mp_tree node, mp_tree parent WHERE node.path LIKE CONCAT(parent.path, '%')
AND node.level = parent.level + 1 AND parent.id = parent_id;
-- Перемещаем ветку
OPEN mvBranch;
SELECT FOUND_ROWS() INTO m_rows;
WHILE m_cnt < m_rows DO
FETCH mvBranch INTO c_id, c_path;
UPDATE mp_tree
SET path = REPLACE_PATH(path, n_path, CONCAT(np_path, '.', new_pos)), level = level + dt_lvl WHERE id = c_id;
SET m_cnt = m_cnt + 1;
END WHILE;
CLOSE mvBranch;
-- Исправляем данные о путях в ветке из которой.
-- переместили заданную ветку
OPEN pChildren;
SELECT FOUND_ROWS() INTO p_rows;
WHILE p_cnt < p_rows DO
FETCH pChildren INTO ch_id, ch_path, ch_pos;
UPDATE mp_tree SET path = REPLACE_PATH(path, ch_path, CONCAT(p_path, '.', ch_pos - 1)) WHERE path LIKE CONCAT( ch_path, '%');
SET p_cnt = p_cnt + 1;
END WHILE;
CLOSE pChildren;
END
* This source code was highlighted with Source Code Highlighter.REMOVE_NODE_MP( node_id)
--
-- ПРОЦЕДУРА УДАЛЕНИЯ ВЕТКИ В ДЕРЕВЕ ТИПА MATERIALIZED PATH
--
-- @param node_id - идентификатор узла, который следует удалить
--
CREATE PROCEDURE REMOVE_NODE_MP( node_id BIGINT)
BEGIN
DECLARE n_pos, ch_id, p_id, ch_pos BIGINT;
DECLARE n_path, ch_path, p_path VARCHAR(100);
DECLARE done, p_cnt, p_rows INT DEFAULT 0;
-- Создаем курсор, в который вибираем все ветки справа
-- от перемещаемой, находящиеся с ней на одном уровне
DECLARE pChildren CURSOR FOR
SELECT SQL_CALC_FOUND_ROWS node.id, node.path,
CAST(SUBSTRING(REVERSE(node.path), 1, LOCATE('.', node.path)-1) AS UNSIGNED) as pos
FROM mp_tree node, mp_tree parent
WHERE node.path LIKE CONCAT(parent.path, '%') AND node.level = parent.level + 1
AND CAST(SUBSTRING(REVERSE(node.path), 1, LOCATE('.', node.path)-1) AS UNSIGNED) > n_pos
AND parent.id = p_id
ORDER BY pos;
DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1;
-- Собираем необходимые данные
SELECT path, CAST(SUBSTRING(REVERSE(path), 1, LOCATE('.', path)-1) AS UNSIGNED) INTO n_path, n_pos FROM mp_tree
WHERE id = node_id;
SELECT parent.id, parent.path INTO p_id, p_path FROM mp_tree node, mp_tree parent
WHERE parent.path = SUBSTRING( node.path, 1, (LENGTH(node.path) - LOCATE('.', REVERSE(node.path))))
AND node.id = node_id;
-- Удаляем вветку
DELETE FROM mp_tree WHERE path LIKE CONCAT( n_path, '%');
-- Исправляем данные о путях в ветке из удалили заданную ветку
OPEN pChildren;
SELECT FOUND_ROWS() INTO p_rows;
WHILE p_cnt < p_rows DO
FETCH pChildren INTO ch_id, ch_path, ch_pos;
UPDATE mp_tree SET path = REPLACE_PATH(path, ch_path, CONCAT(p_path, '.', ch_pos - 1)) WHERE path LIKE CONCAT( ch_path, '%');
SET p_cnt = p_cnt + 1;
END WHILE;
CLOSE pChildren;
END
* This source code was highlighted with Source Code Highlighter.Фактически, теперь все тонкости реализации раскрыты, на этом можно остановиться и переходить к вопросам проведения тестов.
Тестирование
Тестирование производилось с помощью самописной консольной программы на следующей конфигурации:
Аппаратное обеспечение:
CPU: Intel® Core(TM)2 Duo CPU E7200 @ 2.53GHz 6Mb 64bit
RAM: 4 Gb
HD: 2 x 250Gb 7200rpm RAID 1
Программное обеспечение:
OS: Debian Linux 2.6.26-1-amd64 (64bit)
PHP-CLI: 5.2.6-5 with Suhosin-Patch 0.9.6.2
MySQL: 5.0.51a, for debian-linux-gnu (x86_64) using readline 5.2
Скажем так, данный аппарат — это сервер, далеко не сильно загруженный на данный момент (около 100 000 достаточно простых HTTP-запросов в сутки), что для такой конфигурации практически не заметно.
Саму же программу вы можете скачать отсюда и попробовать произвести тестирование на своей машине (работает только в Unix-подобной среде). Инструкцию по работе с программой вы найдете в скачанном дистрибутиве в файле README.TXT.
Во время проведения тестирования было выбрано 5 конфигураций деревьев:
- 100 узлов и уровень вложенности 5
- 1000 узлов и уровень вложенности 10
- 10000 узлов и уровень вложенности 20
- 100000 узлов и уровень вложенности 25
- 500000 узлов и уровень вложенности 30
Это деревья, тесты над которыми удалось успешно завершить. Все тесты были завершены чуть меньше чем за 6 часов, при этом основное время, естественно, занял последний тест с деревьями в полмиллиона узлов.
Алгоритм создания деревьев работает таким образом, что закон распределения узлов по дереву примерно следующий:
Где по оси абсцисс — идентификаторы узлов по возрастанию, а по оси ординат — количество узлов в ветках узла с заданным идентификатором.
В связи с таким положением вещей была выбрана следующая схема тестированя. На выборку — итеративная пошаговая схема для проверки функционирования алгоритмов выборки на разных участках дерева. Итерации организованы следующим способом:
id > 1 < 10 - шаг 1 id > 10 < 100 - шаг 10 id > 100 < 1000 - шаг 100 id > 1000 < 10000 - шаг 1000 id > 10000 < 100000 - шаг 10000 id > 100000 - шаг 100000
Это позволяет отследить зависимость функций поиска и выборки от закона распределения узлов.
Для функций изменения схема выбрана несколько иная. Поскольку сами операции изменения для большинства алгоритмов — это достаточно затратные операции, проверять их итеративным способом нет смысла (слишком сильно увеличивается время ожидания завершения тестирования). Поэтому, способ проверки основан на проведении изменений в одном из наибольших узлов, который расположен в начале дерева. К тому же, такой тест будет выполнен единожды. Для того, чтобы обрисовать общую картину и обозначить круг проблем — этого вполне достаточно.
Анализ
Итак, тесты выполнены, данные собраны. Я считаю, что нет смысла вываливать в данной статье все те цифры, которые мы получили в результатах. Тем не менее они доступны для скачивания в виде архива. Так что все желающие могут на них посмотреть воочию.
Куда же более интересным будет показать эмпирически, каковы данные результаты. Давайте посмотрим на что похожи некоторые графики для дерева в 100 000 узлов.
Все ниже посчитано и указанно в секундах.
Рис. 1. Выборка всего дерева целиком
На последующих графиках отображена зависимость флуктуаций функций выборки от поиска на разных участках дерева. Фактически цифрами по оси ординат отмечены шаги, о которых речь шла выше.
Рис. 2. Поиск узла-родителя
Рис. 3. Поиск наследников заданного узла
Рис. 4. Выбор всей ветки заданного узла
Рис. 5. Поиск полного пути от корня к заданному узлу
Далее проиллюстрированы функции изменения, которые проводились над деревьями различных типов.
Рис. 6. Добавление нового узла в дерево
Рис. 7. Перемещение узла
Рис. 8. Удаление узла и всех его потомков из дерева
Обобщенно же, в абсолютных цифрах можно сделать такие выводы:
Списки смежности (Adjacency List):
| Узлов | ALL | PATH | BRANCH | PARENT | CHILDREN | ADD | MOVE | REMOVE |
| 100 | 0,00245 | 0,00016 | 0,00416 | 0,00009 | 0,00011 | 0,00059 | 0,00037 | 0,00009 |
| 1000 | 0,00335 | 0,00025 | 0,03579 | 0,00009 | 0,00011 | 0,00387 | 0,00037 | 0,00009 |
| 10000 | 0,01244 | 0,00058 | 0,38146 | 0,00024 | 0,00036 | 0,03548 | 0,00081 | 0,00011 |
| 100000 | 0,10798 | 0,00105 | 2,55379 | 0,00155 | 0,00138 | 0,06382 | 0,00119 | 0,13931 |
| 500000 | 0,62305 | 0,00124 | 43,91373 | 0,00053 | 0,00209 | 0,05232 | 0,00077 | 0,00041 |
Вложенные множества (Nested Set)
| Узлов | ALL | PATH | BRANCH | PARENT | CHILDREN | ADD | MOVE | REMOVE |
| 100 | 0,00020 | 0,00015 | 0,00020 | 0,00017 | 0,00019 | 0,00367 | 0,02285 | 0,00314 |
| 1000 | 0,00129 | 0,00040 | 0,00093 | 0,00017 | 0,00059 | 0,02593 | 0,19237 | 0,02619 |
| 10000 | 0,01387 | 0,00433 | 0,00825 | 0,01771 | 0,00460 | 0,38235 | 1,37070 | 0,37219 |
| 100000 | 0,17165 | 0,07634 | 0,14261 | 0,17218 | 0,09953 | 101,749 | 213,461 | 59,1912 |
| 500000 | 0,83033 | 0,41670 | 0,62517 | 0,42942 | 0,15318 | 1427,96 | 3712,30 | 1627,97 |
Материализованный путь (Materialized Path)
| Узлов | ALL | PATH | BRANCH | PARENT | CHILDREN | ADD | MOVE | REMOVE |
| 100 | 0,00020 | 0,00017 | 0,00020 | 0,00016 | 0,00019 | 0,00076 | 0,02633 | 0,00059 |
| 1000 | 0,00137 | 0,00069 | 0,00107 | 0,00016 | 0,00071 | 0,00136 | 0,22232 | 0,00136 |
| 10000 | 0,01560 | 0,00608 | 0,01372 | 0,00056 | 0,00737 | 0,00679 | 1,44434 | 0,00801 |
| 100000 | 0,18680 | 0,10466 | 0,17608 | 0,00064 | 0,18546 | 0,92136 | 41,5875 | 1,06560 |
| 500000 | 0,99102 | 0,56412 | 0,59418 | 0,00090 | 0,56800 | 2,02149 | 2950,40 | 1,67124 |
Давайте подумаем, о чем говорят все эти цифры и графики.
Во-первых, все алгоритмы на малых объемах данных (до 10 000 узлов включительно) показали достаточно приемлемую производительность на всех функциях.
Во-вторых, проблемные операции существуют, а именно:
Выборка ветки целиком в дереве AL. Посмотрите, данная операция занимает до 2,5 секунд.
Хотелось бы отметить, что мы немного схитрили в нашем тесте. И вот каким образом. В алгоритме списков смежности (AL) мы реализовали выбор пути методом множественных JOIN'ов таблицы с собой же. Да, результат впечатляющий, особенно в сравнении с результатом выборки ветки рекурсивным способом. Но вряд ли вы выберите такой путь реализации данной функции для своего приложения. Разве что в качестве временной оптимизации. Ведь вам нужно знать максимальный уровень вложенности и не попасть под ограничение СУБД на количество JOIN'ов в одном запросе. Мы же просто провели тест.
Далее у нас возникают проблемы с операциями перемещения узла в алгоритмах NS и MP начиная от 10 000 узлов в дереве (свыше 1 секудны) и далее все становиться ещё хуже — на 100 000 узлах для MP — этот показатель свыше 40 секунд, для NS — почти 4 минуты. На 500 000 узлов цифры и вовсе переходят все рамки разумных пределов — почти 50 минут для MP и свыше 1 часа для NS.
Для NS похожая картина складывается и в остальных операциях изменения. На 10 000 элементов добавление занимает свыше 1,5 минут, а на 500 000 уже свыше 23 минут. С удалением та же проблема — почти минута для 100 000 узлов и свыше 27 минут на 500 000 узлов.
MP ж довольно уверенно себя чувствует и на достаточно больших объемах в операциях удаления и добавления узлов. На деревьях в 100 000 элементов эти операции протекают в пределах 1 секунды, что является более чем положительным результатом. И даже на 500 000 узлах эти операции происходят в пределеах нескольких секунд.
А это значит, что Nested Set следует использовать с фактически статичными деревьями, которые если и изменяются, то крайне редко. При этом, стоит и вовсе задуматься о создании инструмента, который перестраивает дерево по запросу полностью, используя в базовой основе AL-схему (как это делает наша программа генерации произвольных случайных деревьев). Это, как свидетельствуют факты гораздо быстрее, чем рутины самого NS. Либо вообще отказаться от данного алгоритма в пользу Materialized Path.
Заключение
Как мы смогли выяснить, востребованность таких алгоритмов, как Nested Set и Materialized Path обусловлена, в первую очередь, большими объемами данных, где они могут оптимизировать некоторые запросы на поиск и выборку, которые будут критичными для приложения. Или же в условиях высоких нагрузок, где также важна оптимизация запросов. В данном случае речь идет об оптимизации таких операций, как поиск пути и выборка всей ветки в Adjacency List дереве. На практике также стоит говорить и об оптимизации операций поиска соседей, выбора «листьев» всего дерева или в ветке заданного узла, а также других не рассмотренных здесь операций (которые, по сути, для AL сложнореализуемы на уровне SQL-запросов).
На фоне полученных результатов Nested Set качественно уступает Materialized Path, который достаточно уверенно себя чувствует и в операциях на удаление и добавление (а как часто вы перемещаете узлы в ваших деревьях?...). Кроме того, я вижу неплохие перспективы оптимизации данного алгоритма, о чем мы поговорим в следующей статье.
Удачи в девелопменте!
Это кросс-пост оригинальной статьи с моего блога
