What databases can I use to represent ordered sets? In a SQL database, the only way to represent an arbitrarily ordered set is to give every record an "Order" and every time you update or move an item around in this ordering you have to update or somehow maintain the entire list of ranks with a nightly job or something like that. 

For example, I can represent the ordered set [C, B, D, A] in this way in a SQL database:

ID  Name   Order
1   A      4
2   B      2
3   C      1
4   D      3


If I want to move an item to a different position in the set, or prepend a new item, I may have to update a lot of items. In general there is a lot of maintenance overhead with this approach.

Querying the data once it is in the database is not an issue for SQL, the issue is the significant maintenance overhead of reordering the set. There is no simple operation in SQL to move an item to a new position in the set. The ordering is arbitrary and user-defined.

I realize that this can be accomplished using SQL, it's just very clunky to perform certain operations like prepending items, or moving an item to a new position. Even this example operation of reversing the order of the set requires a pretty lengthy, complex, query. The type of database I'm looking for might support such an operation natively, or at least more elegantly.

So, if I am designing an application (like Trello, for example) that very heavily involves ordered sets, it seems SQL is not the ideal database technology for me. Are there any databases whose syntax support ordered sets in a more natural way? 

These are some CQL3 queries from the Cassandra documentation that seem close to what I'm looking for. This prepends an item to an ordered set.

UPDATE users SET top_places = [ 'the shire' ] + top_places WHERE user_id = 'frodo';


This one will set the value of the item at position 2 in the set. I suspect I could use this to easily perform arbitrary swaps/reorders.

UPDATE users SET top_places[2] = 'riddermark' WHERE user_id = 'frodo';


Unfortunately the documentation also states


  And while we may (or may not) relax that rule a bit in the future,
  this still means that collections are not meant to be excessively
  large. They are not a replacement for a proper modelisation into
  tables.


which seems to suggest that ordered sets are not (yet) first class citizens in CQL3.
I think you are missing one of the key principles of relational database design. I thought it was Dr E F Codd but I can't find a reference.

Data is stored without sorting, and is sorted when it is retrieved. This was intended to avoid the overhead of re-ordering the data with every update or insert. 

Sorting is done with the order by clause when you select data.

The fact that some vendors store the data ordered by a clustered index is a bit misleading. If your data must be sorted you should always use order by rather than rely upon the the underlying storage.

As you must have some criteria for sorting, why not incorporate that in your query so that data is ordered as it is queried every time you select it.