I am looking to store a sorted list inside a database. I want to perform the following operations efficiently.
- Insert(x) - Insert record x into the table
- Delete(x) - Delete record x from the table
- Before(x,n) - Return the 'n' records preceding the record x in the sorted list.
- After(x,n) - Return the 'n' records succeeding the record x in the sorted list.
- First(n) - Return the first 'n' records from the sorted list.
- Last(n) - Return the last 'n' records from the sorted list.
- Compare(x,y) - Given two records x and y from the table, find if x > y.
The simple method I could think of is to store some kind of a 'rank' attribute in the table and query by sorting on that attribute. But in this method inserting/modifying a record with a rank becomes a costly operation. Is there a better method?
Specifically, I am looking to implement the table using Amazon's SimpleDB. But a general answer for a relational database should also be helpful.
Update on load profile:
Since I am planning this for a web application, it depends on the number of users that use the app.
If there are 100k active users (super optimism :P), then my very approximate estimate per day would be
500k selects, 100k inserts and deletes, 500k updates
I would expect the table to grow up to 500k in total.
I am looking to optimize on the updates, insert and the Compare operations. The rank of the items will be constantly changing and I need to keep the table updated.