I study the implementation of Redis, I know that there are two data structure (
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
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
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.