Skip lists gamble on structure in a very controlled way: every node climbs to higher levels according to coin flips, and the resulting towers behave like a balanced search structure with high probability. That sounds suspicious until you see why it works, why it is easy to augment with ranks, and why Redis uses it in the skiplist-backed form of its sorted sets.
Redis sorted sets are not just “store items in order.” They need several operations at once: look up a member directly, update its score, fetch ranges by score, fetch ranges by rank, and return the rank of a member quickly. That is a harder job than plain dictionary lookup.
A hash table is great for member -> score, but it does not know anything about order. A balanced tree can represent order, but Redis does not just need ordering. It also needs ranks, range scans, and a structure that is straightforward to augment and maintain.
Perfect for exact lookup and updates when you already know the member name.
Perfect for rank, range, predecessor/successor, and walking the set in sorted order.
When Redis switches to its skiplist-backed encoding, it uses the hash table for identity and the skip list for order, so neither structure has to be contorted into doing both jobs alone.
A skip list is a stack of ordered linked lists. The bottom level contains every element. Higher levels contain progressively fewer elements, acting as express lanes. To decide how tall a node becomes, you repeatedly flip a coin: promote once for heads, stop on tails.
Search works by starting at the top-left of the structure. At each level, you move right while the next key is still less than your target. When moving right would overshoot, you drop down one level and continue. By the time you reach level 0, you are either sitting on the target key or on the last key before where it should be. The higher levels let you skip across big stretches of the list quickly; the lower levels do the fine-grained cleanup.
Insertion uses almost the same walk. As you search for the insertion point, you remember the last node visited at each level. Those remembered nodes are the predecessors. Then you flip coins to choose the new node's height and splice the new tower in after those predecessors on each level it occupies. So insertion is not a global rebalance. It is a local pointer rewrite after one top-down search.
No explicit rotations. No recoloring. No global rebalancing pass. The structure stays well-shaped with high probability because the number of tall towers falls off geometrically. That is what “probabilistic balancing” means here: the balancing policy is encoded in the level distribution rather than by deterministic repair rules.
p = 1/2, roughly half the nodes appear on level 2, a quarter on level 3, an eighth on level 4, and so on.Balanced trees can absolutely be made concurrent. The issue is not possibility; it is engineering friction. Tree updates often involve rotations and multi-node structural cases. Getting all of those corner cases correct under interleaving updates is delicate.
Skip lists mutate more locally. Insertion and deletion are mostly pointer splices across a small number of levels. There is no rotation logic, and the invariants are easier to state: each level is ordered, and each node's tower is vertically aligned. That simplicity is why skip lists show up so often in lock-free and concurrent data-structure literature.
In Redis's skiplist-backed sorted-set encoding, the implementation comment says the structure uses two data structures to hold the same elements: a hash table mapping elements to scores, and a skip list mapping scores to elements. That gives O(log N) ordered updates while preserving direct member lookup. Small sorted sets may instead use a compact listpack encoding.
The interesting extra is span metadata. Each forward pointer stores how many bottom-level nodes it skips. That lets Redis answer rank queries in logarithmic time by accumulating spans while descending the structure. Redis also keeps a backward pointer at level 1, which makes reverse range traversal efficient.
The implementation below is a generic ordered skip list in JavaScript. It stores a value at each key, maintains span metadata so ranks can be answered in logarithmic expected time, and includes the core ordered-map operations: insertion, lookup, deletion, rank, and selection by rank.