Вообще говоря, есть три подхода.
Первый и самый простой — материализованные пути, это когда мы для каждого комментария храним весь его путь от корня, то есть имеем такую структуру, которая выглядит как-то так:
1.
1.1.
1.2.
1.2.1.
1.3
2.
2.1.
Ну и так далее. Для получения всех комментариев в нужном порядке необходимо просто сделать запрос на получение всех комментариев, только отсортированных в лексикографическом порядке по полю, которое содержит этот путь. Если не учитывать время выполнения запроса, то асимптотически это дело будет работать за O(n), где n — количество комментариев.
Второй подход, чуть посложнее, но выглядящий менее криво — для каждого комментария хранить номер родительского. После того, как мы сделали запрос на получение комментариев, отсортированных по id, мы пробегаем по этим комментариям. Будем строить дерево комментов. Понятно, что если у какого-то комментария есть родитель, то мы его уже добавили в дерево, так как у нас комментарии приходят в отсортированном порядке по их номеру. Поэтому возьмём номер родительского комментария и вставим в список его детей текущий коммент (т. е. что-то типа children[parent_id].insert(node_id)). После такого прохода получим дерево, с которым дальше можем делать что угодно. Получаем асимптотику O(n) при использовании обычных массивов и O(n log n) при использовании ассоциативных массивов, но меньший расход памяти.
Третий подход — использовать уже указанные выше
Nested Sets, но на практике, по-моему, их никто не использует.
