Максим Тимофеев: Я не корректно выразился - задача не отсортировать результат запроса к базе, а отсортировать данные в базе (перемещением), чтобы они уже хранились в сортированном виде.
"И как связана insertAfter и сортировка?" - стандартных методов для сортировки в дереве от creocoder нет, есть только методы для перемещения узлов по дереву, ими и пользовался. По замерам именно insertAfter и лопает время: выполнение занимает ~ 0.09 c, то есть на 2000 записях это занимает 180 с, что невообразимо много.