redis中sorted set的实现原理

从redis 1.1版本，redis开始支持sorted set（有序集合），今天在看redis源码时，具体看了它的实现；

关于ZSET的具体用法：http://redis.io/commands#sorted_set

ZSET的实现用到了两个数据结构：hash table 和 skip list(跳跃表)，其中hash table是具体使用redis中的dict来实现的，主要是为了保证查询效率为O(1) ，而skip list(跳跃表)主要是保证元素有序并能够保证INSERT和REMOVE操作是O(logn)的复杂度。

关于skip list这里简单介绍下：skip list是链表的一种特殊形式，对链表的一种优化；保证INSERT和REMOVE操作是O(logn)的负载读，而通用链表的复杂度为O(n);

关于skip list的详细介绍请参考下面这篇文章：

http://blog.csdn.net/caoeryingzi/archive/2010/11/18/6018070.aspx

sorted set的用途：

可以用作实时排名，例如微博用户的排名

还有TOPN问题等

http://wangyuanzju.blog.163.com/blog/static/1302920099311165490/