• The main idea of keeping everything in sequence is ofcourse always a performance issue as changing one record implicitly means an update to all following records, which is implicitly expensive and more so for larger tables.

    To minimize the cost, I see two options:

    * Keep the sequence numbers in a separate table with a 1 to 1 relationship to the main table. So there is a second table with the same PK as for the original table, and it has one extra attribute, namely a sequence counter with a unique index on it.

    * Keep a seprarate numbers with table the same number of records as the main table and let it have a foreign key to the main table. The primary key is the sequence number and it also has a unique index on the foreign key in this instance. You never have gaps this way and never delete records other then the last record(s) in the clustered index. Order changes affect only updates to the foreign key on existing pages.

    The static nature of the last method should work particulary well combined with with view- or table-partitions.

    I can think of more complex schemes that reduce things ever further by eliminating a lot of updates, and by localizing them. This is best pictured as working with offsets relative to a reference value. By updating the reference value(s), all following records are renumbered automatically without update. To reference the effective sequence number or perform sorts, you reference both the reference and the offeset to get the final sequence number/ordering. In such a scheme, moving a record to the top of the list only requires updating one or more reference records, and sometimes some of the offsets as well. But never all the offset records at once that exist for every records in the main table.