Antirez: are you considering a Sorted Map of some kind with a way to iterate over it? (ZSET is almost it, but semantics are a little different and Redis does not have iterators, at least not exposed to the protocol). With SQLite4 a Redis Cluster with such a type could serve as the underlying storage engine, basically creating an infinitely scalable database.
BTW - kudos on Redis, I LOVE the clean C code. I must note that in the process of hacking on Thredis I couldn't help noticing there are many "cultural" similarities between SQLite and Redis, e.g. fondness of Tcl, integers as strings, etc.
BUT this is all a moot point - a Sorted Set is not the type of structure that something like SQLite4 needs anyway. The keys should be sorted lexicographically, not by score. I think a Skip List fits the bill perfectly, and Redis already contains an implementation of it (as part of Sorted Sets), why not expose it as a standalone type?