好久之前有写过有关 redis zset 解析的一篇文章，近期决定整理一下 redis 的知识，从应用到底层实现来讲解，梳理自己的一套 redis 文章，算是一个小专栏，希望能对大家学习 zset 有所帮助。

1.简介

zset 是一个有序集合，每一个成员有一个分数与之对应，成员不可以重复，但是数是可以重复的，zset 会自动用分数对成员进行排序。

2.zset 的应用命令

1.zadd 添加语句

zadd key score member//添加一条key为rank，score为1，member为yc的数据zadd rank 1 yc

2.查看 zset 集合的成员个数

zcard key//查看key为rank的集合内成员个数zcard rank

3.查看 zset 置顶范围的成员，withscores 为输出结果带分数。

zrange key start  end//获取从0到10的rank的memberzrange rank 0 10//获取rank所有的memberzrange rank 0 -1//输出带分数的结果zrange rank 0 -1 withscores

4.获取 zset 成员的下标位置。

zrank key member//查看member为yc的成员在key为rank集合的位置zrank rank yc

5.获取 zset 集合指定分数之间的成员个数

zcount key start end//获取rank分数值在[1,3]之内的值zcount rank 1 3

6.删除集合中一个或者多个成员

zrem key member...//删除rank中值为yc和qj的两个成员zrem rank yc qj  

7.获取指定的分数

zscore key member//获取rank中tom的分数zscore rank tom 

8.为指定成员的分数进行增减操作，负值为减，正值为加。zincrby

zincrby key score member//为tom的分数值加3zincrby rank 3 tom

9.根据指定分数的范围获取值，zrangebyscore

zrangebyscore key start end//获取rank中[0,9]范围内的对象zrangebyscore rank 0 9 

10.倒叙，原本默认的 zset 排序是从小到大按分数排序，有的场景需要用到倒叙 zrerange，zrerangebyscore

zrevrange key start  endzrevrangebyscore key start end//获取rank中[0,9]范围内的对象，倒叙zrevrangebyscore rank 0 9 //获取从0到10的rank的member，以score倒叙zreange rank 0 10

11.根据坐标，分数范围删除数据。zremrangebyscore，zremrangebyrank

zremrangebyscore key start endzremrangebyrank key start end//删除key为rank,分数范围在[0,8]的成员zremrangebyscore rank 0 8//删除key为rank，坐标范围在[0,2]的成员zremrangebyrank rank 0 2 

3.zset 结构分析

3.1 简介

了解完了 zset 的常用使用命令之后我们来关注一下 zset 的底层实现。

zset 对象的编码可以是 ziplist 也可以是 skiplist，所以先来理解一下这两个结构体

实现场景

当数据较少时，sorted set 是由一个 ziplist 来实现的。

当数据多的时候，sorted set 是由一个 dict + 一个 skiplist 来实现的。简单来讲，dict 用来查询数据到分数的对应关系，而 skiplist 用来根据分数查询数据（可能是范围查找）。

实现原因

ziplist 节省内存，但是增删改查等操作较慢，而 skiplist 正好相反，增删改查非常快，但是相比 ziplist 会占用更多内存。redis 在保存 zset 时按如下的规则进行选择：当元素个数超过 128 或最大元素的长度超过 64 时用 skiplist，其他情况下用 ziplist，每次对 zset 进行插入、删除元素时都会重新判断是否需要转换保存格式。

3.2 ziplist

3.2.1 简介

ziplist 是一个经过特殊编码的双向链表，它的设计目标就是为了提高存储效率。ziplist 可以用于存储字符串或整数，其中整数是按真正的二进制表示进行编码的，而不是编码成字符串序列。它能以 O(1)的时间复杂度在表的两端提供 push 和 pop 操作。

3.2.2 ziplist 和普通双向链表的区别

一个普通的双向链表，链表中每一项都占用独立的一块内存，各项之间用地址指针（或引用）连接起来。这种方式会带来大量的内存碎片，而且地址指针也会占用额外的内存。而ziplist却是将表中每一项存放在前后连续的地址空间内，一个ziplist整体占用一大块内存。它是一个表（list），但其实不是一个链表（linked list）。

3.2.3 整体结构图

3.2.4 压缩列表节点的构成

3.2.5 学习感悟

通过 redis 的低层设计其实我们可以学到很多

1.连续的一整块内存，减少了内存碎片，增大了内存利用率

2.通过地址长度来进行数据索引，而不是指针，减少了内存的消耗 　　 　　 　　　　　　　　

3.3 dict

Redis 的字典是用哈希表实现的，一个哈希表里面有多个哈希表节点，每个节点表示字典的一个键值对。

3.3.1 结构图示例

3.3.2 数据结构

