.article | Nested Sets в PostgreSQL

Вопрос посадки деревьев в реляционной СУБД ранее решался мной на MySQL. Работала эта шняга вполне успешно, за исключением нескольких неприятных моментов, а точнее:

  • В корне нарушенный концепт 3х-уровневой архитектуры приложений. Ибо логика хранения данных пересекалась с бизнес логикой приложения.
  • Симуляция трансакций при работе с данными

А потому моя скромная особа перенесла мутированный концепт вложенных множеств в СУБД PostgreSQL в виде User Defined Functions. Работать с данными стало более чем приятно, ибо целостность всех индексов автоматически контролируется СУБД. Более того, все операции по пересчёту индексов и кешей проводятся в трансакционном порядке. Если же к этим массовым приятностям добавить обертку в виде класса на PHP5, которая автоматом отлавливает возможные SQL Exceptions в блоках try{}catch{}, то жизнь вообще начинает казаться маслом.

Мой подход к хранению данных не изменился с тех пор, как я решил работать сразу с несколькими методами индексации данных, а точнее хранить следующие данные для каждой ноды:

  • Родителя
  • Правый и левый индекс
  • Уровень вложенности
  • Порядок сортировки

Обмолвлюсь сразу, что с деревьями я работаю исключительно при навигации сайтов с помощью ЧПУ, а потому не стоит удивляться небольшому отклонению в сторону сохранения путей к нодам с разделителем в виде «/». Дальше всё просто: немного чёрной магии, несколько танцев с бубном и две бутылки пива породили следующий набор User Defined Functions на языке plpgsql для работы с данными:

  • integer add_node(varchar(255), integer)
    Добавит ноду на древо. Первый параметр – это имя ноды. Второй – это ID родителя.
  • integer add_node()
    Это overloader пред-ей функции. Используется для создания корня дерева, ибо вызовет полный add_node(null,null).
  • bool move_tree_after(integer, integer, integer)
    Движение части древа (нода и все её потомки) под нового родителя. Возможно задать порядок вставки под новым родителем, если там уже есть потомки. Первый параметр – ID ноды, которая будет перемещаться. Второй параметр – ID нового родителя. Третий параметр – ID ноды, после которой будет вставлено новое под-древо.
  • bool move_tree(integer, integer)
    Это overloader пред-ей функции. Используется для движения частей древа без указания порядка вставки под новым родителем. Вызовет move_tree_after(integer,integer,null)
  • bool drop_node(integer)
    Функция удалит заданную ноду и всех её потомков. Первый параметр – ID ноды для удаления.
  • text get_path(integer)
    Функция возвращает путь до заданной ноды (включительно). Как разделитель используется “/”. Таким образом путь может выглядеть вот так: «foo/bar/». Данная функция оптимизирована, ибо хранит проработанные пути в поле path_cache. Если же в поле находится значение null, то путь просчитывается снова и сохраняется в поле. Первый параметр – ID ноды, до которой следует просчитать путь.

Далее всё очень приятно и быстро, ибо при вызове функции в СУБД начинается транзакция и проводится запрашиваемая операция. Если запрос не может быть выполнен в связи неверным указанием данных, то будет возвращена SQL ошибка и транзакция будет остановлена. Ошибку можно выловить в PHP и поработать с ней разными очистительными методами. В подробности вдаваться сейчас лень, ибо те, кому интересно, и так всё поймут, а те, кто не понимает – сколько не жуй, всё равно не дано.

Потому просто выкладываю небольшой пакет для работы с деревьями в связке PostgreSQL и PHP5. Код документирован, так что разобраться в нём сможет любой смертный. Для особо одарённых — c классом tree.class.php поставляется Unit Test. Так что дерзайте, дети, а если будут вопросы, то прошу их попробовать решить самим. За исправленные баги воздвигну виртуальный памятник.

 Top

Слова: coding, postgresql, trees, databases

Комментарии Отключены

ELIZIUM

Эм... Вроде просил ответить. :)

23.04.2005 // 16:39 [ ссылка ]

Ответ от Автора

Принято

24.04.2005 // 14:11 [ ссылка ]

Georg

На своем сайте применяю "Рекурсивный Метод", но после прочтения вашей статьи и других

