源码基于redis-3.0

1. 简单动态字符串

简介

简单动态字符串，即SDS（Simple Dynamic String），它是Redis中实现底层字符串相关数据结构的基础，它在C语言的字符串基础上进行抽象构建。

数据结构

在源码中， sds.h/sdshdr 表示一个最基本的SDS的组成，如下

struct sdshdr {

   // 记录buf数组中已使用字节的数量

   // 等于SDS所保存字符串的长度

   int len;

   // 记录buf数组中未使用字节的数量

   int free;

   // 字节数组，用于保存字符串

   char buf[];

};

char buf[] 这里使用的是柔性数组，好处如下：

• 倘若使用指针即bufchar ，分配内存需要量两个步骤：一次分配结构体，一次分配char buf，在释放内存的时候也需要释放两次内存：一次为char *buf，一次为结构体内存。而用长度为 0 的字符数组可以将分配和释放内存的次数都降低为 1 次，从而简化内存管理
• 长度为 0 的数组即char buf[]不占用内存，节省内存空间

// char buf[] 的情况

struct sdshdr s;

printf("%d",sizeof(s));

// 8

// char *buf 的情况

struct sdshdr s;

printf("%d",sizeof(s));

// 12

• 便于SDS统计len、size，时间复杂度为O(1)

// 返回sdshdr.len

static inline size_t sdslen(const sds s) {

   struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));

   return sh->len;

}

// 返回sdshdr.free

static inline size_t sdsavail(const sds s) {

   struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));

   return sh->free;

}

特点

SDS兼容一部分C语言函数

SDS遵循C字符串以空字符结尾的惯例，保存空字符的1字节空间不计算在SDS的len属性里面，并且为空字符分配额外的1字节空间，以及添加空字符到字符串末尾等操作，都是由SDS函数自动完成的，所以这个空字符对于SDS的使用者来说是完全透明的。遵循空字符结尾这一惯例的好处是，SDS可以直接重用一部分C字符串函数库里面的函数。

SDS属性len的作用

• C语言中没有记录字符长度自身信息，字符串长度需要从头到尾遍历，时间复杂度是O(n)，Redis中增加len属性来记录字符串长度，时间复杂度降低为O(1)，记录操作有SDS内部提供实现。
• 由于记录了字符串长度，也在一些字符串操作过程中避免了内存溢出问题

SDS减少了字符串变更时内存空间重分配

字符串的变更会频繁调用系统底层方法来进行内存空间变更，SDS通过未使用空间实现了空间预分配和惰性释放两种优化策略，避免了内存空间频繁变更带来的性能消耗。

预占空间

预占空间策略是，当已使用空间（len）小于1MB时，预占空间大小为已使用空间同等大小的空间进行预占；当已使用空间（len）大于等于1MB时，预占空间大小恒为1MB。通过这种预分配策略，SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次。

惰性释放

惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用属性 free 将这些字节的数量记录起来，并等待将来使用。

总结，无论是提前预分配空间还是惰性释放空间，必然会占用更多的额外空间，这里可以理解是以空间换时间的思想。

SDS保证文本二进制安全

所谓 二进制安全 是一种主要用于字符串操作函数相关的计算机编程术语。一个二进制安全功能（函数），其本质上将操作输入作为原始的、无任何特殊格式意义的数据流。对于每个字符都公平对待，不特殊处理某一个字符。说白了，就是程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，它被读取时就是什么样。

Redis通过buf数组存储字符，读取数组长度是通过len属性，而不是C语言那样通过'\0' 字符，因此对于特殊字符解析不会出现问题，是二进制安全的。

2. 链表

简介

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。C语言并没有内置这种数据结构，Redis提供了双端链表的实现。

数据结构

在源码中， adlist.h/listNode 表示一个最基本的链表的组成，如下

/*

* 双端链表节点

*/

typedef struct listNode {

   // 前置节点

   struct listNode *prev;

   // 后置节点

   struct listNode *next;

   // 节点的值

   void *value;

} listNode;

