zset是一种可以用来排序功能的有序集合，每个元素有一个浮点型的score属性，根据score来从小到大排序，score相同时，按照key的ascii码排序`。
和其他数据结构比较
一、基本使用
ZADDkey[NX
XX][CH][INCR]scoremember[scoremember...]
1、zadd插入元素到有序集合语法
2、key有序集合名
3、NX-元素不存在时才设置成功,XX-元素存在时才设置成功
4、CH修改返回值=添加的新元素和修改的元素之和
5、INCR修改新的score为原score加上新指定的score值
6、score新元素的分数值
7、新元素名称
ZRANGEkeystartstop[WITHSCORES]
1、ZRANGE按范围查找有序集合中元素，支持返回元素的分数
2、key是需要查找的有序集合
3、start开始坐标，0-代表第1个元素，依次内推，-1-代表最后一个元素
4、WITHSCORES是否返回分值
二、存储类型
和hash类型一样，zset也使用两种编码：ziplist和skiplist（跳表）。
在redis.conf中，通过下面的配置条件来切换存储类型
#元素个数小于个时使用ziplistzset-max-ziplist-entries#任意一个元素值member字节超过64字节，不使用ziplistzset-max-ziplist-value64
在源码中，新增一个元素时候，如果不存在有序集合，会根据配置创建不同存储类型的zset。
//新增元素命令根据配置创建不同编码的zsetvoidzaddGenericCommand(client*c,intflags){.../*Lookupthekeyandcreatethesortedsetifdoesnotexist.*/zobj=lookupKeyWrite(c-db,key);if(zobj==NULL){if(xx)gotoreply_to_client;/*Nokey+XXoption:nothingtodo.*/if(server.zset_max_ziplist_entries==0
server.zset_max_ziplist_valuesdslen(c-argv[scoreidx+1]-ptr)){//如果满足配置的ziplist阈值，使用ziplist编码zobj=createZsetObject();}else{//使用skiplistzobj=createZsetZiplistObject();}dbAdd(c-db,key,zobj);}else{if(zobj-type!=OBJ_ZSET){addReply(c,shared.wrongtypeerr);gotocleanup;}}...}
ziplist结构在上文中，已经分析过，本文就不再分析了，本文将重点分析skiplist
三、跳表分析
redis跳表的特点：
1、用c语言翻译实现了`WilliamPugh`的平衡树的概率替代方案算法。
2、支持重复的score成员
3、支持分数排序，也支持数据排序
4、有一个后向指针，所以它是一个双向链表，后向指针仅在“级别1”。这允许从尾到头遍历列表，对ZREVRANGE很有用
四、跳表结构定义
/*跳表节点定义ZSETsuseaspecializedversionofSkiplists*/typedefstructzskiplistNode{//元素内容字符串类型sdsele;//分数doublescore;//后继指针，用于从后向前查找数据structzskiplistNode*backward;structzskiplistLevel{//前驱指针，用于向前面查找数据structzskiplistNode*forward;//元素跨度unsignedlongspan;}level[];}zskiplistNode;typedefstructzskiplist{structzskiplistNode*header,*tail;//大小unsignedlonglength;//总层数intlevel;}zskiplist;typedefstructzset{//字典dict*dict;//跳表zskiplist*zsl;}zset;
总结：跳表是一个链表，每个节点上有一个层级数组，每一层的节点都保存下一个节点的指针。
五、skiplist新增方法源码分析
//插入一个节点zskiplistNode*zslInsert(zskiplist*zsl,doublescore,sdsele){/*update保存每一层插入位置的前一个节点*/zskiplistNode*update[ZSKIPLIST_MAXLEVEL],*x;unsignedintrank[ZSKIPLIST_MAXLEVEL];inti,level;serverAssert(!isnan(score));//zset头节点x=zsl-header;//从最大层开始遍历，寻找每一层插入位置的前一个节点for(i=zsl-level-1;i=0;i--){//计算插入位置最大层基础是0，其他是下一层作为基础/*storerankthatiscrossedtoreachtheinsertposition*/rank=i==(zsl-level-1)?0:rank[i+1];//当前节点的分数小于插入元素分数，或者分数相等，内容小于插入元素内容（需要在这个节点前插入数据）while(x-level.forward(x-level.forward-scorescore
(x-level.forward-score==scoresdscmp(x-level.forward-ele,ele)0))){//累加当前节点跨越的节点数rank+=x-level.span;//记录比现在当前节点小的节点x=x-level.forward;}update=x;}/*weassumetheelementisnotalreadyinside,sinceweallowduplicated*scores,reinsertingthesameelementshouldneverhappensincethe*callerofzslInsert()shouldtestinthehashtableiftheelementis*alreadyinsideornot.*///计算新元素的等级level=zslRandomLevel();//新元素等级比当前跳表等级大if(levelzsl-level){//初始化新等级和老等级之间的每个等级插入位置前一个节点数据for(i=zsl-level;ilevel;i++){//初始化插入位置前一个节点是第1个节点rank=0;//初始化插入位置前一个节为头节点update=zsl-header;//初始化插入位置前一个节点跨越的节点数为跳表长度update-level.span=zsl-length;}zsl-level=level;}//创建一个新节点x=zslCreateNode(level,score,ele);//遍历每一层根据之前算好的前一个位置将新节点插入到每层的位置for(i=0;ilevel;i++){//更新新节点下一个节点x-level.forward=update-level.forward;//新节点插入链接update-level.forward=x;//更新跨度/*updatespancoveredbyupdateasxisinsertedhere*/x-level.span=update-level.span-(rank[0]-rank);update-level.span=(rank[0]-rank)+1;}/*incrementspanforuntouchedlevels*/for(i=level;izsl-level;i++){update-level.span++;}//修改新的节点的前驱节点x-backward=(update[0]==zsl-header)?NULL:update[0];if(x-level[0].forward)x-level[0].forward-backward=x;else//新节点属于尾节点zsl-tail=x;//长度增加zsl-length++;returnx;}//随机计算新层级intzslRandomLevel(void){intlevel=1;//随机数*0.25（百分之25概率要加1个层级）层级自增1while((random()0xFFFF)(ZSKIPLIST_P*0xFFFF))level+=1;return(levelZSKIPLIST_MAXLEVEL)?level:ZSKIPLIST_MAXLEVEL;}
整体流程入下图：
预览时标签不可点收录于话题#个上一篇下一篇