Профессия — 1С

Способы хранения иерархии в таблицах

рубрики: Иерархические структуры | Дата: 9 августа, 2019

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

Существует несколько известных шаблонов, которые позволяют делать такие преобразования. В этой статье кратко рассмотрим эти способы. Для начала просто перечислим их:

Adjacency List (Список смежных вершин)
Nested Set (Вложенное множество)
Matherialized Path (Материализованный путь)
Closure Table (Таблица связей)

А теперь несколько слов о каждом из этих методов.

Adjacency List

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

ID	Name	Parent_ID
0001	Продукты
0002	Овощи	0001
0003	Помидоры	0002
0004	Огурцы	0002
0005	Фрукты	0001
0006	Яблоки	0005
0007	Груши	0005

Собственно именно этот метод и используется в платформе 1С:Предприятие при реализации иерархических справочников.

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

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

Nested Set

Суть этого метода в том, что для каждой записи мы храним левое и правое числовое значение. Назовем эти поля left_value и right_value.
А чтобы понять какие значения должны быть указаны в этих полях для каждой конкретной записи — сделаем обход всех полей дерева слева направо и каждый раз будем увеличbвать значение левого или правого поля на единицу как показано на рисунке:

И теперь наша таблица приобретет вот такой вид:

ID	Name	left_value	right_value
0001	Продукты	1	14
0002	Овощи	2	7
0003	Помидоры	3	6
0004	Огурцы	4	5
0005	Фрукты	8	13
0006	Яблоки	9	12
0007	Груши	10	11

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

Matherialized Path

Здесь идея заключается в хранении полного пути в иерархии для каждого узла. Например вот так:

ID	Name	Path
0001	Продукты	1
0002	Овощи	1.1
0003	Помидоры	1.1.1
0004	Огурцы	1.1.2
0005	Фрукты	1.2
0006	Яблоки	1.2.1
0007	Груши	1.2.2

Такая форма представления информации является интуитивно понятной, т.к. путь напоминает содержание книги. Запросы строить немного сложнее чем при методе Nested Set, и выполняются они дольше, но зато намного проще обстоит ситуация с добавлением и удалением новых узлов. Кроме того полный путь можно представить в виде длинного целого числа, выделив под каждый уровень некоторое количество разрядов, например, 3. И тогда с помощью возведения в степень числа 10 можно упростить запросы для получения данных из дерева. Правда в свою очередь это накладывает ограничения на количество уровней вложенности и на количество элементов на каждом уровне. Но в некоторых ситуациях это может быть полезным. Постараюсь написать отдельныю статью с примером.

Closure Table

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

Заключение

Безусловно, что выбирать способ хранения иерархических структур в таблицах реляционных баз данных необходимо в зависимости от конкретной ситуации. Каждый из методов имеет свои достоинства и недостатки. Кроме того для упрощения получения данных при использовании методов Nested Set и Matherialized Path в таблицу можно добавить дополнительно поле в котором хранить уровень вложенности элементов. Это поможет уменьшить количество кода при выборке и упорядочивании данных.

Добавить комментарий Отменить ответ

2014 - 2024г. Профессия — 1С. Обмен опытом по программированию в 1С