Небольшое введение. Весь пост написан с оглядкой на MySQL, из-за ее распространенности в web. Конечно, у Oracle возможностей больше, но хостинг с Oracle (или, например, с PostgreSQL) поискать еще надо. Нас же интересует практическое применение в веб-приложениях и обычных сайтах. Для построения сложных систем вообще надо сильно подумать над возможностью применения реляционной БД и рассмотреть другие варианты. Ведь не строчно-табличным видом все БД ограничиваются. Основным посылом к написанию этого поста послужили частые обсуждения темы хранения древовидных структур на различных форумах и комьюнити. Я с удивлением узнал, что многие люди просто не знают методов, отличных от первого, "родитель-дети". Я точно помню, что в начале 90-х видел статью, посвященную этой проблеме, но уже не помню где. Может, вPC Magazine или в Компьютерпресс? Может даже это было в безруковской Софтпанораме. Так или иначе статья я не нашел, может, плохо гуглил.
Родитель-дети
Это самый распространенный и простой паттерн для хранения деревьев. Многочисленные реализации его можно увидеть в различных форумах, системах комментирования и т.д. Суть этого паттерна видно на картинке справа — каждый элемент хранит ссылку (идентификатор) на родителя вкачестве внешнего ключа. На картинке PK — primary key, FK — foreign key. Типичное отношение один ко многим.
Добавление и изменение. Никаких проблем с добавлением и изменением, указываем ID родителя и дело сделано.
Удаление. С удалением сложнее. При простом удалении элемента возникает проблема потерянных детей, поэтому придется в приложении отслеживать удаление элемента и реализовывать логику действий с дочерними элементами удаляемого. Типичные решения:
- не удалять, а помечать как удаленный
- переносить прямых потомков в подчинение к родительскому элементу удаляемого
- переносить всех потомков (прямых и непрямых — т.е. потомков потомков) в корень.
Выборка. Это проблемное место. Возможностей простой выборки немного. По сути этот паттерн дает возможность лишь выбрать всех прямых потомков элемента. Выбор всех потомков, прямых и непрямых, постоение пути от корневого элемента (выбор всех родителей) — реализуются рекрсивными функциями в самом приложении или многочисленными JOIN'ами.
Количество элементов и уровни вложенности — практически бесконечны, зависят от размерности поля ID.
Итог. Паттерн очень удобен для добавления и перемещения элементов. Хорошо подходит для часто изменяемой структуры, часто добавляемых данных, множественного добавления. За эту производительность придется расплачиваться снижением производительности при выборке данных, причем часто весьма значительной. Как я уже написал, многие форумы и системы комментирования построены на этой схеме и владельцы сайтов часто сталкиваются с проблемой производительности именно на выборке данных. Не стоит забывать, что сайт посещают не только люди, но и поисковые машины и для каждого запроса строится дерево.
Для разработчиков, использующих этот паттерн в своих приложениях, будет полезен список частых запросов, составленный по материалам коммьюнити ru_mysql в livejournal. Изображение со схемой этого паттерна я там и взял.
Materialized Path
Несмотря на страшное английское название, это очень распространенный паттерн, наиболее близкий к общепринятой человеческой логике. С этим паттерном мы сталкиваемся постоянно, просто не знаем, что он так называется. Библиотечные списки, URL в браузере и даже Библия. Суть этого паттерна заключатся в том, что каждый элемент хранит полный путь до себя от корня. Напрмер: "УК РФ, часть 22, раздел 8, глава 21, стятья 159, параграф 2".
Добавление и изменение. Сложнее, чем в схеме "Родитель-дети". Для добавления элемента, необходимо получить путь (ID) родительского элемента и добавить к нему свой ID. С изменением сложнее, необходимо пересчитывать ID, (фактически — пути), всех дочерних элементов, прямых и непрямых.
Удаление. С удалением все гораздо интереснее, простое удаление любого элемента не влечет за собой нарушения целостности дерева. Потомки удаленного элемента все еще являются непрямыми потомками родителей удаленного. Дети мертвых родителей — не сироты, у них есть бабушки и дедушки. ;-)
Выборка. Это сильная сторона этого паттерна. Для выборки с помощью простых запросов доступны различные варианты, вызывающие головную боль при использовании метода "родитель-дети". ID всех родителей (полный путь) от корня — вообще без проблем. Все потомки, прямые и непрямые? Пожалуйста.
SELECT * FROM ... WHERE ID LIKE '00010001%'
Это очень удобно для построения различных каталогов — например запрос "первые три подраздела с наибольшим количеством элементов, с учетом вложенных" реализуется гораздо проще, без множества рекурсивных вызовов.
Количество элементов и уровни вложенности. Проектирование этих параметров целиком на совести разработчика. На самом деле бесконечное количество уровней вложенности нужно не так уж часто — если вложенность разделов на сайте приближатся к 20-ти, надо подумать о перепланировке сайта, а не об увеличении уровней.
Реализации этого метода различаются. Поле с ID-путем может быть битовым или текстовым. Текстовое поле может содержать элементы, разделенные каким-нибудь символом, например точка (1.1.2.5) или обратный слэш ('\program files\warez\dowload'). Для простоты работы с текстовым полем обычно используют фиксированное количество символов для каждого уровня, дополненные, например, нулями (0001000100020005 — четвертый уровень, по 4 символа на каждый). Это позволяет просто по длине строки определить уровень, получить ID родителя и т.д. Кроме того, кто сказал, что для нумерации нужно использовать только цифры? Добавив в схему латинский алфавит, получим нумерацию в 36-ричной системе (10 цифр+26 букв).
Итог. Для частых выборок и добавлений, минимальнымх изменений структуры. Необходимо тщательное планирование системы идентификаторов, невозможно применять автоинкрементные поля, т.е. формирование ID ложится на плечи программиста. ID типа VARCHAR(255) тоже не вдохновляет, особенно любителей семантики — ведь текстовое поле, о ужас (!), хранит вовсе не текстовые данные. :-)
Немного сумбурное описание реализации, зачем-то совместно с паттерном "родитель-дети", можно найти на сайте PHPClub.
Nested Sets — вложенные наборы.
Паттерн, несколько более сложный для понимания. Оставим в стороне рассуждения о том, что делали программисты LAMP, когда в школе проходили тему множеств. Будем считать, что они знали, но забыли. Или еще не проходили эту тему. :-) Тем не менее, в популярных скриптах этот метод используется гораздо реже, чем первые два. Идея паттерна аналогична предыдущему — упростить выборку дочерних элементов. Однако в отличие от Materialized Path, элемент в явном виде не хранит информацию о пути. Зато позволяет вычислить путь, основываясь на ID элемента. Для этого элемент хранит не только свой номер, но и ID соседей того же уровня. Если соседа того же уровня нет, то хранится ID элемента уровня выше.
На рисунке выше, элемент 1 знает, что его сосед "слева" — 0, "справа" — 3. У элемента с номером 3 — соседи 1 и 9, у элемента 6 — 5 и 9.
- Сколько элементов, дочерних элементу 3? 9-3=6 (включая сам элемент 3). Или 9-3-1=5 (исключая сам элемент номер 3).
- Каковы родители элемента 7? Все элементы, чьи "соседи слева" меньше 7 (ID) и "соседи справа" больше 7 (ID). Под этот запрос попадают элемент 3 и 6.
Рисунок у меня получился немного не наглядный. "Лево" и "право" получились "верх" и "низ". Зато для людей, мыслящих строками таблиц привычнее. ;-)
Добавление и изменение. Крайне затратные процедуры, требующие пересчета как своего ID, так и номеров соседей, а также пересчет соответствующих полей у соседей и родителей. В среднем пересчет затронет половину (sic!) записей в таблице.
Удаление. Удаление, по идее, тоже затратная процедура, также требущая пересчета границ и ID. Однако это возможно отложить и выполнять фоновым заданием или делать по расписанию. Простое удаление элемента не влечет выпадения из дерева дочерних элементов, они все также попадают в границы родителей и становятся подчиненными родителям родителя. Так, при удалении элемента 6, элементы 7 и 8 будут принадлежать элементу 3.
Выборка. Ради этого и были все навороты. Как написано выше, ID дочерних, прямых и непрямых, элементов (и их количество) можно вообще просто высчитать, не обращаясь к БД. При условии, конечно, что удалялись элементы правильно, с пересчетом границ. Ну и ID элементов должны быть целочисленными. Построение пути до корня также описано выше.
Количество элементов и уровни вложенности. Это также сильная сторона паттерна. Количество элементов и уровней вложенности, как и в первом случае с "родителем-детьми" зависит от реализации целочисленного типа поля у БД и может не заботить проектировщика. Ну, до известных пределов, конечно.
Итог. Подходит для частых выборок и редких добавлений или изменений. Ограничение по вложенности не давит на мозг :-) и не требует предварительных расчетов. Вполне подойдет для различных каталогов. Например, каталогов товаров.
Разработчику лучше всего попробовать написать какой-нибудь более-менее универсальный компонент, класс, библиотеку функций для работы с такой структурой. Время, потраченное на это, несомненно окупится.
Есть еще интересная модификация этого метода, основанная на том, что ID могут быть не целочисленными, а границы не соприкасаться. Ведь если на моем рисунке представить, что у элемента 1 "правая" (нижняя) граница не 3, а 2,3 (две целых три десятых) то у нас остается место для безболезненной вставки элементов. Главное при этом, рассчитывать границы добавляемого элемента с "зазором", т.е. вставляя элемент между 1 и 3, установить ему границы 2,4 слева и 2,8 справа, т.е. все время оставлять некий свободный интервал. При использовании этого метода могут получиться элементы с ID бесконечно малыми :-)
Итого
Конечно, это только наиболее частые решения, наверняка есть методики, о которых я не потрудился узнать. Идеальных решений нет. :-) Реляционные БД (RDBMS) вообще не очень хорошо приспособлены для хранения древовидных структур, но это уже совсем другая тема. Приходится выбирать с учетом планируемых действий и мириться с теми или иными недостатками в каждом конкретном случае. Главное, что есть из чего выбирать.