Ну так смотрите debug панель, там есть данные, что конкретно там долго работает.
И как связана insertAfter и сортировка? Вставка элемента в дерево и сортировка дерева. Где логика?
$myModel = MyModel::find()->orderBy('lft')->all();
Далее рекурсия в php. 1 запрос. Вся хитрость в сортировке по lft. Тогда у Вас уже есть правильная упорядоченная структура, остается ей только вложенность сделать базируясь на depth.
Как вариант можете тут глянуть: https://github.com/yiiext/nested-set-behavior/blob...
там внизу самом пример php есть. Он для yii1, но по сути все так же
Я так понимаю _lft, _rgt и parent_id устанавливает за Вас установленное расширение. И проблема в том, что у Вас они валидируются, а не должны. Это должны быть safe атрибуты.
Если надо изменить положение элемента или элементов внутри дерева - надо менять им lft, rgt и при необходимости depth в том числе для потомков. Если деревья не являются частью другого дерева, то можно ввести атрибут sort и по нему сортировать. Возможно в качестве sort можно использовать и tree, но это зависит от архитектуры
function(node, data) {
// data.otherNode.key - что двигаем
// node.key - относительно чего двигаем
// data.hitMode - как именно (after, before, over)
})