- Иерархичный способ организации данных
- 3.1.2. Операции над данными, определенные в иерархической модели:
- 3.1.3. Ограничения целостности.
- Full Hierarchy — иерархические структуры в базах данных
- Суть способа
- Примеры
- Объяснение примеров
- Сравнение данного способа и Materialized Path
- Иерархические структуры данных и производительность
- Введение
- Подготовка
- Тестирование
- Анализ
- Заключение
Иерархичный способ организации данных
При графическом изображении групповые отношения изображают дугами ориентированного графа, а типы записей — вершинами (диаграмма Бахмана).
Для групповых отношений в иерархической модели обеспечивается автоматический режим включения и фиксированное членство . Это означает, что для запоминания любой некорневой записи в БД должна существовать ее родительская запись (подробнее о режимах включения и исключения записей сказано в параграфе о сетевой модели). При удалении родительской записи автоматически удаляются все подчиненные.
Рассмотрим следующую модель данных предприятия (см. рис. 3.1 ): предприятие состоит из отделов, в которых работают сотрудники. В каждом отделе может работать несколько сотрудников, но сотрудник не может работать более чем в одном отделе.
Поэтому, для информационной системы управления персоналом необходимо создать групповое отношение, состоящее из родительской записи ОТДЕЛ (НАИМЕНОВАНИЕ_ОТДЕЛА, ЧИСЛО_РАБОТНИКОВ) и дочерней записи СОТРУДНИК (ФАМИЛИЯ, ДОЛЖНОСТЬ, ОКЛАД). Это отношение показано на рис. (а) (Для простоты полагается, что имеются только две дочерние записи).
Для автоматизации учета контрактов с заказчиками необходимо создание еще одной иерархической структуры : заказчик — контракты с ним — сотрудники, задействованные в работе над контрактом. Это дерево будет включать записи ЗАКАЗЧИК(НАИМЕНОВАНИЕ_ЗАКАЗЧИКА, АДРЕС), КОНТРАКТ(НОМЕР, ДАТА,СУММА), ИСПОЛНИТЕЛЬ (ФАМИЛИЯ, ДОЛЖНОСТЬ, НАИМЕНОВАНИЕ_ОТДЕЛА) (рис. (b) ) . Рис. 3.1
Из этого примера видны недостатки иерархических БД:
- Частично дублируется информация между записями СОТРУДНИК и ИСПОЛНИТЕЛЬ (такие записи называют парными), причем в иерархической модели данных не предусмотрена поддержка соответствия между парными записями.
- Иерархическая модель реализует отношение между исходной и дочерней записью по схеме 1:N , то есть одной родительской записи может соответствовать любое число дочерних. Допустим теперь, что исполнитель может принимать участие более чем в одном контракте (т.е. возникает связь типа M:N ). В этом случае в базу данных необходимо ввести еще одно групповое отношение, в котором ИСПОЛНИТЕЛЬ будет являться исходной записью, а КОНТРАКТ — дочерней (рис. (c) ). Таким образом, мы опять вынуждены дублировать информацию.
3.1.2. Операции над данными, определенные в иерархической модели:
- ДОБАВИТЬ в базу данных новую запись. Для корневой записи обязательно формирование значения ключа.
- ИЗМЕНИТЬ значение данных предварительно извлеченной записи. Ключевые данные не должны подвергаться изменениям.
- УДАЛИТЬ некоторую запись и все подчиненные ей записи.
- ИЗВЛЕЧЬ :
- извлечь корневую запись по ключевому значению, допускается также последовательный просмотр корневых записей
- извлечь следующую запись (следующая запись извлекается в порядке левостороннего обхода дерева)
В операции ИЗВЛЕЧЬ допускается задание условий выборки (например, извлечь сотрудников с окладом более 1 тысячи руб.)
Как видим, все операции изменения применяются только к одной «текущей» записи (которая предварительно извлечена из базы данных). Такой подход к манипулированию данных получил название «навигационного».
3.1.3. Ограничения целостности.
Поддерживается только целостность связей между владельцами и членами группового отношения (никакой потомок не может существовать без предка). Как уже отмечалось, не обеспечивается автоматическое поддержание соответствия парных записей, входящих в разлные иерархии.
Бойко В.В., Савинков В.М. Проектирование баз данных информационных систем. -М.:»Финансы и статистика»,1989.
Источник
Full Hierarchy — иерархические структуры в базах данных
Здравствуйте. В этой статье я хотел бы написать про один очень интересный способ хранения иерархических структур в базах данных, не относящийся при этом к общепринятым и общеизвестным трём (Adjacency List, Nested Set, Materialized Path). Я не встречал в интернете упоминания о нём, о чём очень удивлен, ведь, по моему мнению, — это лучший и единственный способ хранить иерархические структуры. При разработке console-like форума я воспользовался именно этим способом, о чём ни на грамм не жалею. Это авторская статья и ни одно предложение не было вставлено метотодом копипаста.
Вполне возможно, что этот способ известен и называется он иначе. Если так — с удовольствием узнаю, как она называется на самом деле.
Имхо, этот способ больше всего похож на Materialized Path, с незначительным оттенком Adjacency List. По сравнению с Adjacency List он слегка денормализует базу данных, но с теми преимуществами, что он даёт — это не играет значительной роли.
Суть способа
Для каждой иерархической структуры мы создаем две таблицы — таблица с данными и таблица с иерархией. В таблице с данными мы храним то, что нам нужно, единственная ячейка, которая нас здесь интересует — это PRIMARY (`ID`)
В таблице иерархии мы храним список всех элементов и их родителей с уровнем к каждому родителю. То есть, если у элемента есть 5 родителей — мы храним 5 записей формата (ElemID, ParentID, Level). Таким образом, для описания самого глубокого элемента понадобится количество элементов, равное уровню вложенности.
Вы можете ужаснутся: «О Боже, это ведь так распухнет база!». Но это не так критично — ведь в таблице иерархии всего три int поля, по сравнению с десятком-другим текстовых полей в таблице с данными. То есть, несмотря на количество строк, таблица с иерархией будет достаточно легковесной.
Примеры
Итак, какой инструментарий для примера я использую:
- php 5.3. Важно, чтобы объекты передавались по ссылке, потому 4 версию рекомендую не использовать, или значительно реформировать код
- mysql. Используются базовые возможности MySQL, потому версия не так важна. Единственное, что, если вы выберете InnoDB — так, думаю, будет лучше
Изначально я выложу код, который далее в статье объясню:
Я использую сообственноручно написанный класс для работы с БД (LGPL): pastebin.com/f2642074f. Именно в нём меняем параметры подключения.
Теперь по поводу самого кода:
Определяем, какой элемент мы будем хранить в базе. Это объект класс Elem c свойствами $id, $data, $children, $parent: pastebin.com/f78f943d8
Готовые функции, которыми работаем с базой, и далее они будут описаны: pastebin.com/f314afb10
Также создадим в нашей базе данных две таблицы:
CREATE TABLE `Elements` (
`ID` int (11) NOT NULL AUTO_INCREMENT,
` Data ` varchar (64) NOT NULL ,
PRIMARY KEY (`ID`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;
CREATE TABLE `ElementsHierarchy` (
`ElemID` int (11) NOT NULL ,
`ParentID` int (11) DEFAULT NULL ,
` Level ` int (11) NOT NULL ,
KEY `ElemID` (`ElemID`),
KEY `ParentID` (`ParentID`),
KEY ` Level ` (` Level `)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;
* This source code was highlighted with Source Code Highlighter .
Объяснение примеров
Сразу же после подключения базовых файлов для того, чтобы получить тестовые данные вызовем функцию generateData, где 4 — количество элементов на уровень, 3 — глубина вложенности.
$tree = generateData(4, 3, null);
Справа вы можете видеть один из 4 элементов, которые теперь находятся у нас в массиве $tree
Если сделать print_r ($tree), то можно увидеть, что у нас массив из четырех деревьев по (1 + 4 + 4 * 4 + 4 * 4 * 4) = 85 элементов, то есть 340 элементов вместе. В качестве $elem->data будет его уровень. Приблизительно так:
Добавляем данные в таблицу
Для того, чтобы их вставить я написал функцию insertTreeRecursive. На каждый элемент нам понадобится два-три запроса. Один — чтобы вставить данные в таблицу `Elements`, один — чтобы взять данные с таблицы `ElementsHierarchy` о родителях и один — чтобы вставить в таблицу `ElementsHierarchy` данные о родителях. Теперь подробнее на примере функции
Думаю, до этого момента ничего тяжёлого:
Мы вставляем в таблицу `Elements` строку, получаем last_insert_id и присваиваем его текущему элементу. Допустим, ID вставленной записи получилось 37
Если у данного элемента нету родителей, то в базу идет запрос а-ля:
INSERT INTO `ElementsHierarchy`(`ElemID`,`ParentID`,`Level`) VALUES (‘ID’, NULL, 1)
То есть видно, что элемент на первом уровне от отсутствующего элемента (NULL), то есть родителей не имеет.
Но вот если у элемента есть родитель, то мы получаем список всех родителей родителя (допустим, ID ближайшего родителя — 15). Получится что-то типа такого:
Вот такую структуру и добавляем в конец таблицы `ElementsHierarchy`. Для нашего $tree, размером в 430 элементов, получилось 1252 строки в таблице иерархии. Чем меньше средний уровень вложенности — чем меньше будет таблица и наоборот. Обратите внимание, что, несмотря на глубину вложенности для вставки одного элемента достаточно 3 простых запроса.
Получаем данные с таблицы
и получаем как раз то, что нам нужно! Одним SELECT’ом!
Хорошо, но давайте посмотрим дальше. А как же производить UPDATE таблиц? Давайте в качестве теста добавим в таблицу `Elements` еще одно поле:
ALTER TABLE `Elements` ADD `Marked` BOOL NOT NULL
И промаркируем все ячейки, которые находятся в глубине дерева 2:
getTreeByParent(2); Смотрим в базу и видим, что всё получилось. Удаление производится точно так же.
Сравнение данного способа и Materialized Path
CREATE TABLE `ElementsMP` (
`ID` int (11) NOT NULL AUTO_INCREMENT,
` Data ` varchar (64) NOT NULL ,
` Path ` varchar (1000) CHARACTER SET latin1 COLLATE latin1_bin DEFAULT NULL ,
PRIMARY KEY (`ID`),
KEY ` Path ` (` Path `)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;* This source code was highlighted with Source Code Highlighter .
Более того, база не позволяет сделать поле `Path` длиннее 1000 символов (#1071 — Specified key was too long; max key length is 1000 bytes), что значит, что, если у нас средняя длина ID будет 4 символов мы не сможем делать деревья глубже 1000/(4+1), то есть самое глубокое возможное дерево в таком случае — 200 элементов. и 166 при средней длине ключа 5 цифр (если на сайте более 50000 комментариев в среднем)
Возможно, код выше имеет какие-то свои недостатки, но, я уверен, что все недостатки легко исправятся со временем и опытом. Если способ понравится многим, то, думаю, можно будет собраться и написать библиотеку для более удобной работы с ним.
Источник
Иерархические структуры данных и производительность
Введение
В своей предыдущей статье я дал краткий обзор основных моделей хранения иерархических структур в реляционных БД. Как и положено тому быть, у многих читателей стал вопрос ребром о производительности представленных алгоритмов.
В данной статье я постараюсь приоткрыть завесу над этим животрепещущим вопросом, а в следующей обещаю коснуться вопросов оптимизации и поисков нестандартных решений.
Подготовка
Итак, тестирование. Как и любое другое тестирование, наше также требует определенных действий по подготовке, анализу, выработке целей и плана действий.
Фактически, целью является проведение серии стресс-тестов различных алгоритмов на различных объемах данных. Неплохо было бы также прогнать тесты на нескольких различных аппаратных платформах, но, увы, автору это не по силам (время и деньги — всему виной).
Естественно, хорошо было бы провести тесты наиболее важных и значимых операций, которые как правило выполняются над теми или иными деревьями. После достаточно продолжительных размышлений было решено остановиться на таком списке тестируемых операций:
- Выборка всего дерева целиком
- Выборка пути к заданному узлу
- Выборка ветки заданного узла
- Поиск родителя заданного узла
- Поиск наследников заданного узла
- Добавление нового узла в конец заданного родительского узла
- Перемещение узла (или же, другими словами — смена родителя)
- Удаление узла (и всей ветки под ним)
Стоит отметить, что данные операции мы приближаем к боевым условиям, т.е. входными данными для нас будут идентификаторы узлов и их родителей. Это позволит не привязываться к конкретным реализациям каждого из алгоритмов.
Далее оговорим, что нас интересует производительность чистого 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 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 >
— Выбираем ветку в курсор
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 >
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 >
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 >
— Находим разницу в уровнях между уровнями перемещаемых узлов
— и новым родителем:
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 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 > SET m_cnt = m_cnt + 1;
END WHILE ;
CLOSE mvBranch;
— Исправляем данные о путях в ветке из которой.
— переместили заданную ветку
OPEN pChildren;
SELECT FOUND_ROWS() INTO p_rows;
WHILE p_cnt 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 >
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 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 часов, при этом основное время, естественно, занял последний тест с деревьями в полмиллиона узлов.
Алгоритм создания деревьев работает таким образом, что закон распределения узлов по дереву примерно следующий:
Где по оси абсцисс — идентификаторы узлов по возрастанию, а по оси ординат — количество узлов в ветках узла с заданным идентификатором.
В связи с таким положением вещей была выбрана следующая схема тестированя. На выборку — итеративная пошаговая схема для проверки функционирования алгоритмов выборки на разных участках дерева. Итерации организованы следующим способом:
Это позволяет отследить зависимость функций поиска и выборки от закона распределения узлов.
Для функций изменения схема выбрана несколько иная. Поскольку сами операции изменения для большинства алгоритмов — это достаточно затратные операции, проверять их итеративным способом нет смысла (слишком сильно увеличивается время ожидания завершения тестирования). Поэтому, способ проверки основан на проведении изменений в одном из наибольших узлов, который расположен в начале дерева. К тому же, такой тест будет выполнен единожды. Для того, чтобы обрисовать общую картину и обозначить круг проблем — этого вполне достаточно.
Анализ
Итак, тесты выполнены, данные собраны. Я считаю, что нет смысла вываливать в данной статье все те цифры, которые мы получили в результатах. Тем не менее они доступны для скачивания в виде архива. Так что все желающие могут на них посмотреть воочию.
Куда же более интересным будет показать эмпирически, каковы данные результаты. Давайте посмотрим на что похожи некоторые графики для дерева в 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, который достаточно уверенно себя чувствует и в операциях на удаление и добавление (а как часто вы перемещаете узлы в ваших деревьях. ). Кроме того, я вижу неплохие перспективы оптимизации данного алгоритма, о чем мы поговорим в следующей статье.
Источник
