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

Question

[EVGENY T.]

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

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

А как вам кажется, какой вариант лучше?

Comments

[res2001]

Как в таком подходе: Node(id, parent_id) вы будете делать обход дерева? Ведь голова дерева не содержит ссылок на потомков. Вам придется где-то держать все листовые узлы. Такая структура узлов больше похожа на стек, а не на дерево.

У дедушки - классический вариант двоичного дерева.

[EVGENY T.]

res2001, Обходы разные бывают. Если с корня начинать, то удобней дедушкин метод, а если с листьев, то... еще вопрос.

И всё равно любой обход строится через рекурсию и там приходится использовать стэки.

[res2001]

EVGENY T., Да я не против. Задачи бывают разные. Тут совершенно прав Максим Тимофеев

Вариант дерева Node(id, parent_id) - часто видел в базах данных для хранения чего-либо иерархического.
В SQL это легко реализовывается.

[Roman]

надо просто запомнить и все.

https://habr.com/post/188010/

Answer 1

[Ninazu]

Все зависит от того зачем вам это дерево.
1. Это Adjacency List, он хорош когда вам нужно часто писать в дерево и редко его читать.
2. Это Nested Set, он хорош когда вам нужно часто читать дерево и редко в него писать.

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

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

Лично я использую первый вариант для дерева комментариев, а второй для меню сайта. Хотя деревья всегда есть смысл кэшировать.

Answer 2

[Максим Тимофеев]

Разные типы деревьев существуют потому что случаи бывают разные. И типов хранения деревьев на порядок больше, чем Вы знаете. Для каждого случая, своя оптимальная реализация.
Что лучше помидор или задница? Что бы съесть - помидор, что бы с..ть - задница. Так что прекращайте искать лучшие варианты, пока нет проекта.

Comments

[Roman K]

что бы с..ть - задница

Что? Что сделать? Сесть?

[Максим Тимофеев]

Roman Kitaev, ну, пусть будет сесть, сесть и пос..ть

[alex-1917]

Roman Kitaev, ахахах, а я прочитал как соснуть

[Максим Тимофеев]

alex-1917, ))))

Answer 3

[Lander]

Это вы ещё про Nested Set и Materialized Path не слышали.

Comments

[Ninazu]

Так второй вариант как раз и есть Nested Set

[Lander]

Роман Усенко, Да. Вы правы. Просто мне показалось что для полноценного Nested Set чего то не хватает.