Beshere
@Beshere
Разработчик

Какая реализация дерева лучше?

В университете меня учили делать дерево так: Node(id, parent_id), а дедушка Лафоре учит делать так: Node(id, child_left_id, child_right_id).

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

А как вам кажется, какой вариант лучше?
  • Вопрос задан
  • 210 просмотров
Решения вопроса 1
Ninazu
@Ninazu
Все зависит от того зачем вам это дерево.
1. Это Adjacency List, он хорош когда вам нужно часто писать в дерево и редко его читать.
2. Это Nested Set, он хорош когда вам нужно часто читать дерево и редко в него писать.

Для того чтоб построить часть дерева по первому варианту вам нужно либо вытаскивать ВСЕ записи из базы, и потом рекурсивно проходится по ним и строить его, либо писать встроенную процедуру для того чтоб рекурсия была на стороне базы данных. Также нужно следить чтоб не возникало циклических зависимостей в айдишниках

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

Лично я использую первый вариант для дерева комментариев, а второй для меню сайта. Хотя деревья всегда есть смысл кэшировать.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 2
webinar
@webinar
Учим yii: https://youtu.be/-WRMlGHLgRg
Разные типы деревьев существуют потому что случаи бывают разные. И типов хранения деревьев на порядок больше, чем Вы знаете. Для каждого случая, своя оптимальная реализация.
Что лучше помидор или задница? Что бы съесть - помидор, что бы с..ть - задница. Так что прекращайте искать лучшие варианты, пока нет проекта.
Ответ написан
usdglander
@usdglander
Yipee-ki-yay
Это вы ещё про Nested Set и Materialized Path не слышали.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы