Как правильно хранить структуры данных типа деревьев?

Зависит от Ваших данных.

При большой глубине, но небольшой ветвистости неплохо подходит Materialized Path. Учитывая что у Вас задача "выбрать родителей" (а не детей), имхо, это лучший вариант. Просто храните тупо в текстовом поле 1/4/6/9/10 - список родителей с разделителем.

При большой ветвистости, но небольшой глубине вполне катит id-parentid. Не недооценивайте скорость id-parentid цепочек, в рядовой ситуации из такой таблицы вполне можно выбрать 16 родителей одним мускул запросом и это будет неожиданно быстро (left join left join), просто не надо делать рекурсию, надо делать одним проходом.

При среднем объеме данных в принципе годятся оба варианта или их комбинация. Навороты типа nested sets нужны крайне редко.

Есть еще момент модифицировать данные. При изменении данных, как мне найти всех у кого надо изменить эти самые Materialized Path? Наиболее частая операция - это когда где-то посредине цепочки меняется один родитель на другой (у которого тоже там есть свои родители) то есть ветка переносится с одного места дерева на другое.

Like по старому пути узла + % в mysql

Чтобы не нагружать БД я юзаю вот такую функцию в комментариях многоуровневых:

function build_hierarchy($arr, $id_key = 'id', $pid_key = 'parent_id') {

$structure = array();

while($elem = array_shift($arr)) {

if(isset($structure[ $elem[$id_key] ])) {

$elem['children'] = $structure[ $elem[$id_key] ];

unset($structure[ $elem[$id_key] ]);

} else

$elem['children'] = array();

if(isset($references[ $elem[$pid_key] ])) {

$references[ $elem[$pid_key] ]['children'][ $elem[$id_key] ] = $elem;

$references[ $elem[$id_key] ] =& $references[ $elem[$pid_key] ]['children'][ $elem[$id_key] ];

} else {

$structure[ $elem[$pid_key] ][ $elem[$id_key] ] = $elem;

$references[ $elem[$id_key] ] =& $structure[ $elem[$pid_key] ][ $elem[$id_key] ];

}

asort( $references );

}

return array($structure);

}

Все данные из запроса я закидываю в переменную:

$bigmass=fetchAll();//результат выгрузки из БД, обычный SELECT * where url='index'

и делаю разбор:

$bigmass=build_hierarchy($bigmass,'num','rootid'); //Название столбцов из вашей таблицы: num = id записи; rootid = указывает чья это запись;

далее сделав:

print_r($bigmass);

вы увидите как всё разложено по полочками и можете с этим работать.

При этом БД не напрягается вообще.

Можно еще ознакомиться с данными релизациями:

Adjacency List

Materialized Path

Nested Sets

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

Solmyr, надо понимать глубину дерева и общий объем, чтобы предложить оптимальный способ хранения.

LEOnidUKG, ок, у меня в таблице 8кк строк (элементов дерева) с глубиной в 7 уровней. Мне нужно получить всю иерархию от низшего элемента. Оптимально ли будет выбирать всю таблицу?

Полезно почитать о производительности http://mikhailstadnik.com/hierarchical-data-structures-and-performance

Используйте Nested Sets (вложенные множества) для хранения деревьев сложной структуры.

Смотря какой размер данных. Возможно вы храните вообще всю структуру в отдельной таблице и весит она там от силы 50 МБ.

Также можно выгружать из таблицы не все данные, а то только id и rootid.

И тут уже встаёт вопрос, кто быстрее это выполнит mysql или PHP?

Я больше ставлю на второго.

Для 7 уровней, при условии что id и rootid одного типа и оба в ключах, мы категорически поставим на один mysql-ный запрос, который вытянет все уровни. Супротив пхп, которому надо будет вытащить всю иерархию (которая весит "всего" 50мб), составит из нее структуру данных (которая при 50мб будет некисло так в пхп памяти занимать), а потом еще выберет из нее нужную последовательность.

Это уже теории.

Я лично тестировал свою функцию на сайте с комментариями под 500К и посещалкой более 75 000 в сутки. Это на футбольном сайте. Я пишу как делаю на практике и вещь, которая работает достаточно быстро.

Я привожу реальные примеры кода, которые работают. А не какие-то там join, где-то когда будут и как они там будут ХЗ. И сколько там родителей будет.

Я join вообще терпеть не могу, юзаю их очень редко т.к. они достаточно мощно грузят БД если объёмы данных большие.

Также я не думаю, что ТС-у нужно просматривать ВСЕХ сразу родительные и дочерние данные. 99%, что есть условия какие же родители нужно выбрать и там явно не 1 миллион записей.