Как хранить иерархичные структуры в СУБД

Задача хранения деревьев в реляционных базах данных имеет свои особенности, прежде всего, связанные со скоростью чтения дерева и сложностью его модификации. Борьба с этими сложностями привела к появлению множества подходов, оформившихся в паттерны. Чтобы не ошибиться в своем выборе и найти реализацию, удовлетворяющую требованиям, важно знать их плюсы и минусы.

Существует четыре основных паттерна хранения «деревьев»: Adjacency List, Materialized Path, Nested Sets, Closure Table. Давайте рассмотрим каждый из них.

Adjacency List

За ним скрывается довольно простая структура данных:

Скорее всего, каждый из вас хоть раз хранил данные в таком виде, но просто не знал, что это целый паттерн, и у него даже есть название. Идея его так же проста, как и вид – у нас есть колонка ParentId, где мы записываем идентификатор вышестоящей записи. С ним легко разобраться даже без документации, поэтому перейдем сразу к плюсам и минусам данного паттерна.

Плюсы:

• Простота реализации – самый главный плюс;
• Легко и быстро можно отредактировать узлы в середине дерева. Нужно только указать новый ParentId. В сравнении с нашими следующими паттернами это на самом деле огромный плюс;
• Также легко добавляются новые дочерние элементы;
• Этот паттерн не занимает лишнего места при хранении данных;
• В плане консистентности этот идентификатор является внешним ключом, то есть мы можем поддерживать ссылочную целостность дерева;
• Из-за наличия внешнего ключа паттерн также хорошо совместим с ORM, так как можно сделать свойство ссылающееся на вышестоящий узел

С этим паттерном все было бы отлично, но у него есть один большой минус:

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

Когда использовать Adjacency List?

Несмотря на весомый минус, он широко используется в программных системах из-за своей простоты. Например, когда дерево маленькое и его можно целиком выгружать в память.

 Materialized Path (Path Enumeration)

Все остальные паттерны были придуманы, чтобы бороться с единственным минусом Adjacency List. Например, Materialized Path предлагает нам добавить строковую колонку Path и хранить в ней полный путь до узла дерева.

При работе с этим паттерном наш основной друг – это оператор «LIKE». Он немного медленнее, чем оператор «=». Если мы ищем данные по паттерну «/1/2/%», то всe не так страшно. Однако, если мы пытаемся найти что-то по паттерну вида «%/2/» или «%/2/%», то СУБД не сможет использовать индекс по этой колонке.

Плюсы:

• Он все еще прост в реализации. Глядя на таблицу, понятно, как ее заполнять;
• Легко добавлять дочерние элементы. Достаточно брать путь родительского элемента и добавлять к нему еще один идентификатор.

Минусы:

• Сложно редактировать узлы в середине дерева. Приходится переписывать пути всех нижестоящих узлов вместо редактирования одной строчки как в случае с Adjacency List;
• Больше нет внешнего ключа, указывающего на вышестоящий узел. В колонке «Path» могут оставаться несуществующие идентификаторы, а значит страдает консистентность;
• Из-за отсутствия внешнего ключа также страдает совместимость с ORM. Из колонки Path не получится сделать свойство, указывающее на вышестоящие узлы дерева.

Как итог, мы получили более высокую скорость выборки, чем у предыдущего паттерна, но редактирование дерева стало сложнее.

Когда использовать Materialized Path?

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

 Nested Sets

Взглянув на него впервые, можно подумать, что Left и Right – это некоторые идентификаторы записей, но на самом деле все устроено сложнее.

Чтобы понять, как заполняются колонки Left и Right нужно представить таблицу в виде вложенных множеств:

Теперь если провести сквозь все эти множества линию и пронумеровать места пересечения, то мы получим значения для колонок Left и Right. Кроме того, эти числа можно вычислить, выполнив вот такой обход дерева:

Колонки Left и Right – это простые числовые колонки. Они компактные, довольно легко индексируются. Запросы будут простыми и быстрыми.

Плюсы:

• Быстрая выборка частей дерева. Даже быстрее, чем в Materialized Path.

Минусы:

• Большие сложности при модификации дерева. И сложность зависит от конкретного места, куда мы вставляем записи. Например, если мы хотим вставить новый элемент где-то в начало по оси (см. визуализацию через множества), то нам придется перезаписать значения Left и Right для всех элементов правее;
• Left и Right могут стать неконсистентными. Это не первичные ключи, а просто числа;
• Не получится сделать внешний ключ на родительские и дочерние элементы.

Есть вариация этого паттерна под названием Nested Intervals, позволяющая минимизировать сложности с модификацией дерева. Left и Right можно сделать дробными числами или инициализировать с запасом: 0, 100, 200, 300 итд. В этом случае вместо того, чтобы переписывать значения для записей правее, мы можем дробить текущие интервалы, не меняя значения в других узлах.

Когда использовать Nested Sets?

Когда критически важна скорость выборки дерева или поддерева или когда не нужно слишком часто редактировать дерево.

Closure Table

Этот паттерн мы активно используем в AirPlan и в некоторых других наших продуктах.Идея этого паттерна состоит в том, чтобы создать для хранения связей между узлами дерева отдельную таблицу. Таблица выглядит следующим образом:

Желтым обведены полезные данные, которые задают структуру дерева. Помимо них есть много служебных данных. Колонки Parent и Child указывают на узлы дерева. Колонка Distance представляет собой длину связи между узлами:

• Записи c Distance = 0 (D0) представляют собой узлы дерева. Они полезны, когда нужно выбрать нижестоящие или вышестоящие узлы, при этом иметь в выборке и узел, от которого идет отсчет. А еще они пригодятся, если мы захотим генерировать остальные служебные связи при помощи cross join SQL запросов, но об этом позже;
• Записи c Distance = 1 (D1) соединяют соседние узлы и задают структуру дерева. Как было сказано выше – это единственная полезная нагрузка;
• Записи c Distance > 1 (D2, D3, D4 итд) нужны, чтобы соединить каждый узел дерева с другим. Именно благодаря этим записям удается достигнуть хорошей скорости выборки данных.

Плюсы:

• Можно за один запрос достать из БД поддерево;
• Отличная совместимость с ORM. У нас есть внешние ключи на родительские и дочерние элементы, причем не только на соседние, а на всю глубину дерева. Это позволяет нам писать запросы, не разбивая его на подзапросы;
• Хорошая производительность. Да, нужно постоянно делать join этой таблицы, но это то, с чем реляционные базы данных неплохо справляются.

Минусы:

• Этот паттерн сложен в реализации и поддержке. Нужна практика, чтобы быстро научится писать запросы, бывает сложно понять, где вышестоящий или нижестоящий узел;
• Нужно генерировать служебные связи;
• Связей может быть очень много. Очень!

Когда использовать Closure Table?

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

Сравнение 4 паттернов

А теперь давайте сравним 4 паттерна, о которых шла речь:

• Adjacency List хорош всем, кроме скорости чтения дерева на глубину более одного уровня.
• Materialized Path и Nested Sets решают проблему со скоростью доступа, но цена этого – существенные сложности при модификации дерева. Кроме того, страдает ссылочная целостность и удобство использования посредствам ORM. 
• Closure Table все так же сложен при модификации дерева, как Materialized Path и Nested Set, в добавок еще и очень требователен к дисковому пространству. Но как же он хорош при использовании с ORM!

Подводя итог, хочется отметить, что нет плохого или хорошего решения. Все зависит от ваших потребностей. Опирайтесь на них при выборе подходящего паттерна.