Efficient and correct strategy for handling sortable items in a database

Question

In a web application I have a set of entities in a database with a numeric field responsible for their ordering. On a client side these entities are displayed as a sortable list allowing users to change their order.

As of now I have two solutions for managing order updates and none of them satisfies me.

The first one is simple: every time user changes some item order, traverse updated list, get all items IDs into array, send it to a server and issue a series of updates where each item order is it's ID's index in array.
Drawbacks of this approach: lots of unnecessary updates, inability to correctly handle a situation when items array sent to a server does not contain all the entities IDs.

The second one is as follows: when user changes an item order, changed item's ID is sent to a server along with ID's of items that "surround" changed item in it's new place in list. On server item's new order is calculated by (previous.order + next.order) / 2. So if item with order 3 gets moved between items with orders 5 and 6, it's new order becomes 5.5
This solution requires only one update per change but also has a serious problem: due to the algorithm used every change increases the decimal part in order numbers and sooner or later it requires more precision then my database can provide (I use MongoDB for this case but I suppose it's not that important).

My question is if any other more efficient and correct ways exist or maybe my current approaches can be somehow improved?

Answer 1

Describe the order in the database with an ordinal number, which starts at 0 for the first item and increases by 1 for every subsequent item. Then, you just need to send the ordinals of the moved item, and the ordinal of its new previous neighbour. You then do (i'm using $ to mark variables - you'll need to pass these into the queries from your code):

-- if $moved > $previous, and it's moving backwards, move everything between the new previous neighbour and the item forward one
update items
set ordinal = ordinal + 1
where ordinal > $previous
and ordinal < $moved;

-- else $moved < $previous, and it's moving forwards, move everything between the item and the new previous neighbour backwards one
update items
set ordinal = ordinal - 1
where ordinal > $moved
and ordinal <= $previous;

-- then move the item
update items
set ordinal = $previous + 1
where ordinal = $moved;

You could add a unique constraint to the ordinal column to help ensure integrity, but you'd have to be a bit cleverer about how you did updates.