数据结构:
zset是有序的,不运行重复的,带有分值score的
数据结构对比:
操作命令:
zadd myzset 10 java 20 python 20 ruby 40 mysql 50 php (添加)
zrange myzset 0 -1 withscores (通过score进行排序从小到大)
zrevrange myzset 0 -1 withscores (通过score进行排序从大到小)
zrangebyscore myzset 20 30 (通过score取出20-30的产品)
zrem myzset java python (将java和python移除)
zscard myzset (统计总数)
zincrby myzset 5 java (将java加5分)
zcount myzset 20 50 (统计20-50之间有多少个)
zrank myzset java (java在set中处于第几个位置,从0开始)
zscore myzset java (java有多少分)
存储实现原理:
在redis.conf文件中有两行这么写的
zset-max-ziplist-entries 128 # zset中压缩列表ziplist最大的元素是128个,超过128将会使用跳表skiplist+dict来存储
zset-max-ziplist-value 64 # zset中压缩列表ziplist中每个元素最大的个数是64个,超过64将会使用跳表skiplist+dict来存储
什么是跳表skiplist dict呢?我们先来看下面一张图:
这是一个有序的链表,当我们要将20这个数字插入到链表中的时候,他是从开始到结尾一个一个进行比对直到找到21之后才停止,这样他的效率就很低,时间复杂度是O(n),查找也是一样的道理。
怎么优化呢,skiplist是怎么实现的呢?再来看下面一张图:
可以看到他将某些元素中加了指针,这有点类似于数组中的二分法查找,但是链表中没有数组,所以用指针的方式来实现,看下面源码
typedef struct zskiplistNode { sds ele; /* zset 的元素 */ double score; /* 分值 */ struct zskiplistNode *backward; /* 后退指针 */ struct zskiplistLevel { struct zskiplistNode *forward; /* 前进指针,对应 level 的下一个节点 */ unsigned long span; /* 从当前节点到下一个节点的跨度(跨越的节点数) */ }level[]; /* 层 */ }zskiplistNode; typedef struct zskiplist { struct zskiplistNode *header, *tail; /* 指向跳跃表的头结点和尾节点 */ unsigned long length; /* 跳跃表的节点数 */ int level; /* 最大的层数 */ } zskiplist; typedef struct zset { dict *dict; zskiplist *zsl; } zset;
随机获取层数的函数,源码位置t_zset.c
int zslRandomLevel(void) { int level = 1; while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF)) level += 1; return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL; }
应用场景:
排行榜