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

12 3
Solmyr
На сайте с 10.09.2007
Offline
501
1832

Есть объекты объединенные в структуру типа дерева. У каждого объекта может быть ноль или один родитель и ноль или несколько детей. Вопрос состоит в том, как хранить эти данные, чтобы быстро можно было выполнять для конкретного объекта операцию поиска цепочки всех родителей (вплоть до того, объекта у которого 0 родителей).

Поскольку у каждого объекта может быть ноль или один родитель, есть соблазн хранить для каждого объекта id родителя (или 0 если родителя нет). Но тогда операция "пройтись по цепочке" получается рекурсивная и не быстрая.

edogs software
На сайте с 15.12.2005
Offline
771
#1

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

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

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

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

Разработка крупных и средних проектов. Можно с криптой. Разумные цены. Хорошее качество. Адекватный подход. Продаем lenovo legion в спб, дешевле магазинов, новые, запечатанные. Есть разные. skype: edogssoft
Solmyr
На сайте с 10.09.2007
Offline
501
#2

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

VHS
На сайте с 28.09.2007
Offline
142
VHS
#3

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

LEOnidUKG
На сайте с 25.11.2006
Offline
1678
#4

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

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);

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

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

✅ Трастовых площадок под размещение статей и ссылок. Опыт 15 лет! ( https://searchengines.guru/ru/forum/675690 ) ⭐ Купить вечные трастовые ссылки для сайта ( https://getmanylinks.ru/?srh ) ⭐ Новый аналог AllSubbmitter (заполнение форм) https://getmanylinks.ru/getmanysubmits.html (Бесплатное демо)
S
На сайте с 23.05.2004
Offline
305
#5

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

Adjacency List

Materialized Path

Nested Sets

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

Это просто подпись.
VHS
На сайте с 28.09.2007
Offline
142
VHS
#6

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

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

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

Александр Смирнов
На сайте с 30.08.2007
Offline
102
#7

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

Разработаю веб-сервисы на Yii2 фреймворке от 150 тыс. руб. в мес. Обучу программированию на Yii2
LEOnidUKG
На сайте с 25.11.2006
Offline
1678
#8
LEOnidUKG, ок, у меня в таблице 8кк строк (элементов дерева) с глубиной в 7 уровней. Мне нужно получить всю иерархию от низшего элемента. Оптимально ли будет выбирать всю таблицу?

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

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

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

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

edogs software
На сайте с 15.12.2005
Offline
771
#9
LEOnidUKG:
Смотря какой размер данных. Возможно вы храните вообще всю структуру в отдельной таблице и весит она там от силы 50 МБ.
Также можно выгружать из таблицы не все данные, а то только id и rootid.
И тут уже встаёт вопрос, кто быстрее это выполнит mysql или PHP?
Я больше ставлю на второго.

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

LEOnidUKG
На сайте с 25.11.2006
Offline
1678
#10
мы категорически поставим на один mysql-ный запрос, который вытянет все уровни.
которая при 50мб будет некисло так в пхп памяти занимать

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

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

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

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

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

12 3

Авторизуйтесь или зарегистрируйтесь, чтобы оставить комментарий