I'm starting to do things like this in Redis. For instance consider Redis Lists: POP and PUSH are O(1), also to get the first or last 10 items in constant time

I'm starting to do things like this in Redis. For instance consider Redis Lists: POP and PUSH are O(1), also to get the first or last 10 items in constant time is possible with LRANGE, but what if the user is often accessing a "far" range in a very long list? A similar problem happens to ZRANGE and Sorted Sets. Ok this problems allows to apply some access-pattern based optimization solution. For instance the linked list will have an associated N-elements circular buffer with pointers to far elements, so you can jump to the N-th node if it's on the (small) circular buffer and the clients continue to ask for an "LRANGE mylist 1000000 1000010". This is probably just the start but in general a small cache of "nodes" to recently very used places of data structures is a promising strategy in order to turn otherwise O(N) access patterns in constant time when they are very frequent.