why Redis use skiplist to implement zset

I study the implementation of Redis, I know that there are two data structure (skiplist and ziplist) behind zset. I know some basic idea of skiplist (keep multiple pointer to access next element faster, avg time complexity of search is O(logN)).

My question is :
I read the info said that there are two situations that Redis will use skiplist to implement zset, first : there are many members in zset, second : memebers in zset are long string.

What’s the benefit to use skiplist instead of ziplist in these two situations, why these two situations need special treatment? Why don’t we always use one data structure to implement zset?


ziplist is O(n) time complexity for searching and updating and skiplist is O(logN)

The only benefit for ziplist is memory usage. As zip list implement by linear memory address and no pointers to other nodes, it can save a lot of memory space for Redis.

When you only have few members in zset, O(N) and O(logN) will not have significant difference. But memory usage will have huge differences(consider you have 1m keys of zset and each zset only have 10 members).

And when there are a lot of members in zset(like 1m), time complexity is important since it will affect the concurrent performance.