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