Are you really using a database? If you're using a real database, it undoubtedly has support for indexing more than one field in a table. That is, besides the primary key field, you can have auxiliary key fields. So, add a secondary key field that stores a number. Start out with all the numbers being multiples of ten (just like line numbers on old BASIC programs) so that you can insert several records in between before you have to renumber your index. Moving a record from the middle out to the beginning or end, of course, is easy: you just leave a bigger gap where it came from, no problem. Then you write a script that uses idle time or off time to look for places where the numbers are bunched together and renumber some records to pull them apart. The only time you take a performance hit is when you need to insert a record between two that already have adjascent numbers, and even then you only have to renumber enough records to fit it in, and let the background renumberer worry about smoothing out the distribution later.

If the list isn't large enough to warrant a full database, just use splice.

$;=sub{$/};@;=map{my($a,$b)=($_,$;);$;=sub{$a.$b->()}}
split//,".rekcah lreP rehtona tsuJ";$\=$ ;->();print$/
[download]