五.Redis中那些你不知道的秘密-五大基本结构SortedSet的实现原理

前言

SortedSet(zset)有序集合可以看做是在Set集合的的基础上为集合中的每个元素维护了一个顺序值: score,它允许集合中的元素可以按照score进行排序，所以它的经典实用场景如：考生按分数排名，某游戏玩家分数排行，网站首页某数据排行，最新评论按时间排序等等。

Redis是一个内存数据库，它在保证读写速度的同时也需要考虑内存开销，那对于SortedSet有序集合而言它需要维护一个顺序值，而对于有序集合的底层实现可以选择：数组，链表，平衡树或者红黑树等结构，但是SortedSet没有选择这些结构。数组插入和删除元素性能很差，链表查询慢，平衡树或红黑树虽然查询效率高，但是在插入和删除元素的时候需要维持树的平衡导致性能下降，而且实现极为复杂。

所以，SortedSet底层而是采用了一种新型的数据结构--- 跳跃表

skiplist跳跃表原理

跳跃表的性能堪比红黑树，而且实现起来比红黑树简单很多。那么什么是跳跃表？理解跳跃表之间我们先来看一看下面这个链表。

假如我们要查询值为 13的节点，对于上面的单向链表来说，我需要从前往后遍历节点，算一下要进行 10 次查找，性能是非常差的，如何提升查询速度？我们知道即使有序的链表也是没变法进行二分查找的，除非我们把这个链表变成红黑树这样的结构，但是红黑树实现起来太过麻烦。所以，如果我把这个链表像这样处理一下呢？

我把第一层链表中的元素，每隔2个元素就向上提取一个元素，形成第二层的链表，如上图，如果我查找元素的时候先从最上面的层级找 13 ，当找到 18的时候大于13，就退回10，往下一层找，然后就找到13了，你数一下这一次的查找次数几乎是之前的单向链表的一半，大大节省了查询时间。那如果我再往上抽取一层呢？

按照刚才的规律，我们再向上抽取一层，这一次查找的次数是不是又变少了？其实这种数据结构就是“跳跃表”的存储结构了。其实你可以发现他的查询性能是可以媲美红黑树的，但是实现起来比红黑树简单许多。

SortedSet底层实现

SortedSet底层使用到了Ziplist压缩列表和“跳跃表”两种存储结构，在Redis配置文件中有如下两个配置：

• zset-max-ziplist-entries 128：zset采用压缩列表时，元素个数最大值。默认值为128。
• zset-max-ziplist-value 64：zset采用压缩列表时，每个元素的字符串长度最大值。默认值为64。

zset插入第一个元素时，会判断下面两种条件，zset-max-ziplist-entries的值是否等于0；zset-max-ziplist-value小于要插入元素的字符串长度，满足任一条件Redis就会采用跳跃表作为底层实现，否则采用压缩列表作为底层实现方式。源码见：t_zset.c

void zaddGenericCommand(client *c, int flags) {
   
   
 ...省略...
 if (zobj == NULL) {
   
   
        if (xx) goto reply_to_client; /* No key + XX option: nothing to do. */
        if (server.zset_max_ziplist_entries == 0 ||
            server.zset_max_ziplist_value < sdslen(c->argv[scoreidx+1]->ptr))
        {
   
   
            zobj = createZsetObject();/ *创建跳跃表*/
        } else {
   
   
            zobj = createZsetZiplistObject(); / *创建压缩列表 */
        }
        dbAdd(c->db,key,zobj);
    }
}

一般情况下，不会将zset-max-ziplist-entries配置成0，元素的字符串长度也不会太长，所以在创建有序集合时，默认使用压缩列表的底层实现。zset新插入元素时，会判断以下两种条件：zset中元素个数大于zset_max_ziplist_entries；插入元素的字符串长度大于zset_max_ziplist_value。当满足任一条件时，Redis便会将zset的底层实现由压缩列表转为跳跃表 ，见t_zset.c 中的 zsetAdd 函数

if (zzlLength(zobj->ptr) > server.zset_max_ziplist_entries ||
                sdslen(ele) > server.zset_max_ziplist_value)
     zsetConvert(zobj,OBJ_ENCODING_SKIPLIST);/* 转跳跃表 */

值得注意的是，zset在转为跳跃表之后，即使元素被逐渐删除，也不会重新转为压缩列表。

skiplist的结构

跳表主要有：跳表节点，头节点，尾节点，节点数，节点最大层级数组成，如下：源码见 server.h

typedef struct zskiplist {
   
   
    struct zskiplistNode *header, *tail;//跳表节点 ，头节点 ， 尾节点
    unsigned long length;//节点数量
    int level;//目前表内节点的最大层数
} zskiplist;

typedef struct zset {
   
   
    dict *dict;
    zskiplist *zsl;
} zset;

解释：

• header: 指向跳跃表头节点，头节点是跳跃表的一个特殊节点，它的level数组元素个数为64。头节点在有序集合中不存储任何member和score值，ele值为NULL，score值为0；也不计入跳跃表的总长度。头节点在初始化时，64个元素的forward都指向NULL，span值都为0。
• tail：指向跳跃表尾节点
• length：跳跃表长度，表示除头节点之外的节点总数
• level：跳跃表的最大的节点的高度。

zskiplist 结构如图：

zskiplistNode 结构

//跳表节点
typedef struct zskiplistNode {
   
   
    sds ele;//用于存储字符串类型的数据
    double score;//分值
    struct zskiplistNode *backward;//后向指针
    struct zskiplistLevel {
   
   //节点所在的层
        struct zskiplistNode *forward;//前向指针
        unsigned int span;//该层向前跨越的节点数量
    } level[];  //节点层结构 数组,每次创建一个跳表节点时，都会随机生成一个[1,32]之间的值作为level数组的大小。
} zskiplistNode;

解释：

• ele : 用于存储字符串类型的数据
• backward：后退指针，只能指向当前节点最底层的前一个节点，头节点和第一个节点——backward指向NULL，从后向前遍历跳跃表时使用。
• score：用于存储排序的分值

• level：为柔性数组。每个节点的数组长度不一样，在生成跳跃表节点时，随机生成一个1～64的值，值越大出现的概率越低。

  • forward：指向本层下一个节点，尾节点的forward指向NULL。
    • span：forward指向的节点与本节点之间的元素个数。span值越大，跳过的节点个数越多

跳跃表的每个节点的ele存储有序集合的成员member值，score存储成员score值。所有节点的分值是按从小到大的方式排序的，当有序集合的成员分值相同时，节点会按member的字典序进行排序。

文章结束，希望对你有所帮助，如果喜欢请给个好评吧！！！