Иерархический способ хранения данных

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 комментариев в среднем)

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

Источник

Хранение иерархических данных в плоском виде

На примере хранения дерева комментариев.

Многие наверняка сталкивались с проблемой хранения комментариев, по крайней мере задумывались об этом. Очевидным решением «в лоб» является ссылка на родительский комментарий и, как следствие, рекурсивные вызовы при необходимости отобразить дерево. Современные СУБД поддерживают иерархические запросы, но мне кажется, что это просто перенос проблемы за пределы области видимости, может быть я не прав. В любом случае я писал для Google Application Engine, там разговора об иерархических запросах не идёт вообще.

Мне очень не нравилась перспектива рекурсии и множество мелких запросов к базе, поэтому я стал изобретать какой-то способ получить все комментарии одним простым запросом. И такой способ я довольно быстро «изобрёл». Опросил нескольких знакомых, оказалось, что мало кто на эту тему задумывался, поэтому возьму на себя смелость описать что именно я реализовал.

Итак, главное требование — получить все комментарии сразу в нужном порядке одним запросом. Соответственно, я должен хранить 1) порядок отображения 2) уровень вложенности.

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

Для решения этих двух задач предлагается ввести некое поле, сортировка по которому и даст желаемый порядок следования комментариев.

Ниже небольшое дерево комментариев с примерами хэша.

000000 1 первый комментарий
000100 1.1 ответ на первый комментарий
000101 1.1.1 .
000102 1.1.2 .
000103 1.1.3 .
000104 1.1.4 .
000200 1.2
000300 1.3
010000 2 второй комментарий
010100 2.1 ответ на второй комментарий
010200 2.2 .
020000 3 третий комментарий

Здесь числа типа «1.1.х» это просто часть комментария, а не часть хэша, каким его предлагает классический «материализованный путь».

Предлагаемый хэш стоит в начале каждой строки. В данном случае хэш содержит как бы три двузначных разряда: комментарии нулевого уровня нумеруются в двух первых разрядах, второго в двух вторых и так далее. Мне кажется вычисление этого поля достаточно очевидным из картинки.

Автоматически следуют два ограничения:
1) ограничено количество комментариев на каждом уровне
2) ограничено количество уровней.

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

В действительности я решил что на оба эти ограничения можно закрыть глаза. В случае хранения комментариев и их количество и вложенность вполне можно ограничить. Кроме того я пошёл на небольшую хитрость и «разрешаю» добавлять комментарий на 4-й уровень, но фактически оформляю это как комментарий третьего уровня и так же отображаю. Это сделано чтобы не ограничивать обсуждение двух увлёкшихся комментаторов.

Подробности реализации
Развивая эту идею, от цифрового поля я решил отказаться в пользу текстового. В этом случае я немного теряю в эффективности, но зато я вообще не ограничен в длине хэша. Вместо цифр я пользуюсь символами A-Z и a-x, то есть фактически использую числа с основанием 50 (пятидяситеричная система).

В пятидесятиричной системе я одним разрядом нумерую сразу 50 записей, двумя — уже 2500, для моих целей этого достаточно. Уровней вложенности я использую 8. Оба эти параметра легко меняются, но это можно сделать только один раз, перед началом использования.

С целью вычисления хэша для каждой записи кроме её уровня вложенности я храню ещё и количество дочерних записей, чтобы при добавлении очередной записи не приходилось делать лишних запросов (google data storage, фактически, не умеет выполнять select count(*)).

Вычисление хэша, а, вернее, обновление счётчика дочерних записей необходимо выполнять внутри транзакции. Само добавление комментария можно выполнять уже за рамками транзакции, так как значение хэша уже ни от чего не зависит.

Кстати, просто на всякий случай, я храню ссылку на родительский элемент. Если я вдруг решу всё поменять — у меня будут все исходные данные для восстановления картины.

Выводы
легкий дискомфорт из-за всё-таки наличия ограничений;
некоторые сложности при вычислении этого служебного поля;
моментальная выдача всех результатов одним плоским запросом без лишней нагрузки на сервер.

По-моему стоит иметь ввиду этот или похожий способ хранения иерархических данных, иногда он вполне применим и даёт неплохие результаты.

Например здесь можно посмотреть как это всё выглядит и работает.

Источник

Хранение иерархических структур. Симбиоз «Closure Table» и «Adjacency List»

Когда перед нами встаёт задача хранения и управления иерархическими структурами данных всегда приходится выбирать из довольно ограниченного набора паттернов. Для того чтобы найти наиболее подходящий шаблон необходимо проанализировать особенности каждого способа хранения и обработки данных и оценить их с учётом задачи и специфики используемой СУБД.

Предположим, существует задача, предоставить возможность пользователям сайта оставлять комментарии к публикациям. Комментарии должны иметь древовидную структуру, пользователи должны иметь возможность оставить один или более комментариев к посту, а также отвечать на любые комментарии других пользователей. То есть, нужна система комментариев аналогичная той, что мы можем видеть на Habrahabr. По каким-то причинам, нам не подходят готовые решения, допустим из-за того, что предполагается дополнительная очень сложная бизнес-логика, которая должна быть интегрирована в систему комментариев.

Наша цель – разработать свою реализацию, учитывающую требования нашего приложения.

Что для нас важно?

1. Минимизировать количество запросов к базе данных. В частности, для извлечения ветки комментариев должно быть достаточно одного запроса.
2. Получить высокую производительность, поэтому запросы к базе данных, особенно на чтение, должны быть простыми и выполняться быстро даже при большом объёме данных.
3. Хранить текст комментариев и иерархическую структуру дерева в разных таблицах.
4. Иметь возможность отсортировать извлечённые из базы данных комментарии, чтобы в результате отобразить их в естественном виде, как древовидную иерархическую структуру или, что ещё лучше, сразу извлечь из базы данных отсортированное дерево.
5. Контролировать глубину вложенности комментариев.
6. Гарантировать целостность данных.
7. Учесть специфику MySQL. Как известно, эта СУБД не поддерживает рекурсивные запросы. Рекурсия в этой СУБД возможна только в хранимых процедурах с ограничением вложенности — не более 255 уровней.
8. Требования вполне обоснованные и актуальные для многих проектов.

Итак, рассмотрим известные способы хранения и работы с деревьями. Их не так уж и много:

Детали реализации этих паттернов отлично рассмотрены в презентации Билла Карвина (Bill Karwin).

Особенность метода «Adjacency List», заключается в том, что без поддержки рекурсивных запросов СУБД, извлечь одним простым запросом произвольную часть иерархии невозможно. Поэтому, в контексте использования MySQL этот вариант нас совершенно не устраивает.

Метод «Path Enumeration» (или как его ещё называют «Materialized Path»), очевидно, нам тоже не подходит, ввиду низкой производительности SQL-запросов SELECT, так как предполагается использование оператора LIKE и поиск по шаблонам вида: ‘1/2/3/4%’. Хранение некого множества в виде строки с разделителями, едва ли уместно в мире реляционных баз данных.

Пожалуй, самый интересный паттерн для работы с древовидными структурами – Nested Sets. Он вполне может быть использован для нашей задачи, но его реализация довольно сложная и он не обеспечивает целостность данных. Ошибка при вставке нового элемента в иерархию или при переносе поддерева из одного места в другое может создать большие проблемы. Необходимость пересчёта и изменения значений части левых и правых индексов элементов поддерева при добавлении нового элемента, вне всяких сомнений, является существенным недостатком Nested Sets.

Последний метод «Closure Table», исходя из наших требований, мог бы стать лучшим выбором, если бы не одно «но» — отсутствие простого способа построить отсортированное дерево из получаемого запросом плоского списка связей.

Давайте рассмотрим этот шаблон работы с древовидными структурами данных подробнее.

Схема связей элементов дерева «Closure Table» выглядит следующим образом:

Предположим, у нас есть иерархия комментариев, которая соответствует приведённой выше схеме связей:

Получить список всех элементов нужной нам части дерева можно следующим запросом (извлечём дерево начиная от `commentsTree`.`idAncestor` = 1):

