На счет ABBYY — неправда, механизмы распознавания текста у этой компании иные.

Был на одной их лекции, на которой они рассказывали, что пытались раз пять использовать нейронные сети для распознавания текста — все попытки были зафейлены, в результате чего в стенах компании слово «нейрон» и производные от него игнорируются :)

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

Вообще говоря, есть три подхода.

Первый и самый простой — материализованные пути, это когда мы для каждого комментария храним весь его путь от корня, то есть имеем такую структуру, которая выглядит как-то так:

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, но на практике, по-моему, их никто не использует.