Que tal usar um integer coluna que define a ordem? Por padrão, você atribui números * 1.000, como 1.000, 2.000, 3.000.... e se você mover 3.000 entre 1.000 e 2.000, você o altera para 1.500. Então, na maioria dos casos, você não precisa atualizar os outros números. Eu uso essa abordagem e funciona bem. Você também pode usar double mas você não tem controle sobre a precisão e os erros de arredondamento, então não use.

Assim, o algoritmo se pareceria com :digamos que você mova B para a posição depois de A. Primeiro execute select para ver a ordem do registro ao lado de A. Se for pelo menos +2 maior que a ordem de A, basta definir a ordem de B para caber no meio. Mas se for apenas +1 acima (não há espaço depois de A), você seleciona os registros limítrofes de B para ver quanto espaço está deste lado, divide por 2 e depois adiciona esse valor à ordem de todos os registros entre A e B. É isso!

(Observe que você deve usar transação/bloqueio para qualquer algoritmo que contenha mais de uma única consulta, então isso também se aplica a este caso. A maneira mais fácil é usar a transação InnoDB.)