Эта версия статьи устарела. Новая версия статьи перенесена по адресу: 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)
...
Типичные задачи, которые встречаются при работе с такими структурами:
- выбрать всех детей элемента
- выбрать всех потомков (детей и их детей) элемента
- выбрать цепочку предков элемента (родитель, его родитель, и так далее)
- переместить элемент (и его потомков) из одной группы в другую
- удалить элемент из таблицы (со всеми потомками)
У каждой записи есть идентификатор — уникальное число, он на схеме написан в скобках (думаю, это ты и так знаешь). Рассмотрим способы хранения таких данных.
Мы добавляем к каждой записи колонку 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/
В этом способы мы так же добавляет поле 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
Идея в том, что мы добавляем к каждой записи поля parent_id, depth, left, right и выстраиваем записи хитрым образом. После этого выборка всех потомков (причем уже отсортированных в нужном порядке) делаетсяпростым запросом вида SELECT WHERE left >= :a AND right <= :b
Минусы: необходимость пересчитывать left/right при вставке записей в середину или удалении, сложное перемещение веток, сложность в понимании.
Плюсы: скорость выборки
Теория: http://www.webscript.ru/stories/04/09/01/8197045
В общем-то, годный вариант для больших таблиц, которые часто выбираются, но меняются нечасто (например, только через админку, где не критична производительность).
Идея в том, что записи в пределах одной ветки нумеруются по порядку и в каждую запись добавляется поле 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
Я в этом не разбираюсь, может кто-то расскажет, какие есть возможности в БД для нативной поддержки деревьев. Вроде что-то такое есть в MSSQL и Oracle. Только хотелось бы услышать, как именно это оптимизируется и какой метод хранения используется, а не общие слова.
Автор пасты http://archive-ipq-co.narod.ru
Стоит добавить только то, что Nested Sets, в первоначальном варианте не использует parent_id. Это уже известный гибрид NS + AL.
P.S.: вообще NS + AL прекрасный вариант для хранения иерархии в БД. Есть сложности, но над ними стоит просто думать, они решаемы. И не забывайте, что читаем всё таки в большинстве случаев чаще, чем записываем.