/*

* 双端链表结构

*/

typedef struct list {

   // 表头节点

   listNode *head;

   // 表尾节点

   listNode *tail;

   // 节点值复制函数

   void *(*dup)(void *ptr);

   // 节点值释放函数

   void (*free)(void *ptr);

   // 节点值对比函数

   int (*match)(void *ptr, void *key);

   // 链表所包含的节点数量

   unsigned long len;

} list;

特点

• 双端 链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的时间复杂度是O(1)
• 无环 表头节点的prev指针和表尾节点的next指针都指向null，对链表的访问以NULL为终点
• 带表头指针和表尾指针 通过list结构的head指针和tail指针获取链表的表头节点和表尾节点，时间复杂度是O(1)
• 带链表长度计数器 使用list结构的len属性来对list持有的链表节点进行计数，获取链表长度的时间复杂度是O(1)
• 多态 支持保存不同类型的值

使用场景

List列表键、发布&订阅、监视器、慢查询

3. 字典

简介

字典，是用来保存键值对（Kev-Value）类型数据的抽象数据结构。C语言并没有内置上线这种数据结构，Redis提供了实现支持。字典中的每个键（Key）都是独一无二的，程序可以在字典中根据键查找与之关联的值，或者通过键来更新值，又或者根据键来删除整个键值对，等等

数据结构

Redis字典所使用的哈希表由 dict.h/dictht 结构定义

/*

* 字典

*/

typedef struct dict {

   // 类型特定函数

   dictType *type;

   // 私有数据

   void *privdata;

   // 哈希表

   dictht ht[2];

   // rehash索引; 当rehash 不在进行时，值为-1

   in rehashidx;

} dict;

• type 支持多态存储特定数据类型
• privdata 保存需要传给那些类型特定函数的可选参数
• ht 字典持有两个哈希表dictht，ht[0]用来存储数据，ht[1]在rehash时使用
• rehashindx 标记当前是否正在进行rehash，值为-1时没有进行rehash

/*

* 哈希表

*

* 每个字典都使用两个哈希表，从而实现渐进式 rehash 。

*/

typedef struct dictht {

   // 哈希表数组

   dictEntry **table;

   // 哈希表大小

   unsigned long size;

   // 哈希表大小掩码，用于计算索引值

   // 总是等于size-1

   unsigned long sizemask;

   // 该哈希表已有节点的数量

   unsigned long used;

} dictht;

• table 持有一个dictEntry 组成的数组，存储的是字典数据的节点数据，即Key-Value数据
• size 数组大小
• sizemask 索引值，总是size-1
• used 已使用dictEntry 节点数量

/*

* 哈希表节点

*/

typedef struct dictEntry {

   // 键

   void *key;

   // 值

   union {

       void *val;

       uint64_t u64;

       int64_t s64;

   } v;

   // 指向下个哈希表节点，形成链表

   struct dictEntry *next;

} dictEntry;

• key 键
• v 值，可以是指针、或uint64_t整数、或int64_t整数
• next 指向下一个节点的指针

底层原理

哈希值计算

1. 使用字典设置的哈希函数，计算键key的哈希值，Redis使用MurmurHash2算法来计算哈希值，这种算法的优点在于，即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，并且算法的计算速度也非常快

hash = dict->type->hashFunction(key);

2. 使用哈希表的sizemask属性和哈希值进行取模计算，计算出索引值来确定哈希槽位置。根据情况不同，ht[x]可以是ht[0]或者ht[1]

index = hash & dict->ht[x].sizemask;

哈希碰撞

当 哈希表节点dictEntry 产生碰撞时，通过next来串联指向下一个节点，通过 链地址方法 解决哈希节点碰撞进行存储，碰撞的节点会采用 头插法 插入到单链表的头部，排在其他节点前面，因为该操作不需要遍历链表时间复杂度为O(1)

