Дерево с базой sql

How to store a tree in SQL database

I found the discussion in the SQL Anti-patterns very helpfull, as it also focuses on the drawbacks of every implementation.

Also, The slides 48-77 in this presentation reiterate that analisys.

Bottom line, there is no such thing as a generic tree, and no silver bullet for SQL trees. You’ll have to ask yourself about the data, how and how much will they be selected, modified, will branches be moved around, etc, and based on those answers implement a suitable solution.

Well, the easiest way would be for a record to have a ParentID column so that it knows which record is its parent. This is a pretty standard practice. For example, an online store might have a hierarchy of product categories. Each category will have a ParentID. Example: The «Jeans» category in an clothing database might have «Pants» as the parent category. It’s a bit harder if you want a record to indicate which are its children, unless you restrict the number of children. If you want a binary tree, you could have LeftChildID and RightChildID columns. If you allow any number of children, you could have a Children column with IDs delimited by commas (such as 1,4,72,19 ) but that will make querying rather hard. If your database allows for array types in columns, you can probably use an array instead of a delimited string, which would be easy to query — but I’m not sure if MS SQL Server supports that or not.

Other than that, it depends on what kind of data you are modelling, and also what sort of operations you plan to do with this tree.

• Adjacency List is great for finding one level up or down, and being able to edit nodes in the middle.
• Path Enumeration allows you to have unlimited depth and traverse quickly, but makes editing nodes in the middle difficult.
• A Closure Table allows for unlimited depth traversal and also editing middle nodes, but takes more space and is more complex to develop.

There are three basic solutions to store a tree or hierarchal structure in a database.

1. Adjacency list: store each node’s parent
2. Path enumeration: store the entire path for each node in text
3. Closure table: create an additional table with all ancestor/descendant relationships

Each solution has pros and cons:

Adjacency List	Path Enumeration	Closure Table
Storage cost	Low: O(n)	Low: O(n)	High: O(n 2 )
Find first child	Easy/fast	Easy/fast	Easy/fast
Find all children	Hard/slow	Easy/medium	Easy/fast
Find direct parent	Easy/fast	Easy/fast	Easy/fast
Find whole path	Hard/medium	Easy/fast	Easy/fast
Add children	Easy/fast	Easy/fast	Easy/fast
Modify parent	Easy/fast	Hard/slow	Easy/fast
Contradiction prone?	No	Yes	No
Development complexity	Easy	Easy	Hard

1. Adjacency List

CREATE TABLE family_tree_adjacency_list ( PersonId int, Name varchar(255), ParentId int 

This is the simplest tree structure in SQL. Easy to create, easy to conceptualize. Since each node in a tree has only one parent, you can just store each node’s parent and you’ve stored the whole tree. Any nodes with a NULL parent are the top level nodes. This can be a good structure if you don’t need to find the top level ancestors or bottom level descendants of nodes.

• Only 1 table required, no extra storage needs.
• Can easily find any node’s direct child or parent ( SELECT * FROM family_tree WHERE parent_id = 47 ).
• Adding more children is easy
• If you need to modify a node in the middle of the tree to change its parent, no additional changes are needed.

• You can’t find all children at all depths. If you’re using trees to categorize, you’ll either have to do recursive programming to find all the children, or set a limit on number of total descendants. This is complex and slow.
• You can’t find the top level parent. If you need to traverse the tree all the way to the top, you’ll need to use recursive programming (or set a limit on how many fields deep you can go).

2. Path Enumeration

CREATE TABLE family_tree_path_enumeration ( PersonId int, Name varchar(255), Path varchar(255) ) 

This is a good compromise structure. Don’t over-engineer your solution! This solution is easy to implement, easy to conceptualize, and usually decently fast. To find all children of a particular node, you’ll need to use LIKE with a % wildcard, which is slower than = , but that’s usually fine for most cases. The only real downside to this solution is editing the table. Reorganizing a mid-tree node is a very complex endeavor, so if that’s something you do often, don’t use path enumeration.

• Low storage costs still
• Fast to search children and parents, even all the way to the top, regardless of how many levels there are.
• Easy to add children
• Easy to develop

• Modifying a parent requires finding all children and editing each child path as well, which will be an expensive operation. If this is a common task, don’t use Path Enumeration. Messing up could also cause contradictions within the database
• Finding all children of a node is slightly slower, since it uses LIKE % . This could make a difference in a HUGE database.

-- find all sub-children of #1 SELECT * from family_tree_path_enumeration WHERE Path like '%1% 

3. Closure Table

CREATE TABLE family_tree_closure_table ( PersonId int, Name varchar(255) ) CREATE TABLE family_tree_relationships ( AncestorId int, DescendantId int, Depth int -- this is a helper field to make our lives easier when finding parents and children ) 

This solution is a bit more complex, but it will be fast even with large datasets, and still allows for modification without running into problems. The downside here is that development is slightly more complex, and it can use exponentially more storage space (although in practice that’s not usually the case). This can be a good structure if you need to find the top ancestor and bottom descendant, and also need to edit the tree regularly.

• Expandable and fast
• Can quickly find the entire parent path, or all descendant nodes
• Easily add children
• Somewhat easily modify a middle node (depending on what you’re doing, you might need to modify Depth for descendants)

• Complex to develop (needs 2 separate tables)
• Uses more space (needs 2 separate tables)
• You might be over-engineering your solution!

Conclusion

Each table has its tradeoffs. The simple Adjacency List is nice if you want a simple solution that’s easy to reorganize and easy to find one level of parents or children with. A Path Enumeration table is better if you need to find the full path (up or down), but don’t need to edit nodes in the middle of your table very often. If you need to find all nodes in a category, but also need the ability to edit the nodes in the middle, you’ll probably want to use a Closure Table.

Источник

codedokode / Как хранить в БД древовидные структуры (паста).md

Древовидные структуры — это такие структуры, где есть родители и дети, например, каталог товаров:

Бытовая техника (id=1) Телевизоры (id=2) Плазменные (id=3) LCD (id=4) Холодильники (id=5) Маленькие (id=6) Средние (id=7) Большие (id=8) Профессиональная техника (id=9) . 

Типичные задачи, которые встречаются при работе с такими структурами:

• выбрать всех детей элемента
• выбрать всех потомков (детей и их детей) элемента
• выбрать цепочку предков элемента (родитель, его родитель, и так далее)
• переместить элемент (и его потомков) из одной группы в другую
• удалить элемент из таблицы (со всеми потомками)

У каждой записи есть идентификатор — уникальное число, он на схеме написан в скобках (думаю, это ты и так знаешь). Рассмотрим способы хранения таких данных.

1) Добавить колонку parent_id (метод Adjacency List)

Мы добавляем к каждой записи колонку parent_id (и индекс на нее), которая хранит id родительской записи (если родителя нет — NULL). Это самый простой, но самый неэффективный способ. Вот как будет выглядеть вышеприведенное дерево:

Бытовая техника (id=1, parent_id=NULL) Телевизоры (id=2, parent_id=1) Плазменные (id=3,parent_id=2) LCD (id=4,parent_id=2) Холодильники (id=5,parent_id=1) 

Выбрать всех детей просто: SELECT WHERE parent_id = ? , но другие операции требуют выполнения нескольких запросов и на больших деревьях особо неэффективны. Например, выбор всех потомков элемента с идентификатором :id

• выбрать список детей :id ( SELECT WHERE parent_id = :id )
• выбрать список их детей ( SELECT WHERE parent_id IN (:children1) )
• выбрать список детей детей ( SELECT WHERE parent_id IN (:children2) )

И так, пока мы не дойдем до самого младшего ребенка. После этого надо еще отсортировать и объединить результаты в дерево.

Плюсом, впрочем, является быстрая вставка и перемещение веток, которые не требуют никаких дополнительных запросов, и простота реализации. Если можно эффективно кешировать выборки, это в общем-то нормальный и работающий вариант (например, для меню сайта). Это может быть годный вариант для часто меняющихся данных.

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

2) Closure table — усовершенствование предыдущего способа

В этом способы мы так же добавляет поле parent_id , но для оптимизации рекурсивных выборок создаем дополнительную таблицу, в которой храним всех потомков (детей и их детей) и их глубину относительно родителя каждой записи. Поясню. Дополнительная таблица выглядит так:

parent_id child_id depth 1 1 0 // Перечислены все дети записи с 2 1 1 3 2 1 4 2 1 5 1 . 2 2 0 2 3 1 2 4 1 

Чтобы узнать всех потомков записи, мы (в отличие от предыдущего способа), делаем запрос к дополнительной таблице: SELECT child_id FROM closure_table WHERE parent_id = :id , получаем id потомков и выбираем их их основной таблицы: SELECT WHERE id IN (:children) . Если таблицы хранятся в одной БД, запросы можно объединить в один с использованием JOIN.

Данные потом надо будет вручную отсортировать в дерево.

Узнать список предков можно тоже одним запросом к таблице связей: SELECT parent_id FROM closure_table WHERE child_id = :id ORDER BY depth

Минусы метода: нужно поддерживать таблицу связей, она может быть огромной (размер посчитайте сами), при вставке новых записей и при перемещении веток нужны сложные манипуляции. Если таблица часто меняется, это не лучший способ.

Плюсы: относительная простота, быстрота выборок.

Идея в том, что мы добавляем к каждой записи поля parent_id , depth , left , right и выстраиваем записи хитрым образом. После этого выборка всех потомков (причем уже отсортированных в нужном порядке) делаетсяпростым запросом вида SELECT WHERE left >= :a AND right

Минусы: необходимость пересчитывать left / right при вставке записей в середину или удалении, сложное перемещение веток, сложность в понимании.

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

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

Бытовая техника (id=1, number=1, path=1) Телевизоры (id=2, number=1, path=1.1) Плазменные (id=3, number=1, path=1.1.1) LCD (id=4, number=2, path=1.1.2) Холодильники (id=5, number=2, path=1.2) 

При этом способе path хранится в поле вроде TEXT или BINARY, по нему делается индекс. Выбрать всех потомков можно запросом SELECT WHERE path LIKE ‘1.1.%’ ORDER BY path , который использует индекс.

Плюс: записи выбираются уже отсортированными в нужном порядке. Простота решения и скорость выборок высокая (1 запрос). Быстрая вставка.

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

Этот способ отлично подходит для древовидных комментариев.

5) Использовать БД с поддержкой иерархии

Я в этом не разбираюсь, может кто-то расскажет, какие есть возможности в БД для нативной поддержки деревьев. Вроде что-то такое есть в MSSQL и Oracle. Только хотелось бы услышать, как именно это оптимизируется и какой метод хранения используется, а не общие слова.

Источник