Какая реализация дерева лучше?
Все зависит от того зачем вам это дерево.
1. Это Adjacency List, он хорош когда вам нужно часто писать в дерево и редко его читать.
2. Это Nested Set, он хорош когда вам нужно часто читать дерево и редко в него писать.
Для того чтоб построить часть дерева по первому варианту вам нужно либо вытаскивать ВСЕ записи из базы, и потом рекурсивно проходится по ним и строить его, либо писать встроенную процедуру для того чтоб рекурсия была на стороне базы данных. Также нужно следить чтоб не возникало циклических зависимостей в айдишниках
Второй вариант может вытянуть часть дерева со всеми его дочерними элементами одним запросом, но при изменении структуры запросы могут быть тяжелыми, особенно когда дерево внушительных размеров.
Лично я использую первый вариант для дерева комментариев, а второй для меню сайта. Хотя деревья всегда есть смысл кэшировать.
Это вы ещё про Nested Set и Materialized Path не слышали.