Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Как хранить в БД древовидные структуры

Эта версия статьи устарела. Новая версия статьи перенесена по адресу: https://github.com/codedokode/pasta/blob/master/db/trees.md


Как хранить в БД древовидные структуры

Те, кто знают английский, могут сразу перейти сюда: http://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database

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

Бытовая техника (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, указывющее глубину вложенности, но его надо не забыть обновлять при перемещении ветки.

Теория: http://xpoint.ru/forums/computers/dbms/mysql/thread/34068.xhtml, http://www.opennet.ru/docs/RUS/hierarchical_data/

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

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

parent_id    child_id   depth
1            1          0       // Перечислены все дети записи с id = 1
1            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

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

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

Теория: http://dirtsimple.org/2010/11/simplest-way-to-do-tree-based-queries.html

3) Nested sets

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

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

Плюсы: скорость выборки

Теория: http://www.webscript.ru/stories/04/09/01/8197045

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

4) Materialized Path

Идея в том, что записи в пределах одной ветки нумеруются по порядку и в каждую запись добавляется поле 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

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

Теория: google it

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

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

Автор пасты http://archive-ipq-co.narod.ru

@MelloIocus

This comment has been minimized.

Copy link

@MelloIocus MelloIocus commented Mar 31, 2016

Очень познаватольно, спасибо. И навено react.js использует 4) Materialized Path, для dom элементов очень пожи data-reactid

@codedokode

This comment has been minimized.

Copy link
Owner Author

@codedokode codedokode commented Apr 17, 2016

Да, возможно, что там используют похожий способ формирования id, но MPath это все же паттерн хранения данных в БД (а реакт - JS библиотека для реализации View), так что не говорите такие вещи на собеседовании!

@lincaseidhe

This comment has been minimized.

Copy link

@lincaseidhe lincaseidhe commented Jan 3, 2018

Отличная статья, как раз ищу способ хранения деревьев в mysql. Пробежался быстро по теории nested sets - там получается пересчет индексов даже при вставке в конец? или пересчитывается только последний индекс у первой записи? Я не силен в mysql, но кажется этот способ то что мне нужно. Вот только смущает пересчет индексов...

@aariabov

This comment has been minimized.

Copy link

@aariabov aariabov commented May 29, 2018

По поводу 5ого пункта: используется метод Adjacency List, только некоторые СУБД, такие как MSSQL и Oracle, умеют выполнять рекурсивные запросы.

@codedokode

This comment has been minimized.

Copy link
Owner Author

@codedokode codedokode commented Jun 22, 2018

Увы, мне не приходят уведомления о комментариях тут, потому я о них даже не знаю, пока не наткнусь.

@lincaseidhe Да, в Nested Sets надо при любых изменениях пересчитывать цифры. То есть вставки, удаления и перестановки тут довольно дорогие. Это обычно используется для случаев, когда таблица не слишком огромная и редактируется нечасто, например, через админку.

@aariabov Спасибо за информацию.

@brussens

This comment has been minimized.

Copy link

@brussens brussens commented Jan 15, 2019

Стоит добавить только то, что Nested Sets, в первоначальном варианте не использует parent_id. Это уже известный гибрид NS + AL.
P.S.: вообще NS + AL прекрасный вариант для хранения иерархии в БД. Есть сложности, но над ними стоит просто думать, они решаемы. И не забывайте, что читаем всё таки в большинстве случаев чаще, чем записываем.

@bagau

This comment has been minimized.

Copy link

@bagau bagau commented Mar 19, 2019

У метода Materialized Path есть один момент, связанный с порядком получения. Если сортировать по строке то следующие Paths 1.1, 1.2, 1.10 будут отсортированы при получении вот так: 1.1, 1.10, 1.2. Решением пока вижу только писать path начиная с 1000, то есть 1000, 1001. (Можно и 100, а может нужно будет и 10000, в зависимости от планируемого количества элементов).
Для вложенных это будет 1000.1001, 1000.1002, 1000.1010.
Может быть есть более элегантное решение...

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.