В результате получим:

Всё просто! Но извлечённые строки нужно преобразовать в отсортированную древовидную иерархию. Именно она нам нужна. Увы, данных для преобразования этого множества в нужную нам форму недостаточно.

Как же нам решить эту проблему?

Вариант 1. Заставим СУБД сортировать дерево

Существует довольно оригинальный способ, при помощи которого можно получить из базы данных сразу отсортированную древовидную иерархию, причём всего одним запросом. Известный разработчик Билл Карвин (Bill Karwin) предложил весьма изящный вариант решения задачи извлечения отсортированного дерева:

В результате мы получим, то что нам нужно:

Но, как не сложно заметить, такой способ будет корректно работать только в случае, когда длина идентификаторов idAncestor у всех строк, отвечающих условию запроса, одинаковая. Обратите внимание на следующий фрагмент SQL-запроса: «GROUP_CONCAT(tableStructure.idAncestor ORDER BY tableStructure.level DESC) AS structure». Сортировка строк содержащих множества «12,14,28» и «13,119,12» будет некорректной с точки зрения нашей задачи. То есть, если все идентификаторы в запрашиваемой части дерева одинаковой длинны, то сортировка верная, а в случае если это не так, то структура дерева будет нарушена. Уменьшить количество неправильных сортировок можно, задав начало отсчёта идентификаторов с большого целого числа, например 1000000, указав в SQL запросе при создании таблицы AUTO_INCREMENT=1000000.

Для того чтобы полностью избавится от этой проблемы, можно указать для столбца идентификатора idAncestor параметр ZEROFILL, в этом случае СУБД будет автоматически добавлять атрибут UNSIGNED и идентификаторы буду выглядеть примерно так: 0000000004, 0000000005, 0000000194.

Для некоторых задач, без сомнений, можно использовать этот способ. Но давайте всё-таки постараемся избежать использования двух JOIN’ов при работе с двумя таблицами, функции GROUP_CONCAT(), да ещё и параметра ZEROFILL.

Вариант 2. Симбиоз двух методов «Closure Table» и «Adjacency List»

Давайте ещё раз посмотрим на метод «Closure Table». В плоском списке связей иерархической структуры, который мы получаем всего одним запросом, нам, очевидно, не хватает информации о связи каждого элемента со своим родителем, для того, чтобы мы смогли построить отсортированное дерево. Поэтому, давайте добавим поле idNearestAncestor в таблицу commentsTree и будем сохранять там ссылку на элемент, который является ближайший предком.

Таким образом, мы получили симбиоз двух методов «Closure Table» и «Adjacency List». Теперь формирование правильно отсортированной иерархической структуры — тривиальная задача. И самое главное, мы нашли решение, которое полностью отвечает требованиям.

Следующим запросом мы получим необходимые для построения дерева данные:

Критика «Closure Table»

Шаблон «Closure Table» часто критикуют за то, что необходимо хранить в базе данных связи каждого элемента дерева со всеми его предками, а так же ссылку каждого элемента на самого себя. Чем глубже в иерархии располагается элемент, тем больше записей в таблице необходимо сделать. Очевидно, что добавление новых элементов в конец глубокой древовидной иерархии будет менее эффективным, чем вставка элементов вблизи корня дерева. Кроме этого, стоит отметить, что для хранения деревьев метод Closure Table требует больше места в базе данных, чем любой другой метод.

Для того чтобы объективно оценить значимость этих замечаний, их следует рассматривать в контексте специфики реального проекта. Например, снижение производительности при добавлении нового элемента на двухвостый или тысячный уровень может быть незначительным или некритичным для работы приложения, или же, что ещё более вероятно, такая ситуация вовсе никогда не произойдёт. Как правило, в реальной жизни нет необходимости в иерархических структурах большой вложенности. Кроме этого, в большинстве случаев, принципиальным параметром является скорость извлечения данных, а не записи. Объём дискового пространства, который может потребовать структура дерева едва ли стоит учитывать, так как другие потребители этого ресурса намного более значимые, например логирование посетителей сайта.

Источник