материалов по "Tree Traversal" решил перейти на этот метод так как он более быстрый.

Несколько переделал под себя ваш объект и встала одна проблема. Мой сайт использует ЧПУ и

для выбора статьи главный скрипт анализирует запрошеный URL и выводит из базы MySQL за

один запрос нужную статью.

В вашем объекте есть метод get_path но он позволяет найти статью только по ID.

А как же вы тогда используете ЧПУ? Мы же должны всегда у всех элементов иметь правильное

поле "path_cache". То есть его нужно корректировать при изменениях родителя а вы его

корректируете только в функции get_path. И вообще зачем нужна функция get_path если сайт

на ЧПУ. По моему ситуация когда по ID нужно найти полный путь не встречается если сайт на

ЧПУ, полный путь элемента всегда известен!

Пожалуйста посоветуйте как мне организовать вывод статей по URL?

11.05.2005 // 10:41 [ ссылка ]

Ответ от Автора

это смотря как подойкти к вопросу, у меня же есть поле url, там хранится unix reference для ноды, а далее при запросе определённой ноды происходит примерно такой алгоритм

1) смотрим, есть ли этот адрес в path_cache 2) если есть, берём id узлы и работаем с ним 3) если нет, то проходим по древу до нужного места, если оно находится пишем адрес в path_cache если нет то отдаём 404 страницу

всё просто. Более того, get_path работает только на PostgreSQL $) для мускула эта фенька пока слишком крута.

Для чего нужен path_cache? ну вот, например, выдаю я где-то на сайте список статей, и хотелось бы сразу с ходу до них полный адрес иметь а не ссылку по id. Тем не менее, id мне тоже надо, ибо на нём основывается дофига бизнес логики и связи данных.

Для всего свои резоны.

11.05.2005 // 11:34 [ ссылка ]

Georg

Ваш алгоритм мне понравился!

Посмотрел ваш ответ только 14.05, а до этого придумал свой алгоритм поиска статьи по ЧПУ строке.

1) Сначала разбиваем ЧПУ строку по слешу в массив1.

2) Берем последний элемент в этом масиве, что будет соответствовать полю name таблице базы данных.

3)Ищем в таблице элемент с таким именем, если его нет то сразу выводим 404 страницу.

4)Если найден один элемент то он и есть искомый -> берем его id

5)Если элементов несколько то вычислять полные пути мы будем только у тех элементов у которых поле level совпадает с размерностью массива1 с ЧПУ строками.

6)Теперь нам известны: полные пути ко всем подходящим элементам, находим нужный путем сравнения с искомой строкой.

Достоинства: 1) не нужно хранить полный URL в базе, а только имя элемента

2) не нужно их пересчитывать при добавлении 3) малое число запросов и передаваемых данных от MySQL к PHP

Недостаток один: при большом колличестве одинаковых имен в разных разделах с одним уровнем вложенности возрастает колличество запросов.

Как вам мой!

14.05.2005 // 14:10 [ ссылка ]

Ответ от Автора

Не катит, потому как предаоложим, что есть у меня папка “articles” в ней есть подпаки по темам “php”, “dbms” в каждой из этих ещё подпапки. Плюс ко всему, в основной папке у меня хранятся Symbollic Links на материал из других папок. Внимание, задача: вывести список материала в папке “articles” c ссылками. Имея кеш путей это сдулаю в один запрос. Не имея кеша путей, буду валадаться до потери пульса.

Да таких задач сотни. Практика показывает, что кешировать нужно всё и вся, главное чтобы кеш был «умный» и сам обновлялся когда надо.

Это вообще ведёт к тому, что даже тут, в блоге, все страницы статические ;) так что мне вообще фиолетово сколько уйдёт запросов на её построение %)

14.05.2005 // 14:14 [ ссылка ]

freepk

Я тут подумал вот что у меня получилось.
[ ссылка ]

Все примерно так же, только немножно систематезированней.

Вдруг вам это пригодится.

29.08.2005 // 11:21 [ ссылка ]

Ответ от Автора

Тематично ;) А у меня давно проапрейдено всё уже. Разработка постоянно идёт вперёд. Это важно.

29.08.2005 // 18:54 [ ссылка ]