Обзор паттернов хранения деревьев в реляционных БД / Хабр
Всем привет! Меня зовут Пантелеев Александр и я бэкенд-разработчик в компании Bimeister.
Постараюсь описать исчерпывающе, кратко и понятно суть основных паттернов хранения деревьев в реляционных базах данных. Надеюсь, что статья будет полезна тем, кто до сего момента не сталкивался с такими паттернами, и станет отправной точкой в их понимании.
В этой статье не будет терминов реляционной алгебры или базы данных: таких как атрибут, домен и т. д. Также не будет привязки к какой-либо СУБД, какому-либо SQL или пользовательскому коду.
Всего существует 4 общепринятых паттерна хранения деревьев:
Adjacency List;
Nested Sets;
Closure Table;
Materialized Path.
Кратко рассмотрим каждый из них.
Adjacency List
Описание
Это самый простой и интуитивный вариант хранения. Каждому элементу сопоставляется его свойство — его родительский элемент.
Если родительский элемент не задан, то он считается корневым элементом.
Когда связь сопоставления элемента и родительского элемента хранится отдельно от элемента, Adjacency List можно рассматривать как частный случай Closure Table со связями 1 уровня.
Преимущества
Лёгкость реализации, а также простота вставки, удаления и перемещения элементов в дереве.
Недостатки
Можно получить только непосредственные дочерние элементы. Чтобы получить все дочерние элементы, необходимо выполнить рекурсивный запрос либо производить множественные запросы.
Примеры
Рисунок 1.Элемент | Родительский элемент |
A | — |
B | A |
C | B |
D | C |
E | B |
F | B |
G | A |
H | G |
I | A |
Рассмотрим элемент «B»:
Чтобы получить все его дочерние элементы, нам необходимо выбрать элементы, удовлетворяющие условию:
Родительский элемент равен «B»
Nested Sets
Описание
Каждому элементу сопоставляются свойства: левый и правый индекс, на основе которых будет производиться выборка дочерних элементов.
Также, но необязательно, элемент может дополняться свойством уровень для указания желаемого уровня вложенности выбираемого элемента относительно корня или родительского элемента.
Запрос получения дочерних элементов строится на том факте, что для любого дочернего элемента выполняются условия:
При создании и обновлении дерева левые и правые индексы элементов дерева, при его обходе в глубину, заполняются по определённым правилам.
Преимущества
Возможность получения дочерних элементов любых уровней вложенности с помощью простого одиночного запроса.
Недостатки
При использовании целочисленных типов для левого и правого индекса и уровня необходимо пересчитывать индексы всех связанных элементов в следующих случаях:
при вставке элементов;
при удалении элементов;
при изменении родительского элемента.
Пример
Рисунок 2.Элемент | Левый индекс | Правый индекс | Уровень |
A | 1 | 18 | 0 |
B | 2 | 11 | 1 |
C | 3 | 6 | 2 |
D | 4 | 5 | 3 |
E | 7 | 8 | 2 |
F | 9 | 10 | 2 |
G | 12 | 15 | 1 |
H | 13 | 14 | 2 |
I | 16 | 17 | 1 |
Рассмотрим элемент «B».
Его значения свойств:
левый индекс = 2;
правый индекс = 11;
уровень = 1.
Чтобы получить все его дочерние элементы, нам необходимо выбрать элементы, удовлетворяющие условию:
левый индекс больше 2 И правый индекс меньше 11
Чтобы получить его непосредственные дочерние элементы, нам необходимо добавить к условию ограничение на уровень:
левый индекс больше 2 И правый индекс меньше 11 И уровень = 1
Чтобы получить дочерние элементы вместе с родительским элементом, нам необходимо ослабить условия индексов:
левый индекс больше или равен 2 И правый индекс меньше или равен 11
Closure Table
Описание
Суть этого паттерна заключается в том, что мы сопоставляем каждому элементу множество связей со всеми его дочерними элементами или сопоставляем каждому элементу множество связей со всеми его родительскими элементами.
Также, но необязательно, связь может содержать свойство Уровень. Уровень задаёт расстояние между элементами в дереве.
Если в запросе получения дочерних или родительских элементов по элементу необходимо получать в результате сам элемент, то нужно добавлять связь элемента самого на себя — то есть со значением уровня связи 0.
Преимущества
Возможность получения дочерних элементов любых уровней вложенности с помощью простого одиночного запроса.
Возможность получения родительских элементов любых уровней с их иерархией относительно дочернего элемента с помощью простого одиночного запроса.
Недостатки
При вставке и удалении элементов из дерева, а также при перемещении элементов в дереве необходимо пересчитывать все связи, в которых этот элемент участвует.
Пример
Рисунок 3.Родительский элемент | Дочерний элемент | Уровень |
A | A | 0 |
A | B | 1 |
A | C | 2 |
A | E | 2 |
A | D | 3 |
B | B | 0 |
B | C | 1 |
B | E | 1 |
B | D | 2 |
C | C | 0 |
C | D | 1 |
E | E | 0 |
D | D | 0 |
Рассмотрим элемент «B»:
Чтобы получить все его дочерние элементы, нам необходимо выбрать элементы, удовлетворяющие условию:
родительский элемент равен «B»
Чтобы получить его непосредственные дочерние элементы, нам необходимо добавить к условию ограничение на уровень:
родительский элемент равен «B» И уровень = 1
Чтобы получить дочерние элементы вместе с родительскими, нам необходимо ослабить условия индексов:
родительский элемент равен «B» И уровень = 0
Чтобы получить все его родительские элементы, нам необходимо выбрать элементы, удовлетворяющие условию:
дочерний элемент равен «B»
Materialized Path
Описание
Каждому элементу сопоставляется свойство — его путь, который является последовательностью родительских элементов заданного элемента, отсортированных по уровням.
В общем случае, чтобы формировать гибкие запросы, тип реализации свойства путь должен поддерживать сопоставление по шаблону в каком-либо виде. При денормализации пути в отдельную таблицу получается разновидность Closue Table.
Условия запросов на получение элементов заключается в применении предиката над свойством путь.
Преимущества
Возможность получения дочерних элементов любых уровней вложенности.
Возможность получения родительских элементов любых уровней с их иерархией относительно дочернего элемента.
Лёгкость вставки элемента.
Лёгкость удаления элемента.
Недостатки
Сложность изменения родителя для существующего элемента. Для всех дочерних элементов необходимо пересчитать новый путь.
Операции со свойством путь обычно происходят долго.
Пример
Рисунок 4.Элемент | Путь |
A |
|
B | A |
C | A B |
D | A B C |
E | A B |
Рассмотрим элемент «B»:
Чтобы получить все его дочерние элементы, нам необходимо выбрать элементы, удовлетворяющие условию:
путь содержит «B»
Чтобы получить его непосредственные дочерние элементы, нужно указать позицию, в которой содержится элемент.
В примере путь отсортирован так, что последняя часть пути — это непосредственный родительский элемент:
последняя часть пути равна «B»
Заключение
Мы кратко рассмотрели основные паттерны хранения деревьев в реляционной базе данных. Их основные достоинства и недоставки, а также на примерах рассмотрели основные запросы к ним. В этой статье не были рассмотрены алгоритмы построения и заполнения метаданных деревьев, то есть операции добавления, обновления и удаления элементов.
Паттерн паттерна: дерево стратегии и тактики как патерн-дерево: ailev — LiveJournal
?Anatoly Levenchuk (ailev) wrote,
- IT
length > 0″ ng-click=»catSuggester.reacceptAll()»> CancelОписание проблемы в паттернах соответствует описанию желаемого состояния мира (стратегии) в ДСТ.
Описание сил в паттернах — это, конечно, необходимые посылки (объяснение, почему существует проблема, и нужно что-то делать).
Дискуссия в паттернах — это, конечно, параллельные посылки (объяснение того, как именно действия тактики позволяют достичь желаемого состояния мира) и посылки достаточности (объяснения того, почему больше ничего делать не нужно). Заметим, что дискуссия в паттернах с необходимостью ведет к поминанию других паттернов — так же, как узел ДСТ ведет к поминанию других (нижележащих) узлов.
Паттерны формируют язык, но ведь и ДСТ является не деревом а вовсе направленным графом! Более того, Голдратт демонстрирует одно «дерево» (один набор паттернов), пригодное на все случаи жизни в пределах какого-то типа организаций.
Забавно, забавно. Нужно будет еще над этим подумать.
* * *
Никак не соберусь сделать апдейт PraxOS.ru, в частности:
— подправить понятие организационной системы (свести его к фреймворку)
— подправить набор «мощных идей»
— и (как я сейчас понял) вернуться к дереву стратегии и тактики и паттерной форме как способу систематического изложения материала
Останавливает меня одно: чем больше я знакомлюсь с разными фреймворками, тем больше меня воротит от той формы, в которой они излагаются. Редкая птица перелетит пару тысяч страниц со скучным изложением какой-то онтологии. Интересно, поможет ли явный переход к форме паттернов/дерева стратегии и тактики хоть как-то решить эту проблему.
Ключ к PraxOS, конечно — онтологический подход к разным организационным системам (PraxOS как «система систем», выраженная в более абстрактных терминах, небольшое количество «мощных идей», которые адепт PraxOS сможет узнавать в самых различных фреймворках, и поэтому сможет поддерживать разговор с представителями самых разных учений).
Поэтому нужны какие-то прорывы по форме. А содержание становится все более и более очерчено и понятно.
Subscribe
Менеджмент, предпринимательство и начальничество
Вчера я опубликовал фрагмент курса «Системного менеджмента», где показал соответствие между подролями системного инженера и менеджера (…
Роли в системном менеджменте, понимаемом как системная инженерия организации
Ещё несколько выдержек из курса «Системный менеджмент»: иллюстрация к приёму, облегчающему понимание инженерами менеджмента как варианта системной…
«Распожаризация» и управление работами
Термин «распожаризация» был предложен Юлией Чайковской, которая заметила как вдруг исчезают «пожары» и «авралы» после выполнения рекомендаций курса…
Photo
Hint http://pics.
livejournal.com/igrick/pic/000r1edq
Tree Patterns — Etsy Turkey
Etsy больше не поддерживает старые версии вашего веб-браузера, чтобы обеспечить безопасность пользовательских данных. Пожалуйста, обновите до последней версии.
Воспользуйтесь всеми преимуществами нашего сайта, включив JavaScript.
Найдите что-нибудь памятное, присоединяйтесь к сообществу, делающему добро.
( 1000+ релевантных результатов, с рекламой Продавцы, желающие расширить свой бизнес и привлечь больше заинтересованных покупателей, могут использовать рекламную платформу Etsy для продвижения своих товаров. Вы увидите результаты объявлений, основанные на таких факторах, как релевантность и сумма, которую продавцы платят за клик. Узнать больше. )
Построение с помощью шаблонов: древовидный шаблон
Многие из рассмотренных нами ранее шаблонов проектирования схем подчеркивали, что экономия времени на операциях JOIN является преимуществом.
Данные, к которым обращаются вместе, должны храниться вместе, и некоторое дублирование данных допустимо. Хорошим примером является шаблон проектирования схемы, такой как расширенная ссылка. Однако что, если данные, которые нужно объединить, являются иерархическими? Например, вы хотите определить цепочку отчетности от сотрудника до генерального директора? MongoDB предоставляет оператор $graphLookup для навигации по данным в виде графиков, и это может быть одним из решений. Однако, если вам нужно выполнить много запросов к этой иерархической структуре данных, вы можете применить то же правило хранения вместе данных, к которым осуществляется доступ вместе. Здесь мы можем использовать шаблон дерева.
Шаблон дерева
Существует множество способов представить дерево в устаревшей табличной базе данных. Наиболее распространенные из них для узла в графе, чтобы перечислить своего родителя и для узла, чтобы перечислить своих дочерних элементов. Оба эти представления могут потребовать множественного доступа для построения цепочки узлов.
В качестве альтернативы мы можем сохранить полный путь от узла к вершине иерархии. В этом случае мы в основном будем хранить «родителей» для каждого узла. В табличной базе данных это, скорее всего, будет сделано путем кодирования списка родителей. Подход в MongoDB состоит в том, чтобы просто представить это как массив.
Как видно здесь, в этом представлении есть некоторое дублирование данных. Если информация относительно статична, как в генеалогии, ваши родители и предки не изменятся, что упрощает управление этим массивом. Однако в нашем примере с корпоративной структурой, когда что-то меняется и происходит реструктуризация, вам нужно будет обновить иерархию по мере необходимости. Это все еще небольшие затраты по сравнению с преимуществами, которые вы можете получить, если не будете все время рассчитывать деревья.
Пример использования
Каталоги товаров — еще один очень хороший пример использования шаблона «Дерево». Часто товары относятся к категориям, которые являются частью других категорий. Например, твердотельный накопитель может находиться в разделе
Обратите внимание в документе выше на поле ancestor_categories , которое отслеживает всю иерархию. У нас также есть поле родительская_категория . Дублирование непосредственного родителя в этих двух полях — это передовой метод, который мы разработали после работы со многими клиентами, использующими древовидный шаблон. Включение поля «родительский» часто бывает удобным, особенно если вам нужно поддерживать возможность использования $graphLookup в ваших документах.
Хранение предков в массиве дает возможность создать многоключевой индекс для этих значений.
