Здравствуйте. В этой статье я хотел бы написать про один очень интересный способ хранения иерархических структур в базах данных, не относящийся при этом к общепринятым и общеизвестным трём (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 на ID текущего элемента, увеличиваем Level на единицу и дописываем в конец массива еще родите ID=15 и Level = 1.| ElemID | ParentID | Level || 15 | NULL | 4 | | 15 | 1 | 3 | | 15 | 5 | 2 | | 15 | 10 | 1 |
Получилось у нас следующее:
Вот такую структуру и добавляем в конец таблицы `ElementsHierarchy`. Для нашего $tree, размером в 430 элементов, получилось 1252 строки в таблице иерархии. Чем меньше средний уровень вложенности — чем меньше будет таблица и наоборот. Обратите внимание, что, несмотря на глубину вложенности для вставки одного элемента достаточно 3 простых запроса.| ElemID | ParentID | Level || 37 | NULL | 5 | | 37 | 1 | 4 | | 37 | 5 | 3 | | 37 | 10 | 2 | | 37 | 15 | 1 |
Получаем данные с таблицы
Воспользуемся функцией getRowsByParent для получения данных с таблицы:
$tree = getRowsByParent(2);
print_r($tree);Мы видим, что у нас вывелись элемент #1.1 и все дерево в подмножестве #1.1.*
Но `ParentID` у нас не ближайшего родителя, а того родителя, по которому мы осуществляли поиск. Потому мы немножко усовершенствуем наш запрос и а также сделаем цикл, который оформит результаты запроса в объект. Вызываем
$tree = getTreeByParent(2);
print_r($tree);Хорошо, но давайте посмотрим дальше. А как же производить 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'у, что натолкнул меня на эту идею.
