custom sorting or ordering a table without resorting the whole shebang

Question

for ten years we've been using the same custom sorting on our tables, i'm wondering if there is another solution which involves fewer updates, especially since today we'd like to have a replication/publication date and would'nt like to have our replication replicate unnecessary entries. i had a look into nested sets, but it does'nt seem to do the job for us.

base table:

id | a_sort
---+-------
1    10
2    20
3    30

after inserting

insert into table (a_sort) values(15)

an entry at the second position.

id | a_sort
---+-------
1    10
2    20
3    30
4    15

ordering the table with

select * from table order by a_sort

and resorting all the a_sort entries, updating at least id=(2,3,4)
will of course produce the desired output

id | a_sort
---+-------
1    10
4    20
2    30
3    40

the column names, the column count, datatypes, a possible join, possible triggers or the way the resorting is done is/are irrelevant to the problem. also we've found some pretty neat ways to do this task fast.

only; how the heck can we reduce the updates in the db to 1 or 2 max.

seems like an awfully common problem.

the captain obvious in me thougth once "use an a_sort float(53), insert using a fixed value of ordervaluefirstentry+abs(ordervaluefirstentry-ordervaluenextentry)/2"..
but this would only allow around 1040 "in between" entries - so never resorting seems a bit problematic ;)

Answer 1

You really didn't describe what you're doing with this data, so forgive me if this is a crazy idea for your situation:

You could make a sort of 'linked list' where instead of a column of values, you have a column for the 'next highest valued' id. This would decrease the number of updates to a maximum of 2.

You can make it doubly linked and also have a column for next lowest, which would bring the maximum number of updates to 3.

See: http://en.wikipedia.org/wiki/Linked_list