[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.