从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/

来自yaronspace.cn  本文链接:http://yaronspace.cn/blog/archives/1259