Дерево паттерн: Обзор паттернов хранения деревьев в реляционных БД / Хабр

Обзор паттернов хранения деревьев в реляционных БД / Хабр

Всем привет! Меня зовут Пантелеев Александр и я бэкенд-разработчик в компании Bimeister.

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

В этой статье не будет терминов реляционной алгебры или базы данных: таких как атрибут, домен и т. д. Также не будет привязки к какой-либо СУБД, какому-либо SQL или пользовательскому коду.

Всего существует 4 общепринятых паттерна хранения деревьев:

• Adjacency List;

• Nested Sets;

• Closure Table;

• Materialized Path.

Кратко рассмотрим каждый из них.

Adjacency List

Описание

Это самый простой и интуитивный вариант хранения. Каждому элементу сопоставляется его свойство — его родительский элемент. Если родительский элемент не задан, то он считается корневым элементом.
Когда связь сопоставления элемента и родительского элемента хранится отдельно от элемента, Adjacency List можно рассматривать как частный случай Closure Table со связями 1 уровня.

Преимущества

Лёгкость реализации, а также простота вставки, удаления и перемещения элементов в дереве.

Недостатки

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

Примеры

Рассмотрим элемент «B»:

Чтобы получить все его дочерние элементы, нам необходимо выбрать элементы, удовлетворяющие условию:

Родительский элемент равен «B»

Nested Sets

Описание

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

Запрос получения дочерних элементов строится на том факте, что для любого дочернего элемента выполняются условия:

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

Преимущества

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

Недостатки

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

• при вставке элементов;

• при удалении элементов;

• при изменении родительского элемента.

Пример

Рассмотрим элемент «B». Его значения свойств:

• левый индекс = 2;

• правый индекс = 11;

• уровень = 1.

Чтобы получить все его дочерние элементы, нам необходимо выбрать элементы, удовлетворяющие условию:

левый индекс больше 2 И правый индекс меньше 11

Чтобы получить его непосредственные дочерние элементы, нам необходимо добавить к условию ограничение на уровень:

левый индекс больше 2 И правый индекс меньше 11 И уровень = 1

Чтобы получить дочерние элементы вместе с родительским элементом, нам необходимо ослабить условия индексов:

левый индекс больше или равен 2 И правый индекс меньше или равен 11

Closure Table

Описание

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

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

Преимущества

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

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

Недостатки

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

Пример

Рассмотрим элемент «B»:

Чтобы получить все его дочерние элементы, нам необходимо выбрать элементы, удовлетворяющие условию:

родительский элемент равен «B»

Чтобы получить его непосредственные дочерние элементы, нам необходимо добавить к условию ограничение на уровень:

родительский элемент равен «B» И уровень = 1

Чтобы получить дочерние элементы вместе с родительскими, нам необходимо ослабить условия индексов:

родительский элемент равен «B» И уровень = 0

Чтобы получить все его родительские элементы, нам необходимо выбрать элементы, удовлетворяющие условию:

дочерний элемент равен «B»

Materialized Path

Описание

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

Условия запросов на получение элементов заключается в применении предиката над свойством путь.  

Преимущества

• Возможность получения дочерних элементов любых уровней вложенности.

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

• Лёгкость вставки элемента.

• Лёгкость удаления элемента.

Недостатки

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

Операции со свойством путь обычно происходят долго.

Пример

Рассмотрим элемент «B»:

Чтобы получить все его дочерние элементы, нам необходимо выбрать элементы, удовлетворяющие условию:

путь содержит «B»

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

последняя часть пути равна «B»

Заключение

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

Компоновщик

/ Паттерны проектирования / Структурные паттерны

Также известен как: Дерево, Composite

// Общий интерфейс компонентов.
interface Graphic is
    method move(x, y)
    method draw()
// Простой компонент.
class Dot implements Graphic is
    field x, y
    constructor Dot(x, y) { ... }
    method move(x, y) is
        this.x += x, this.y += y
    method draw() is
        // Нарисовать точку в координате X, Y.
// Компоненты могут расширять другие компоненты.
class Circle extends Dot is
    field radius
    constructor Circle(x, y, radius) { ... }
    method draw() is
        // Нарисовать окружность в координате X, Y и радиусом R.
// Контейнер содержит операции добавления/удаления дочерних
// компонентов. Все стандартные операции интерфейса компонентов
// он делегирует каждому из дочерних компонентов.
class CompoundGraphic implements Graphic is
    field children: array of Graphic
    method add(child: Graphic) is
        // Добавить компонент в список дочерних.
    method remove(child: Graphic) is
        // Убрать компонент из списка дочерних.
    method move(x, y) is
        foreach (child in children) do
            child.
  move(x, y)
    method draw() is
        // 1. Для каждого дочернего компонента:
        //     - Отрисовать компонент.
        //     - Определить координаты максимальной границы.
        // 2. Нарисовать пунктирную границу вокруг всей области.
// Приложение работает единообразно как с единичными
// компонентами, так и с целыми группами компонентов.
class ImageEditor is
    field all: CompoundGraphic
    method load() is
        all = new CompoundGraphic()
        all.add(new Dot(1, 2))
        all.add(new Circle(5, 3, 10))
        // ...
    // Группировка выбранных компонентов в один сложный
    // компонент.
    method groupSelected(components: array of Graphic) is
        group = new CompoundGraphic()
        foreach (component in components) do
            group.add(component)
            all.remove(component)
        all.add(group)
        // Все компоненты будут отрисованы.
        all.draw()