[TOC] 參考連接：http://zhangtielei.com/posts/blog-redis-skiplist.html ## 概述 Redis的zset有序集合的內部數據結構是`ziplist`和`zskiplist` * 有序集合保存的元素數量小于128個 * 有序集合保存的所有元素的長度小于64字節 當同時滿足上述條件時使用`ziplist`，否則使用`zskiplis`. ziplist前文已經講過，不再贅述。這一節我著重描述`zskiplist`--跳躍表. 下文統一用`skiplist` `skiplist`本質上也是一種查找結構，用于解決算法中的查找問題（Searching），即根據給定的key，快速查到它所在的位置（或者對應的value）。 一般查找問題的解法分為兩個大類：一個是基于各種平衡樹，一個是基于哈希表。但skiplist卻比較特殊，它沒法歸屬到這兩大類里面。 ## `skiplist`的數據結構 server.h ``` typedef struct zskiplistNode { sds ele; double score; struct zskiplistNode *backward; struct zskiplistLevel { struct zskiplistNode *forward; unsigned long span; } level[]; } zskiplistNode; typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level; } zskiplist; ``` ## redis有序集合采用跳躍表的原因 為什么redis的有序集合采用跳躍表而不是紅黑樹呢？對于這個問題，可以在[https://news.ycombinator.com/item?id=1171423](https://news.ycombinator.com/item?id=1171423)找到作者本人的一個回答： >1. They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then *less* memory intensive than btrees. > 2. A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees. > 3. They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code. About the Append Only durability & speed, I don’t think it is a good idea to optimize Redis at cost of more code and more complexity for a use case that IMHO should be rare for the Redis target (fsync() at every command). Almost no one is using this feature even with ACID SQL databases, as the performance hint is big anyway. About threads: our experience shows that Redis is mostly I/O bound. I’m using threads to serve things from Virtual Memory. The long term solution to exploit all the cores, assuming your link is so fast that you can saturate a single core, is running multiple instances of Redis (no locks, almost fully scalable linearly with number of cores), and using the “Redis Cluster” solution that I plan to develop in the future.