rehash

重新散列步骤如下，以扩容为例

扩容前

开辟空间

为字典的 ht[1] 哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及 ht[0] 当前包含的键值对数量（也即是 ht[0].used 属性的值）。如上图，扩容操作， size 要大于等于 2 ht[0].used 的第一个2的n次方即42=8，正好是2的3次方，因此 ht[1] 的size设置为8

拷贝对象

将保存在 ht[0] 中的所有键值对rehash到 ht[1] 上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到 ht[1] 哈希表的指定位置上

变更指针

当ht[0]包含的所有键值对都迁移到了 ht[1] 之后（ ht[0] 变为空表），释放 ht[0] ，将 ht[1] 设置为 ht[0] ，并在 ht[1] 新创建一个空白哈希表，为下一次rehash做准备

rehash触发条件

如下是扩容方法的源码：

// 指示字典是否启用 rehash 的标识

static int dict_can_resize = 1;

// 强制 rehash 的比率

static unsigned int dict_force_resize_ratio = 5;

/*

Expand the hash table if needed */

/*

* 根据需要，初始化字典（的哈希表），或者对字典（的现有哈希表）进行扩展

*

* T = O(N)

*/

static int _dictExpandIfNeeded(dict *d)

{

   /* Incremental rehashing already in progress. Return. */

   // 渐进式 rehash 已经在进行了，直接返回

   if (dictIsRehashing(d)) return DICT_OK;

   /* If the hash table is empty expand it to the initial size. */

   // 如果字典（的 0 号哈希表）为空，那么创建并返回初始化大小的 0 号哈希表

   // T = O(1)

   if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

   /* If we reached the 1:1 ratio, and we are allowed to resize the hash

    * table (global setting) or we should avoid it but the ratio between

    * elements/buckets is over the "safe" threshold, we resize doubling

    * the number of buckets. */

   // 以下两个条件之一为真时，对字典进行扩展

   // 1）字典已使用节点数和字典大小之间的比率接近 1：1

   //    并且 dict_can_resize 为真

   // 2）已使用节点数和字典大小之间的比率超过 dict_force_resize_ratio

   if (d->ht[0].used >= d->ht[0].size &&

       (dict_can_resize ||

        d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))

   {

       // 新哈希表的大小至少是目前已使用节点数的两倍

       // T = O(N)

       return dictExpand(d, d->ht[0].used*2);

   }

   return DICT_OK;

}

满足以下条件之一随即触发rehash

在执行BGSAVE命令或BGREWRITEAOF命令的过程中，Redis需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制（copy-on-write）技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可能地避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要的内存写入操作，最大限度地节约内存。

这里个人理解是Redis会根据情况调整dict_can_resize来决定是否开启提高负载因子比例进行rehash

渐进式rehash

扩容、缩容都遵循渐进式处理方式，以下是扩容渐进式rehash步骤：

