Что Adjacency List, что Nested Set позволяет построить дерево за один запрос.
Просто дергаете с сортировкой по id_parent и ordering и собираете в ассоциативный массив к примеру, чтобы потом во view размотать в то, что нужно.
Самое главное, не делать рекурсивную загрузку с запросами к БД, есть вероятность сделать ОЧЕНЬ много запросов к БД, что крайне непродуктивно.
Касаемо кэширования - тоже вариант хороший.
Схема простая - механизм построения дерева смотрит, есть ли кэш - если есть - отдает его, если нет - строит дерево и кэширует его (банальная сериализация, к примеру).
При записи/изменении ресурса, участвующего в дереве можно сбросить кэш, чтобы последующий запрос построил его и добавил в кэш.
