Pull to refresh

Full Hierarchy — иерархические структуры в базах данных

Reading time 5 min
Views 16K
Здравствуйте. В этой статье я хотел бы написать про один очень интересный способ хранения иерархических структур в базах данных, не относящийся при этом к общепринятым и общеизвестным трём (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 будет его уровень. Приблизительно так:
#.1
#.1.1
#.1.1.1
#.1.1.2
#.1.2
#.2
#.2.1
#.2.2

Добавляем данные в таблицу

Для того, чтобы их вставить я написал функцию insertTreeRecursive. На каждый элемент нам понадобится два-три запроса. Один — чтобы вставить данные в таблицу `Elements`, один — чтобы взять данные с таблицы `ElementsHierarchy` о родителях и один — чтобы вставить в таблицу `ElementsHierarchy` данные о родителях. Теперь подробнее на примере функции

Думаю, до этого момента ничего тяжёлого:
$elem->setId(Db::execute($query));

Мы вставляем в таблицу `Elements` строку, получаем last_insert_id и присваиваем его текущему элементу. Допустим, ID вставленной записи получилось 37

Если у данного элемента нету родителей, то в базу идет запрос а-ля:
INSERT INTO `ElementsHierarchy`(`ElemID`,`ParentID`,`Level`) VALUES ('ID', NULL, 1)

То есть видно, что элемент на первом уровне от отсутствующего элемента (NULL), то есть родителей не имеет.

Но вот если у элемента есть родитель, то мы получаем список всех родителей родителя (допустим, ID ближайшего родителя — 15). Получится что-то типа такого:
|   ElemID   |  ParentID  |  Level  |
|     15     |    NULL    |    4    |
|     15     |      1     |    3    |
|     15     |      5     |    2    |
|     15     |     10     |    1    |
Мы заменяем у каждой строки ElemID на ID текущего элемента, увеличиваем Level на единицу и дописываем в конец массива еще родите ID=15 и Level = 1.
Получилось у нас следующее:
|   ElemID   |  ParentID  |  Level  |
|     37     |    NULL    |    5    |
|     37     |      1     |    4    |
|     37     |      5     |    3    |
|     37     |     10     |    2    |
|     37     |     15     |    1    |
Вот такую структуру и добавляем в конец таблицы `ElementsHierarchy`. Для нашего $tree, размером в 430 элементов, получилось 1252 строки в таблице иерархии. Чем меньше средний уровень вложенности — чем меньше будет таблица и наоборот. Обратите внимание, что, несмотря на глубину вложенности для вставки одного элемента достаточно 3 простых запроса.

Получаем данные с таблицы

Воспользуемся функцией getRowsByParent для получения данных с таблицы:
$tree = getRowsByParent(2);
print_r($tree);

Мы видим, что у нас вывелись элемент #1.1 и все дерево в подмножестве #1.1.*
Но `ParentID` у нас не ближайшего родителя, а того родителя, по которому мы осуществляли поиск. Потому мы немножко усовершенствуем наш запрос и а также сделаем цикл, который оформит результаты запроса в объект. Вызываем
$tree = getTreeByParent(2);
print_r($tree);
и получаем как раз то, что нам нужно! Одним SELECT'ом!

Хорошо, но давайте посмотрим дальше. А как же производить UPDATE таблиц? Давайте в качестве теста добавим в таблицу `Elements` еще одно поле:
ALTER TABLE `Elements` ADD `Marked` BOOL NOT NULL


И промаркируем все ячейки, которые находятся в глубине дерева 2:
getTreeByParent(2); Смотрим в базу и видим, что всё получилось. Удаление производится точно так же.

Сравнение данного способа и Materialized Path


По предложению хабрасообщества был проведен тест для сравнения скорости выборки из базы данного метода и метода Materialized Path. И у меня есть очень впечатляющие результаты. Я сгенерировал десять 11110 деревьев по 11111 елементов, размером 5*10, то есть 111110 елементов в базе и сделал по ним тесты: Я генерировал 20 случайных ID и искал полное дерево под ними в базе данных. В результате, во всех случаях, Full Hierarchy показывает себя в 5-8 раз лучше, чем Materialized Path (вы можете сами проверить, все исходники тестов — выложены):
pastebin.com/f65b2fb7d — функции, которые использовались во время тестирования.
pastebin.com/f793f7c74 — само тестирование и его результат.
Структура базы `ElementsMP`:
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 комментариев в среднем)

Итог


Возможно, код выше имеет какие-то свои недостатки, но, я уверен, что все недостатки легко исправятся со временем и опытом. Если способ понравится многим, то, думаю, можно будет собраться и написать библиотеку для более удобной работы с ним.

Благодарности

Спасибо DkZ из конфы FreeCR, что нарисовал лого для темы.
Спасибо Kostyan'у, что натолкнул меня на эту идею.
Tags:
Hubs:
+56
Comments 108
Comments Comments 108

Articles