Return to Answer

If rank isn't completely arbitrary but is instead derivable from some other property (e.g. name, player score, etc.) then take a good look at Joel's answer.

If it is an arbitrary property of your data, then that should be stored as a column in your table of records. Assuming Amazon's SimpleDB is similar to the typical RDBMS, you can then index this column and quickly satisfy all your above queries with the appropriate indexing strategy. This is normal for an RDBMS.

Given that you expect high insert and update activity, but also relatively high read activity, I recommend doing the following:

• Cluster the table on the rank, especially if the vast majority of your queries are against rank. If not, or if choosing a clustering key is not available in SimpleDB, then just create an index with rank as the leading column. This would satisfy queries 3-6.
• An index on the record first and then rank (or, in the SQL Server world, just record and INCLUDE-ing rank, or just record if you've clustered on rank) would satisfy query 7.
• Operations 1 and 2 can be optimized by spacing out your data appropriately (i.e. setting the FILLFACTOR in SQL Server). This is especially important if you cluster on rank.
• As you insert or update ranks, maintain as much of a gap between rank numbers as possible to minimize that possibility that you will need to re-rank an existing record to accommodate a rank insert or update. For example, if you rank your records in steps of 1000 you leave enough room for about half that many changes and inserts with minimal chance you'll need to re-rank a record not directly involved in those changes.
• Every night re-rank all records to reset the rank gaps between them.
• You can tune the frequency of the mass re-rankings as well as the rank gap size to accommodate your expected number of inserts or updates relative to the number of existing records. So if you have 100K records and expect your inserts and updates to be 10% of that, leave enough room for 10K new ranks and re-rank nightly.
• Re-ranking 500K records is an expensive operation, but done once a day or week off-hours should be fine for a database like that. This off-hours mass re-ranking to maintain the rank gaps is what saves you having to re-rank many records for each rank update or insert during your normal and peak hours.

If you expect 100K+ reads on a 100K+ sized table I do not recommend using the linked list approach. It will not scale well to those sizes.

If rank isn't completely arbitrary but is instead derivable from some other property (e.g. name, player score, etc.) then take a good look at Joel's answer.

If it is an arbitrary property of your data, then that should be stored as a column in your table of records. Assuming Amazon's SimpleDB is similar to the typical RDBMS, you can then index this column and quickly satisfy all your above queries with the appropriate indexing strategy. This is normal for an RDBMS.

Given that you expect high insert and update activity, but also relatively high read activity, I recommend doing the following:

• Cluster the table on the rank, especially if the vast majority of your queries are against rank. If not, or if choosing a clustering key is not available in SimpleDB, then just create an index with rank as the leading column. This would satisfy queries 3-6.
• An index on the record first and then rank (or, in the SQL Server world, just record and INCLUDE-ing rank, or just record if you've clustered on rank) would satisfy query 7.
• Operations 1 and 2 can be optimized by spacing out your data appropriately (i.e. setting the FILLFACTOR in SQL Server). This is especially important if you cluster on rank.
• As you insert or update ranks, maintain as much of a gap between rank numbers as possible to minimize that possibility that you will need to re-rank an existing record to accommodate a rank insert or update. For example, if you rank your records in steps of 1000 you leave enough room for about half that many changes and inserts with minimal chance you'll need to re-rank a record not directly involved in those changes.
• Every night re-rank all records to reset the rank gaps between them.
• You can tune the frequency of the mass re-rankings as well as the rank gap size to accommodate your expected number of inserts or updates relative to the number of existing records. So if you have 100K records and expect your inserts and updates to be 10% of that, leave enough room for 10K new ranks and re-rank nightly.
• Re-ranking 500K records is an expensive operation, but done once a day or week off-hours should be fine for a database like that. This off-hours mass re-ranking to maintain the rank gaps is what saves you having to re-rank many records for each rank update or insert during your normal and peak hours.

If you expect 100K+ reads on a 100K+ sized table I do not recommend using the linked list approach. It will not scale well to those sizes.

Since rank is a property of your data, then that should be stored as a column in your table of records. Assuming Amazon's SimpleDB is similar to the typical RDBMS, you can then index this column and quickly satisfy all your above queries with the appropriate indexing strategy. This is normal for an RDBMS.

What kind of load profile do you expect? Are ranks modifiable after the record has been inserted?

• If you expect this database to be heavily read-biased, you can cluster the table on the rank or create an index with rank as the leading column. This would satisfy queries 3-6.
• An index on the record then rank (or, in the SQL Server world, just record and INCLUDE rank, or just record if you've clustered on rank) would satisfy query 7.
• Operations 1 and 2 can be optimized by spacing out your data appropriately (i.e. setting the FILLFACTOR in SQL Server).

If rank isn't completely arbitrary but is instead derivable from some other property (e.g. name, player score, etc.) then take a good look at Joel's answer.

If it is an arbitrary property of your data, then that should be stored as a column in your table of records. Assuming Amazon's SimpleDB is similar to the typical RDBMS, you can then index this column and quickly satisfy all your above queries with the appropriate indexing strategy. This is normal for an RDBMS.

Given that you expect high insert and update activity, but also relatively high read activity, I recommend doing the following:

• Cluster the table on the rank, especially if the vast majority of your queries are against rank. If not, or if choosing a clustering key is not available in SimpleDB, then just create an index with rank as the leading column. This would satisfy queries 3-6.
• An index on the record first and then rank (or, in the SQL Server world, just record and INCLUDE-ing rank, or just record if you've clustered on rank) would satisfy query 7.
• Operations 1 and 2 can be optimized by spacing out your data appropriately (i.e. setting the FILLFACTOR in SQL Server). This is especially important if you cluster on rank.
• As you insert or update ranks, maintain as much of a gap between rank numbers as possible to minimize that possibility that you will need to re-rank an existing record to accommodate a rank insert or update. For example, if you rank your records in steps of 1000 you leave enough room for about half that many changes and inserts with minimal chance you'll need to re-rank a record not directly involved in those changes.
• Every night re-rank all records to reset the rank gaps between them.
• You can tune the frequency of the mass re-rankings as well as the rank gap size to accommodate your expected number of inserts or updates relative to the number of existing records. So if you have 100K records and expect your inserts and updates to be 10% of that, leave enough room for 10K new ranks and re-rank nightly.
• Re-ranking 500K records is an expensive operation, but done once a day or week off-hours should be fine for a database like that. This off-hours mass re-ranking to maintain the rank gaps is what saves you having to re-rank many records for each rank update or insert during your normal and peak hours.

If you expect 100K+ reads on a 100K+ sized table I do not recommend using the linked list approach. It will not scale well to those sizes.

Since rank is a property of your data, then that should be stored as a column in your table of records. Assuming Amazon's SimpleDB is similar to the typical RDBMS, you can then index this column and quickly satisfy all your above queries with the appropriate indexing strategy. This is normal for an RDBMS.

What kind of load profile do you expect? Are ranks modifiable after the record has been inserted?

If you expect this database to be heavily read-biased, you can cluster the table on the rank or create an index with rank as the leading column.

Since rank is a property of your data, then that should be stored as a column in your table of records. Assuming Amazon's SimpleDB is similar to the typical RDBMS, you can then index this column and quickly satisfy all your above queries with the appropriate indexing strategy. This is normal for an RDBMS.

What kind of load profile do you expect? Are ranks modifiable after the record has been inserted?

• If you expect this database to be heavily read-biased, you can cluster the table on the rank or create an index with rank as the leading column. This would satisfy queries 3-6.
• An index on the record then rank (or, in the SQL Server world, just record and INCLUDE rank, or just record if you've clustered on rank) would satisfy query 7.
• Operations 1 and 2 can be optimized by spacing out your data appropriately (i.e. setting the FILLFACTOR in SQL Server).