Профессия — 1С » Способы хранения иерархии в таблицах

Профессия — 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вать значение левого или правого поля на единицу как показано на рисунке:
Схема Nested Set

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

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 в таблицу можно добавить дополнительно поле в котором хранить уровень вложенности элементов. Это поможет уменьшить количество кода при выборке и упорядочивании данных.

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *

   

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