Думаю, некоторые уже видели мою статью на хабре, но хотелось бы еще услышать мнения, комментарии и предложения посетителей php.ru. Здравствуйте. В этой статье я хотел бы написать про один очень интересный способ хранения иерархических структур в базах данных, не относящийся при этом к общепринятым и общеизвестным трём (Adjacency List, Nested Set, Materialized Path). Я не встречал в интернете упоминания о нём, о чём очень удивлен, ведь, по моему мнению, — это лучший и единственный способ хранить иерархические структуры. При разработке console-like форума я воспользовался именно этим способом, о чём ни на грамм не жалею. Это авторская статья и ни одно предложение не было вставлено метотодом копипаста. Суть способа Для каждой иерархической структуры мы создаем две таблицы — таблица с данными и таблица с иерархией. В таблице с данными мы храним то, что нам нужно, единственная ячейка, которая нас здесь интересует — это PRIMARY (`ID`) В таблице иерархии мы храним список всех элементов и их родителей с уровнем к каждому родителю. То есть, если у элемента есть 5 родителей — мы храним 5 записей формата (ElemID, ParentID, Level). Таким образом, для описания самого глубокого элемента понадобится количество элементов, равное уровню вложенности. Вы можете ужаснутся: «О Боже, это ведь так распухнет база!». Но это не так критично — ведь в таблице иерархии всего три int поля, по сравнению с десятком-другим текстовых полей в таблице с данными. То есть, несмотря на количество строк, таблица с иерархией будет достаточно легковесной. Примеры Итак, какой инструментарий для примера я использую: * php 5.3. Важно, чтобы объекты передавались по ссылке, потому 4 версию рекомендую не использовать, или значительно реформировать код * mysql. Используются базовые возможности MySQL, потому версия не так важна. Единственное, что, если вы выберете InnoDB — так, думаю, будет лучше Изначально я выложу код, который далее в статье объясню: Я использую сообственноручно написанный класс для работы с БД (LGPL): http://pastebin.com/f2642074f. Именно в нём меняем параметры подключения. Теперь по поводу самого кода: Определяем, какой элемент мы будем хранить в базе. Это объект класс Elem c свойствами $id, $data, $children, $parent: http://pastebin.com/f78f943d8 Готовые функции, которыми работаем с базой, и далее они будут описаны: http://pastebin.com/f314afb10 Также создадим в нашей базе данных две таблицы: [sql]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;[/sql] Объяснение примеров Сразу же после подключения базовых файлов для того, чтобы получить тестовые данные вызовем функцию generateData, где 4 — количество элементов на уровень, 3 — глубина вложенности. PHP: <? $tree = generateData(4, 3, null); Если сделать print_r ($tree), то можно увидеть, что у нас массив из четырех деревьев по (1 + 4 + 4 * 4 + 4 * 4 * 4) = 85 элементов, то есть 340 элементов вместе. В качестве $elem->data будет его уровень. Приблизительно так: Код (Text): #.1 #.1.1 #.1.1.1 #.1.1.2 #.1.2 #.2 #.2.1 #.2.2 Добавляем данные в таблицу Для того, чтобы их вставить я написал функцию insertTreeRecursive. На каждый элемент нам понадобится два-три запроса. Один — чтобы вставить данные в таблицу `Elements`, один — чтобы взять данные с таблицы `ElementsHierarchy` о родителях и один — чтобы вставить в таблицу `ElementsHierarchy` данные о родителях. Теперь подробнее на примере функции Думаю, до этого момента ничего тяжёлого: PHP: <? $elem->setId(Db::execute($query)); Мы вставляем в таблицу `Elements` строку, получаем last_insert_id и присваиваем его текущему элементу. Допустим, ID вставленной записи получилось 37 Если у данного элемента нету родителей, то в базу идет запрос а-ля: [sql]INSERT INTO `ElementsHierarchy`(`ElemID`,`ParentID`,`Level`) VALUES ('ID', NULL, 1)[/sql] То есть видно, что элемент на первом уровне от отсутствующего элемента (NULL), то есть родителей не имеет. Но вот если у элемента есть родитель, то мы получаем список всех родителей родителя (допустим, ID ближайшего родителя — 15). Получится что-то типа такого: Код (Text): | ElemID | ParentID | Level | | 15 | NULL | 4 | | 15 | 1 | 3 | | 15 | 5 | 2 | | 15 | 10 | 1 | Мы заменяем у каждой строки ElemID на ID текущего элемента, увеличиваем Level на единицу и дописываем в конец массива еще родите ID=15 и Level = 1. Получилось у нас следующее: Код (Text): | ElemID | ParentID | Level | | 37 | NULL | 5 | | 37 | 1 | 4 | | 37 | 5 | 3 | | 37 | 10 | 2 | | 37 | 15 | 1 | Вот такую структуру и добавляем в конец таблицы `ElementsHierarchy`. Для нашего $tree, размером в 430 элементов, получилось 1252 строки в таблице иерархии. Чем меньше средний уровень вложенности — чем меньше будет таблица и наоборот. Обратите внимание, что, несмотря на глубину вложенности для вставки одного элемента достаточно 3 простых запроса. Получаем данные с таблицы Воспользуемся функцией getRowsByParent для получения данных с таблицы: PHP: <? $tree = getRowsByParent(2); print_r($tree); Мы видим, что у нас вывелись элемент #1.1 и все дерево в подмножестве #1.1.* Но `ParentID` у нас не ближайшего родителя, а того родителя, по которому мы осуществляли поиск. Потому мы немножко усовершенствуем наш запрос и а также сделаем цикл, который оформит результаты запроса в объект. Вызываем PHP: <? $tree = getTreeByParent(2); print_r($tree); и получаем как раз то, что нам нужно! Одним SELECT'ом! Хорошо, но давайте посмотрим дальше. А как же производить UPDATE таблиц? Давайте в качестве теста добавим в таблицу `Elements` еще одно поле: [sql]ALTER TABLE `Elements` ADD `Marked` BOOL NOT NULL[/sql] И промаркируем все ячейки, которые находятся в глубине дерева 2: getTreeByParent(2); Смотрим в базу и видим, что всё получилось. Удаление производится точно так же. Сравнение данного способа и Materialized Path По предложению сообщества был проведен тест для сравнения скорости выборки из базы данного метода и метода Materialized Path. И у меня есть очень впечатляющие результаты. Я сгенерировал десять 11110 деревьев по 11111 елементов, размером 5*10, то есть 111110 елементов в базе и сделал по ним тесты: Я генерировал 20 случайных ID и искал полное дерево под ними в базе данных. В результате, во всех случаях, Full Hierarchy показывает себя в 5-8 раз лучше, чем Materialized Path (вы можете сами проверить, все исходники тестов — выложены): http://bin.com/f65b2fb7d — функции, которые использовались во время тестирования. http://pastebin.com/f793f7c74 — само тестирование и его результат. Структура базы `ElementsMP`: [sql]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;[/sql] Более того, база не позволяет сделать поле `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'у, что натолкнул меня на эту идею.