Nested sets или вложенные множества

     Nested sets (Вложенные множества, анг.) — модель хранения древовидной структуры данных в линейном представлении, в нашем случае в таблице базы данных. Проще говоря, когда вы хотите сделать на сайте каталог файлов с категориями, форум или многоуровневые комментарии, вам ничего не остается как использовать одну из подобных моделей. Алгоритмов существует множество, а шире всего при написании сайтов используются adjacency list и nested sets. Оба алгоритма имеют свои плюсы и минусы.
     Adjacency list (Список смежных вершин, анг.) позволяет легко управлять данными в древе и быстро находить родителей и детей узла древа, но при возрастании количества необходимых для получения уровней будет экспоненциально рости количество необходимых sql запросов.
     Nested sets же позволяет получать большие объемы разнообразных данных одним запросом и очень быстро. Его ахиллесовой пятой является большая сложность управления данными в древе. Перемещение или удаление ветвей ресурсоемко и требует переписать множество строк по всему древу.
     Так как я уже пережил этап вопросов «Какая прорграмма поможет создать веб-сайт», то в своем проекте всё разрабатываю сам, с нуля. Именно поэтому я решил использовать nested sets, хотя он и сложнее. Из-за высокой скорости получения данных его использовать логичнее, так как считываний данных гораздо больше чем записей данных в базу. Проблема была в том что на момент этого моего решения я весьма смутно представлял себе работу алгоритма и ещё хуже понимал последовательность запросов для выполнения операций вставки, удаления, копирования и перемещения ветвей в nested sets.
     Я не стану в сотый раз описывать вам теорию работы алгоритма nested sets, прочтите её сами, статья по ссылке весьма хороша. Вместо этого я приведу вам свой класс управления древом данных.
     Код класса class.nestedsets.php выложен на webcodes.ru, как и код парсера условий из одного из предыдущих постов. Класс более менее универсален, за исключением того что все обращения к базе данных идут через обертку, которая реализуется классом class.sql.php для удобства. Я не претендую на идеальность кода и отсутствие ошибок, единственное что могу сказать - класс протестирован и используется.
     Особенность класса в том что он позволяет работать с таблицей которая совмещает оба описанных выше алгоритма работы с древовидными структурами. Это позволяет восстановить более сложный nested sets с помощью adjacency list в случае рассинхронизации ключей в результате какой либо ошибки. Один из методов класса как раз позволяет это сделать. Ниже я рассмотрю каждый из методов (кстати все они коротко описаны в интерфейсе класс в начале файла просто для удобства).

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


     Два последних параметра необязательны и нужны только если ваша таблица так же совмещает два алгоритма. Далее вы можете вызывать методы класса через созданный объект. обратите внимание на то что каждый метод требует передачи названия таблицы в базе, а названия полей передаются один раз при вызове. Это сделано потому, что обычно у одного программиста названия типовых полей в таблицах будут совпадать и нет смысла передавать их каждый раз. Если названия у вас различны — просто пересоздайте объект, удалив старый.
     Если у вас есть таблица с данными но вся информация о ключах отсутствует (например таблица новая или тестовая), то вы можете использовать метод $obj->build('table_name') для создания одномерной структуры данных.
     Если у вас уже есть таблица, данные в которой распределены по алгоритму adjacency list, а вы хотите начать использовать nested sets, или пострадали ключи nested sets в таблице, использующей оба алгоритма — используйте $obj->build_from_al('table_name') для пересоздания структуры nested sets.
     Для проверки правильности структуры nested sets используйте метов $obj->check('table_name'). Он вернет true если таблица правильна и false если ключи или уровни сбиты.
     Далее следуют методы управления данными в древе. Мой класс позволяет вставлять или удалять узлы и ветви, перемещать узлы и ветви и даже копировать ветви в древе.
     Метод $obj->delete_keys('table_name','left_key','right_key') позволяет удалить узел и все его родственные узлы из древа. Ему необходимо передать правый и левый ключи узла. Если ключи заранее неизвесты то для упрощения можно использовать метод $obj->delete_id('table_name','node_id'), который принимает id удаляемого узла.
     Для вставки данных в таблицу использeтся метод $obj->insert_keys('table_name',array('column'=>'value'),'right_key',child) который принимает массив дополнительных значений для неуказанных столбцов данных, правый ключ узла ЗА который будет помещен новый узел а так же булевный параметр, который отмечает, будет ли добавлени элемент в качестве брата (false) или в качестве ребенка (true). Есть так же два упрощенных метода $obj->insert_before_id('table_name', 'node_id', array('column'=>'value'))
и $obj->insert_after_id('table_name', 'node_id', array('column'=>'value'), child) которые вместо правого ключа принимают идентификатор узла. Обратите внимание что новый узел не может быть вставлен в качестве ребенка  методом $obj->insert_before_id().
     Методы перемещения узлов и ветвей:
 $obj->move_before_id('table_name', 'node_id_from', 'node_id_to')
$obj->move_after_id('table_name', 'node_id_from', 'node_id_to', child)
$obj->move_keys('table_name', 'left_key_from', 'right_key_from', 'node_level_from', 'right_key',child)
     Они принимают ключи (идентификаторы) перемещаемого узла и узла, после которого будет расположен перемещаемый узел а так же текущий уровень узла. Перемещаемый узел так же может быть расположен в качестве ребенка или брата.
     Копирование узлов очень похоже на перемещение, за исключением того что оригинал копируемого узла остается не тронутым а идентификаторы скопированного узла и всех его потомков обновляются на незанятые. Вот методы для кпирвоания узлов и ветвей:
$obj->copy_before_id('table_name', 'node_id_from', 'node_id_to')
$obj->copy_after_id('table_name', 'node_id_from', 'node_id_to', child)
$obj->copy_keys('table_name', 'left_key_from', 'right_key_from', 'node_level_from', 'right_key', child)
     Все девять описанный выше методов в качестве id/ключа назначения могут принимать 0. В этом случае перемещаемый, копируемый или добавляемый узел будет помещен в самое начало древа. Так же при указании ноля узел не будет создан в качестве ребенка несмотря на булевный параметр.
     Фух.. пост получился довольно длинным. Надеюсь он будет и не менее полезным.