1. 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。
2. 在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。
3. 在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性的值增一。添加数据只会在ht[1]添加，不会再重复添加到旧容器，查询逻辑会先在ht[0]查找没有的话再到ht[1]中查找。
4. 随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash至ht[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。

渐进式rehash的好处在于它采取分而治之的方式，将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的庞大计算量。

使用场景

哈希键

4. 跳跃表

简介

跳跃表（skiplist） 是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。支持平均O（logN）、最坏O（N）复杂度的节点查找，还可以通过顺序性操作来批量处理节点。跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。

数据结构

Redis的跳跃表由 redis.h/zskiplistNode 和 redis.h/zskiplist 两个结构定义，其中 zskiplistNode 结构用于表示跳跃表节点，而 zskiplist 结构则用于保存跳跃表节点的相关信息

/* ZSETs use a specialized version of Skiplists */

/*

* 跳跃表节点

*/

typedef struct zskiplistNode {

   // 成员对象

   robj *obj;

   // 分值

   double score;

   // 后退指针

   struct zskiplistNode *backward;

   // 层

   struct zskiplistLevel {

       // 前进指针

       struct zskiplistNode *forward;

       // 跨度

       unsigned int span;

   } level[];

} zskiplistNode;

• obj 成员对象。每个节点的成员对象是唯一的。
• score 分值。跳跃表中的所有节点都按分值从小到大来排序，分值相同时按照成员对象obj在字典序中的大小来进行排序，成员对象较小的节点会排在前面
• backward 后退指针，指向zskiplistNode节点
• level 层，由zskiplistLevel组成的数组。程序可以通过这些层来加快访问其他节点的速度，一般来说，层的数量越多，访问其他节点的速度就越快。每个跳跃表节点的层高都是1~32之间的随机数

• forward指向zskiplistNode节点的前进指针，提供遍历跳跃表的能力
• span跨度。通过跨度来标记当前节点在跳跃表中的排名rank。两个节点之间的跨度越大，它们相距得就越远。指向NULL的所有前进指针的跨度都为0，因为它们没有连向任何节点。

/*

* 跳跃表

*/

typedef struct zskiplist {

   // 表头节点和表尾节点

   struct zskiplistNode *header, *tail;

   // 表中节点的数量

   unsigned long length;

   // 表中层数最大的节点的层数

   int level;

} zskiplist;

• header 代表跳跃表最头部的zskiplistNode的头节点
• tail 代表跳跃表最尾部的zskiplistNode的尾节点
• length 跳跃表中节点总数量（不包含表头节点）
• level 跳跃表中的总层数（不包含表头节点中的层数）

底层原理

Redis中的 跳跃表 ，简单说就是在链表基础上增加了 多级索引 加快数据查找速度，另外增加了 backward 提供逆序查找，是 空间换时间 的思想。

如上图红色虚线为节点遍历路径，通过 span 跨度为1的 level 层进行节点边路，由 forward 路由到下一节点，直到遇到 forward 等于null，说明已是末位节点。

使用场景

有序集合键

5. 整数集合

简介

当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现，它是存储有序、不重复的整数集。

数据结构

在Redis中， intset.h/intset 结构表示一个整数集合

typedef struct intset {

   // 编码方式

   uint32_t encoding;

   // 集合包含的元素数量

   uint32_t length;

   // 保存元素的数组

   int8_t contents[];

} intset;

• encoding 编码方式。根据存储数据类型决定编码方式支持最小格式存储的编码方式
• length 数组的数量
• contents 保存元素的数组。contents数组并不保存任何int8_t类型的值，contents数组的真正类型取决于encoding属性的值。元素会按照从小到大的顺序进行存储

编码升级

使用能满足元素数据类型长度最小的编码方式，在无法满足时进行编码格式升级；不支持降级操作。

升级过程：

1. 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
2. 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
3. 将新元素添加到底层数组里面。

编码升级优点：

1. 统一编码存放避免类型错误
2. 节省内存

使用场景

集合键

6. 压缩列表

简介

压缩列表（ziplist）是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型（sequential）双端链表数据结构。一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。

数据结构

压缩列表

Redis的压缩列表是由 ziplist.c 结构体组成

• zlbytes 是一个无符号4byte整数，保存着 ziplist 使用的内存数量。
  通过 zlbytes，程序可以直接对 ziplist 的内存大小进行调整，无须为了计算 ziplist 的内存大小而遍历整个列表。
• zltail 压缩列表 最后一个 entry 距离起始地址的偏移量，占4byte。
  这个偏移量使得对表尾的pop操作可以在无须遍历整个列表的情况下进行。
• zllen 压缩列表的节点entry数目，占2byte。
  当压缩列表的元素数目超过 2^16 - 2 的时候，zllen 会设置为2^16-1 ,当程序查询到值为2^16-1，就需要遍历整个压缩列表才能获取到元素数目。所以 zllen 并不能替代 zltail。
• entry 压缩列表存储数据的节点，可以为字节数组或者整数。
• zlend 压缩列表的结尾，占1byte，恒为 0xFF，即255。

数据结构特点：

1. 内部表现为数据紧凑排列的一块连续内存数组。
2. 可以模拟双向链表结构，以O（1）时间复杂度入队和出队
3. 新增删除操作涉及内存重新分配或释放，加大了操作的复杂性
4. 读写操作涉及复杂的指针移动，最坏时间复杂度为O（n2）
5. 适合存储小对象和长度有限的数据

节点信息

/*

* 保存 ziplist 节点信息的结构

*/

typedef struct zlentry {

   // prevrawlen ：前置节点的长度

   // prevrawlensize ：编码 prevrawlen 所需的字节大小

   unsigned int prevrawlensize, prevrawlen;

   // len ：当前节点值的长度

   // lensize ：编码 len 所需的字节大小

   unsigned int lensize, len;

   // 当前节点 header 的大小

   // 等于 prevrawlensize + lensize

   unsigned int headersize;

   // 当前节点值所使用的编码类型

   unsigned char encoding;

   // 指向当前节点的指针

   unsigned char *p;

} zlentry;

• prevrawlensize 前置节点的长度
• prevrawlen 编码前置节点所需的字节大小
• len 当前节点值的长度
• lensize 编码当前节点所需的字节大小
• headersize 当前节点header的大小，等于 prevrawlensize + lensize
• encoding 当前节点值所使用的编码类型。支持3种字节数组、6种整数

• *p 指向当前节点的指针。配合zltail进行使用可以快速定位尾部节点位置

这里例举说明下：

• zlbytes 是210，代表整个压缩列表占用210字节
• zltail 尾部entry节点偏移量是179，通过指针p加上偏移量179可以找到尾结点
• zllen 是5，代表当前有5个entry节点
• entry 当前有5个entry节点
• zlend 恒为 0xFF，即255。

连锁更新

由于每个 entry 都维护了前置节点的字节大小，当前置节点字节大小变化会引起当前节点属性变更，Redis 将这种在特殊情况下产生的连续多次空间扩展操作称之为 连锁更新（cascade update）

影响

连锁更新在最坏情况下需要对压缩列表执行 N 次空间重分配操作， 而每次空间重分配的最坏复杂度为 O(N) ， 所以连锁更新的最坏复杂度为 O(N^2) 。

触发条件

压缩列表里要恰好有多个连续的、长度介于 250 字节至 253 字节之间的节点， 连锁更新才有可能被引发。

综上，触发连锁更新的概率很低，即使触发如果满足触发条件的节点数量不多也不会对性能产生太大影响

使用场景

列表键（少量、小整数值、短字符串）、哈希键（少量、小整数值、短字符串）

当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串或当一个哈希键只包含少量键值对，比且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做它的底层实现

7. 对象

简介

Redis 使用对象来表示数据库中的键和值， 每次当我们在 Redis 的数据库中新创建一个键值对时， 我们至少会创建两个对象， 一个对象用作键值对的键（键对象）， 另一个对象用作键值对的值（值对象）。

数据结构

Redis 中的每个对象都由一个 redisObject 结构表示

typedef struct redisObject {

   // 类型

   unsigned type:4;

   // 编码

   unsigned encoding:4;

   // 对象最后一次被访问的时间

   unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */

   // 引用计数

   int refcount;

   // 指向实际值的指针

   void *ptr;

} robj;

• type 类型。对于 Redis 数据库保存的键值对来说， 键总是一个字符串对象， 而值则可以是字符串对象、列表对象、哈希对象、集合对象、有序集合对象的其中一种

• encoding 类型。对象所使用的编码， 也即是说这个对象使用了什么数据结构作为对象的底层实现

不同类型对象具体底层实现的数据结构也不同， Redis 可以根据不同的使用场景来为一个对象设置不同的编码， 从而优化对象在某一场景下的效率，如下

• refcount 引用计数。 因为C语言没有内存自动回收机制，Redis通过引用计数（Reference Counting）实现了内存回收机制。当引用计数为0时，对象所占用的内存会被回收。

如上图， refcount 引用计数为5，此时说明被5个指针引用，此时对象进行共享，极大的减少了内存空间占用

Redis只提供了0~9999整数共享对象池，而没有提供其他数据类型的

• lru 对象最后一次被访问的时间。通过OBJECT IDLETIME [KEY]命令进行查看对象的空闲时间，当使用GET、SET等命令会激活对象，lru会被重置为0。该属性会在内存回收算法在volatile-lru或allkeys-lru时发挥作用
• *ptr 指向底层实现数据结构的指针

对象类型

字符串对象

raw与embstr的区别：

• embstr创建字符串对象只需一次内存分配，而raw需要两次
• embstr释放对象内存只需一次，而raw需要两次
• embstr使用的是一段连续的内存空间，比raw能更好的利用缓存带来的优势

浮点数值 会被转换成字符串对象进行保存和使用
编码转换 当存储值发生变化，编码格式和底层数据结构会发生变化
嵌套对象 字符串对象是最基础的对象类型，既可以存储数值也可以存储字符串，因此它也是构成其他复杂对象类型的基石，是五种数据对象中唯一一个可以被嵌套使用的对象类型，也就是说其他复杂数据对象如哈希对象、列表对象等会将字符串对象作为组成元素之一进行构建自身复杂对象类型

以embstr编码格式、string类型对象为例的字符串对象，ptr指向了sds数据结构，如下：

列表对象

双端链表实现

双端列表中 listNode 节点中 value 使用了 字符串对象 进行了构建

压缩列表实现

哈希对象

压缩列表实现

• 使用压缩列表进行哈希对象实现，键值对都是成对存储在一起
• 总是从尾部节点插入，Key在前，Value在后

哈希表实现

集合对象

整数集合实现

哈希表实现

使用哈希表作为底层数据结构时，通过 dictEntry 中 key 有值进行存储， value 为空

有序集合

压缩列表实现

• 使用压缩列表进行有序集合对象实现，元素和分值都是成对存储在一起
• 总是从尾部节点插入，元素在前，分值在后

跳跃表实现

跳跃表实现通过 zset 结构进行实现，同时包含一个 字典(dict) 和一个 跳跃表(skiplist)

/*

* 有序集合

*/

typedef struct zset {

   // 字典，键为成员，值为分值

   // 用于支持 O(1) 复杂度的按成员取分值操作

   dict *dict;

   // 跳跃表，按分值排序成员

   // 用于支持平均复杂度为 O(log N) 的按分值定位成员操作

   // 以及范围操作

   zskiplist *zsl;

} zset;

• dict 字典。键为成员，值为分值。用于支持O(1)复杂度的按成员取分值操作
• zsl 跳跃表。按分值排序成员。用于支持O(log N)的按分值定位成员操作以及范围操作

为什么有序集合要同时使用字典和跳跃表实现？

• 使用字典会保留O(1)复杂度查找，但是分值是无序存放的，无法支持排序和范围操作
• 使用跳跃表会保留分值顺序，支持排序和范围操作，但是O(log N)复杂度查找

综上，为了发挥各自优势，采用冗余两种数据结构才进行存储，且字典和跳跃表会共享元素成员和分值，因此不会造成对象重复，减少内存空间占用

参考

《Redis设计与实现》

https://www.cnblogs.com/meituantech/p/9376472.html 美团针对Redis Rehash机制的探索和实践

http://www.voidcn.com/article/p-pmiobrfc-bnw.html

https://blog.csdn.net/luoyanjiewade/article/details/88229820

https://www.cnblogs.com/hunternet/p/11248192.html 跳跃表

https://www.bilibili.com/read/cv9019236 压缩列表

http://redisbook.com/

https://github.com/huangz1990/redis-3.0-annotated