Strategy for Storing Large Amount of Ordered, but Reorderable Data in Database?

Question

If you had a fairly large amount of data (say a million rows) that you need returned in a specific order, one obvious way to do this is to simply put a numeric index on each row and order by that index. However, if you then want to create a new row in the middle of that data, you either need to hope that that there is a gap in the index between the two rows you need to put between, or you need to "UPDATE table SET position = position+1 WHERE position > new_position" which is potentially slow and not scalable.

Is there a smarter strategy for dealing with this? Am I best off just leaving large gaps between my rows and hoping for the best (possibly respacing rows with a background process.) Is there a database equivalent to a linked list?

EDIT: I know what indexes are and how traditional ordering is done (read my first sentence.) I'm wondering if there's a data structure to insert a new row into the middle of an ordered index such that range queries can still be done. A traditional next/prev pointer won't work for doing this as a single range query, so far as I know.

Answer 1

Databases are not spreadsheets, there is not implicit ordering.

select Col1, Col2, Col3
from some_table
where Col3 between value_1 and value_2
order by Col2 asc;

To speed-up retrieval, indexes are used.

Answer 2

You simply can't create a tuple in the middle of your data. You will add it at the end. The order by column must be used to return data in correct order and it will be fast if it is indexed.

Is there a database equivalent to a linked list?

Not directly - there are some ideas of storing trees inside of sql - which is a bit more than you asked for - but almost the same design. But be aware that this results in a query for each tuple (read link target, select next tuple). This will be extremely slow if you deal with millions of tuples.

Your edit: You can't add in the middle of tuples!

If you really need to do this:

• create a new table - add everything in the desired order
• drop old table
• rename new table to old table
• Be aware that you need to do this for each added tuple (as long as it is not added at the end of your data)