How to save a particular, mutable "order" into a database

The best way I've found to handle this is to have a floating point order field. When you move something between two other items, set that field to halfway between its neighbors.

This is cheap on both reads and writes. The only downside is the floats keep getting longer :)

Looking at Tony Andrew's and Mark's answers in particular, it seems I really have only two alternatives:

• Saving a 'next' value, making the objects behave like a linked list (see Mark's answer)
  With this, changing the order is cheap, but I'd have to retrieve the items and then sort them by their 'next' value, which is expensive
• Saving an 'order' value (see Tony Andrew's answer)
  This makes retrieving cheap but saving a new order potentially expensive, because in the worst case, I'd have to change all the order values. cletus points out that one could use a large number in the form of 2^n for the order multiplier.

Meta: All of these answers are good and correct, which one should I choose as correct?

The "naive" approach you suggest is also the best practice!

Taking Tony Andrews' answer into consideration, you could alternatively store a "next" index with each entry. Then when you pull them all in, walk the array by following the chain. That makes moving an item easier, as you only have to touch maximum two rows.

The disadvantage with this approach is if you ever need a subset (e.g. the first 3 items) you still need to pull in all the items, or use a SQL loop. So it's between affecting all rows during update, or accessing all items during read. As ever, measure the speed and see which is better for your situation.