Как вариант — организовать записи в таблице как связанный список (однонаправленный, либо двунаправленный, в зависимости от задачи). В таком случае, при перемещении той или иной записи будут меняться ссылки лишь в записях, которые были до и после перемещаемой и в тех между которыми встанет перемещаемая запись.
