Nested sets - множественные rootы или оперирование level

лично я использую множество корней, для оптимизации работы скрипта при удалении/вставке дочерних нод. Но эта структура базы будет зависеть от конкретной архитектуры модели системы, то есть, у меня нет абстрактных универсальных хэлперов, которые рулят количеством рутовых нод (так как подобное может только негативно повлиять на скорость работы), а руты выбираются руками и заносятся конфиги, далее, всё зависит от абстракции уровня данных - это могут быть датамапперы с некоторой поддержкой ОРМ для всего конкретного дерева, начинающегося с этой корневой ноды, их совокупность (когда нужно осуществить многие ко многим или аналоги) или просто врапперы, типа актив-тэйбл, но только с поддержкой методов по работе с сабжем.

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

зы: ну а лэйвл использую всегда, и разумеется ключи по всему ) Там, где можно выкрутиться без лэйвла при использовании nested sets (приемлемая производительность при пересчётах индексов нод, отсутствие необходимости выгребать предка предка 2й с боку ноды, которая сестринская по отношению к заданной ;) и т.д.) надобность в нестед сетс, имхо, отпадает, достаточно просто parent, child, level

Ну я решил выступить в роли одного из скрипткиддис :) - просто есть несколько готовых расширений к Yii, которые в целом при совокуплении и после небольшой доточки напильником реализуют нужный мне функционал - написание велосипеда было бы излишним. Только вот этот момент с количеством корневых нод смущал.

Из сказанного вами я понял, что скорее всего стоит остановится на однорутовом варианте - в противном случае мне для каждого пользователя нужно заводить отдельный корень, что как я теперь понимаю, является несколько мудрённым вариантом.

p.s. На yiiframework.ru мне ответили, что одно из преимуществ множества рутов

Тоже разумно, не подумал об этом. В общем "с этим нужно переспать" :)

если для хранения пользователей и групп - одного рута хватит с головой (вы подобие ACL хотите организовать, как я понимаю ?), кроме того, в первой ссылке вы добавили, что нет необходимости в пересчётах левых/правых ключей. Вот этот пересчёт - самое слабое место вложенных множеств.

То есть, как бы лично сделал я, в случае хранения иерархии пользователей и их прав - использовал бы одну рутовую ноду. Но, если задача стоит просто организовать иерархию пользователей, отношение их к конкретным группам (и не только к одной), и все возможные права на объекты модели данных проекта, рекомендую почитать об ACL (по-русски, с иллюстрациями) и используемых структурах, как таковых, безотносительно к конкретному движку и прочее.

RFC2505, в Yii есть свой механизм для ACL + написано много расширений для работы с ним.

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

Близко к EAV паттерну, если не брать во внимание, что это дерево, но опять же не то, а пока не хочется раскрывать суть. :)

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

Dreammaker, если у нас есть "родитель" у некоторого дерева, то я бы юзал многокорневую структуру. да, именно изза обновления райт кеев всего дерева при инсерте, не говоря уже про другие операции (перемещение, удаление), так вообще ололол :)

в PostgeSQL и Oracle есть допоплнение для работы с деревом на уровне хранилица... не на уровне SQL

можно PostgeSQL (правда я там сильно не интересовался деревом, говорят там несколько разных вариантов и есть как в Oracle)

http://www.sai.msu.su/~megera/postgres/gist/ltree/

и смотря какое дерево, во многих случаях достаточно обычный parent_id

большой недостаток NestedSet что очень ресурсоемкие INSERT, UPDATE и DETELE

оно начинает обновлять линию всю поперек... если дерево большой - будет долго (по крайней мере так видно по структуре NestedSet и по тестах так пишут)

лучше всего использовать транзакции, если использовать Nested sets может разваливатся дерево (т.к. INSERT, UPDATE и DETELE ресурсоемкий ) или нужно будет корректировать его

вот тут вот есть самый быстрый и лучший вариант на innodb я это давно еще видел:

http://www.opennet.ru/docs/RUS/hierarchical_data/

-- Adjacency List Tree Structure
CREATE TABLE `al_tree` (
 `id` bigint(20) NOT NULL auto_increment,
 `parent_id` bigint(20) default NULL,
 `name` varchar(50) NOT NULL,
 PRIMARY KEY (`id`),
 KEY `fk_tree_tree` (`parent_id`),
 CONSTRAINT `fk_tree_tree` FOREIGN KEY (`parent_id`) REFERENCES `al_tree` (`id`) ON DELETE CASCADE ON UPDATE CASCADE
) ENGINE=InnoDB DEFAULT CHARSET=utf8
 
-- Nested Set Tree Structure
CREATE TABLE `ns_tree` (
 `id` bigint(20) NOT NULL auto_increment,
 `name` varchar(50) NOT NULL,
 `lft` bigint(20) NOT NULL,
 `rgt` bigint(20) NOT NULL,
 `level` bigint(20) NOT NULL,
 PRIMARY KEY (`id`),
 KEY `nslrl_idx` (`lft`,`rgt`,`level`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8
 
-- Materialized Path Tree Structure
CREATE TABLE `mp_tree` (
 `id` bigint(20) NOT NULL auto_increment,
 `name` varchar(50) NOT NULL,
 `path` varchar(100) NOT NULL,
 `level` int(11) NOT NULL,
 PRIMARY KEY (`id`),
 KEY `mpp_idx` (`path`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8

MyISAM:

http://habrahabr.ru/blogs/perl/65495/

вот есть на триггерах:

http://habrahabr.ru/blogs/mysql/63883/

http://habrahabr.ru/blogs/postgresql/63416/

не много старые

http://doc.prototypes.ru/database/nestedsets/perl/module/

http://webscript.ru/stories/04/09/01/8197045

PS: я бы попробовал бы PostgeSQL

http://habrahabr.ru/blogs/sql/27965/

PSS: я использую только parent_id + кэширование, для моих решений достаточно:)

bearman, спасибо, мысли собираются в кучу.

rtyug, postgresql мне в данный момент не подойдёт по той причине, что мне нужно учить будет, хоть какие-то нюансы да есть :) Можно использовать ORM и переключится строчкой в конфиге, но тогда об использовании специфичных фич не может быть и речи.

Насчёт комбинированных способ хранения - я уже думал. Но у использования готовых расширений, которые есть для Yii существуют преимущества - их будут развивать без моего участия и я могу использовать уже готовый код, занявшись написанием самой логики приложения. Да и в любом случае через время большая часть проекта переедет на MongoDB, а для начала я думаю вряд ли проект упрётся в возможности Nested Sets.