typedef struct dict{  //类型特定函数  dictType *type;  //私有数据  viod *privdata;  //哈希表  dictht ht[2];  //rehash 索引  //当rehash不再进行时，值为-1  int trehashidx;/*rehashing not in progress if rehashidx == -1*/}dict;
typedef struct dictht{  //哈希表数组  dictEntry **table;  //哈希表大小  unsigned long size;  //哈希表大小掩码,用于计算索引值  //总是等于size - 1  unsigned long sizemask;  //该哈希表已经有的节点数目  unsigned long used;}dictht;
typedef struct dictEntry{  //键  void *key;  //值  union{    void *val;    uint64_t u64;    int64_t s64;  }v;  //指向下个哈希表节点，形成链表  struct dictEntry *next;}dictEntry;

3.2.3 学习感悟

哈希表是一种大家都熟知的数据结构，当初学习的时候也觉得理解了，redis 实现的哈希表使用的也是最通用的链地址法解决的哈希冲突，唯一当我觉得不错的是 dictht ht[2];的设计，随着哈希表键值对的增多，他的负载因子（负载因子的大小 = 表中数据个数 / 表的容量 ）需要被维持在一个合理的范围之内，所以我们需要对哈希表的大小进行相应的扩张或者收缩，此时需要进行 rehash。

redis 采用的是渐进式 rehash 的方式，避免哈希表中数据过大而导致一次性切换出现问题，这个方式的主要做法是 rehash 期间，每次对字典执行天假，删除，查找或者更新的时候，出了执行指定操作，还会顺带将 ht[0]哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1]，直到所有的 ht[0]到 ht[1]。

这个渐进式的方法，可以记下来，之后我们写代码转移数据也可以用到这种思想。

3.4 skiplist

3.4.1 简介

本质是一种查找结构，用于解决算法中的查找问题，根据给定的 key 快速查找到它所在位置，通过在每个节点维持多个指向其他节点的指针，从而达到快速访问节点的目的，是对有序链表的优化，查找的效率一般为 O(logn)。

3.4.2 结构图

redis 的跳跃表由 zskiplist 个 zskiplistNode 组成

zskiplist

typedef struct zskiplist{  //表头节点和表尾节点  struct zskiplistNode *head,*tail;  //表中节点数量  unsigned long length;  //表中层数最大的节点的层数  int level;}zskiplist;

header:指向跳跃表的表头

tail:指向跳跃表的表尾

level:记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）

length:记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头不在哪）

zskiplistNode

typedef struct zskiplistNode{  //后退指针  struct zskiplistNode *backward;  //分值  double score;  //成员对象  robj *obj;  //层  struct zskiplistLevel{  //前进指针    sturct zskiplistNode *forward;    //跨度    unsigned int span;  }level[];}zskiplistNode;

level:节点中用 L1,L2,L3 标记节点各个层，每层两个属性，前进指针和跨度。

前进指针用于访问位于表尾方向的其他节点。

跨度记录了前进指针指向节点和当前节点的距离。连线上带数字的箭头代表前进指针，而那个数字就是跨度。

backward(后退指针):节点中用 bw 字样标记节点的后退指针，它指向位于当前节点的前一个节点，在从表尾向表头遍历时使用。

score(分值)：1.0,2.0,3.0 都是节点所保存的分值，在跳跃表中，节点按各自所保存的分值从小到大排列。

成员对象(obj):o1,o2,o3 是节点所保存的成员对象。

3.4.3 算法描述

1.在普通有序链表中查找一个数据，我们要从头查找，时间复杂度是 O(n)

2.在普通链表之上，若我们隔一个，生成一个新的链表，这样如果我要查找 23 流程如下

2.1 23 首先和 7 比较，再和 19 比较，比它们都大，继续向后比较。

2.2 但 23 和 26 比较的时候，比 26 要小，因此回到下面的链表（原链表），与 22 比较。

2.3 比 22 要大，沿下面的指针继续向后和 26 比较。23 比 26 小，说明待查数据 23 在原链表中不存在，而且它的插入位置应该在 22 和 26 之间。

由于新增的指针，我们不需要跟链表中每个节点进行比较，而是先跳跃着比较，缩小比较范围，再进行查找增加了查找的效率，在二层之上，我们还可以添加三层，四层，skiplist 正式由此启发而诞生的数据结构。为了插入节点方便，skiplist 不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是针对每个节点随机出一个层数，以下是一个 skiplist 生成的过程。

举例子，若要在这样的跳表查找 23，流程如下

参考文章

http://zhangtielei.com/posts/blog-redis-skiplist.htmhttp://zhangtielei.com/posts/blog-redis-ziplist.htmlhttps://blog.csdn.net/QJYWYGQJYWYG/article/details/92847077https://blog.csdn.net/cxc576502021/article/details/82974940

书籍--redis 设计与实现