Nested Sets
В очередной раз столкнулся с ситуацией, когда данный алгоритм просто жизненно необходим и снова столкнулся с тем, что из предложенного в Сети нет ничего рабочего под PHP 
класс от Joe Celko грешит ошибками при переносе ветки + адаптация под РНР4 и МуСкул4 меня не особо радует…
класс от Кузьмы Феськова вообще отказывается ветки переносить и уж чересчур привязан к собственным классам по работе с БД и пр. что не очень комфортно
в итоге вспомнив трактовку алгоритма и общие подходы сделал этот класс для работы с Nested Set, который в текущей (30 минутной) версии умеет создавать корень, добавлять/удалять/перемещать ветки и элементы…
Тесты проводил на двух деревьях, с двумя типами перемещения и несколькими типами удаления. Просьба если у кого есть свободное время — ознакомиться и указать тест-кейзы при которых класс себя не оправдывает.
Заранее спасибо 
скачать класс
UPD (2008-01-18):
- добавлена поддержка транзакций
- добавлены методы получения ветки и обртного пути (breadcrumbs)
- добавлено взаимодействие с внешним объектом работы с СУБД (использован личный класс-обертка над mysqli)
Немного теории.
Примечательность алгоритма Nested Sets (вложенные множества) выражается тем, что для выборки ветки или же всего дерева необходим всего один запрос к базе данных. Таким образом мы экономим ресурсы при работе с деревьями на момент выборки (а выборки в 90% случаев происходят гораздо чаще добавлений), хотя и немного теряем в производительности, добавляя новый элемент в структуру (из-за пересчета индексов левого и правого ключей,а так же индексной записи таблицы в БД).
Используя вложенные множества, мы не рискуем оказаться в замкнутой рекурсии, не боимся убить сервер сотнями запросов для получения полной архитектуры дерева и имеем возможность очень гибко управлять свои деревом.
Суть алгоритма состоит в том, что помимо связывания элементов по принципу id - parent_id, мы добавляем так называемые “левый” и “правый” ключи, которые и берут на себя всю основную работу при выборках. об алгоритме создания этих ключей можно почитать тут. Ну а для общего облегчения управлением дерева, в класс я добавил еще и поле level, указывающее глубину элемента в дереве и значительно расширяющее возможности работы алгоритма
Таким образом алгоритм Nested Sets, я считаю наиболее эффективным, если:
- дерево имеет обширную структуру
- выборок гораздо больше, чем изменений и перестановок веток
- производительность приложения должна быть на максимальном возможном уровне
Если вы используете данные классы, то просьба указывать где-то на странице ссылку на эту статью. Спасибо
UPD (03.07.2008): Восстановили файл класса благодаря Александру Власову
Tags: class, DB Design, MySQL, Nested Sets, PHP, ООП, разработка, СУБД, транзакции
Также рекомендую к прочтению:
Январь 29th, 2008 at 16:34
Пожалуйста, выложите ещё раз … ссылка не рабочая! =(
Январь 29th, 2008 at 16:49
перезалил файлик — уже качает
Спасибо за замечание :-[
Январь 29th, 2008 at 16:49
Оперативненько, респект!!!
Январь 29th, 2008 at 16:51
Usage Samples надо?
Хотя думаю там и так вполне самодокументировано
Единственно. Для инициализации объекта Db необходимо сделать изначальную конфигурацию:
$db = Db::getInstance();
$db->connect($options); //смотрим в класс
Январь 29th, 2008 at 17:01
class DBNastedSet extends Collection
^^^^^^^^^^^ не нашел … , что наследуем ?..
Январь 29th, 2008 at 17:06
сорь - выдирал из живого проекта - наследование тут уже не надо
Февраль 18th, 2008 at 19:49
$child_cnt = $this->db->affected_rows;
Что за affected_rows… нету такого в классе
Февраль 19th, 2008 at 10:08
в классе нет, так как сам класс представляет из себя надстройку над mysqli и вызывает собсна его (mysqli) методы и свойства через __call и __get
Февраль 28th, 2008 at 15:55
А чем не подходит Pear::NestedSet?
Февраль 28th, 2008 at 16:01
а) никогда не любил PEAR. Он накладывает дополнительные ограничения на сервера, да и подобный принцип построения архитектуры мне не нра.
б) РНР4
в) в последней версии доступной для скачивания и установки слишком много багов и дополнительных пакетных зависимостей (мой зависит только от одного класса + от него элементарно избавиться)
Февраль 29th, 2008 at 09:37
> Он накладывает дополнительные ограничения на сервера
я не вникал.. А какие ограничения он накладывает?
Февраль 29th, 2008 at 09:55
существование PEAR пакетов + часто необходимость register_globals = on, что противоречит моей религии к примеру
Март 26th, 2008 at 12:54
Из минусов для PEAR NestedSet - приходится создавать отдельное подключение к БД или же передавать параметры созданного соединения, что ни есть хорошо т.к. можно было бы передать объект MDB2 и не давать “лишние данные”. Алексей, в PEAR можно подключать(require) необходимые пакеты как и сам PEAR.class и нет ограничений на сервер в том числе и существования PEAR пакетов - достаточно закачать и подключить один файл PEAR.class. Очень красиво было бы реализовать класс автора на PEAR::DB_DataObject - было бы удобно использовать.
Март 26th, 2008 at 12:59
http://www.phpdoctrine.org/
на сегодняшний день, сказать больше чем по этой ссылке я ничего не могу
Март 26th, 2008 at 15:49
Пожалуй в doctrine всё есть - ORM и Nested set
Март 26th, 2008 at 15:55
вот вот. ZendFramework + Doctrine и любой проект становится реальным за месяц…
Апрель 1st, 2008 at 10:01
http://www.phpdoctrine.org/blog/using-doctrine-zend-framework
Апрель 1st, 2008 at 10:06
у меня со стартом проблем не оказалось
Doctrine + Zend = хорошая связка
Апрель 1st, 2008 at 10:26
Как раз в тему статья появилась “Integrating Zend Framework and Doctrine” через 3 дня после твоего поста
Апрель 1st, 2008 at 10:31
автор не я :)) чесна
за ссылку спасибо
Июль 2nd, 2008 at 19:10
а можно ссылочку обновить, плз. а то 404
спасибо за статью
Июль 15th, 2008 at 23:51
Какашко Ваша Doctrine, памяти выжирает просто немерянно, куча кросс-ссылок внутри, из-за чего освободить ее просто нереально, кучи, просто стада багов - не мудрено 0.10+ версия.
ИМХО самый правильный ORM на пыхе это Propel 1.3 (именно 1.3 а не 1.2 из симфони), там кстати есть и реализация NestedSet, не совсем удачная но за 10 минут дотачивается до совершенства - все остальное, ИМХО, идеально