记录学习过程中的点点滴滴
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/
来自yaronspace.cn 本文链接:http://yaronspace.cn/blog/archives/1259您可能对下面文章也感兴趣:
这篇文章由admin于2011 年 04 月 12 日 17:38发表在分布式数据存储, 开源软件。你可以订阅RSS 2.0 你可以跳到结尾直接评论。目前不允许通知。 |