[AndrewO]

IIRC, Redis uses skip lists in its implementation of sorted sets. Good rundown of the data structure.

[antirez]

Exactly, Redis uses augmented skiplists so that we can support the rank operation in O(log(N)).