这是某个小伙伴最近在面试遇到的一个问题，我觉得特别有意思。当然这个题目有点小问题，因为并不是所有的数据类型底层都是两种数据结构。
松哥之前其实有两篇文章和大家讲了 String 和 List 底层的数据结构，今天我们就来整体上看一下 Redis 中五种常见数据类型底层的数据结构，看完大伙就明白了为什么会有这个问题，一言以蔽之：为了性能。
一、Redis6、Redis7 新特性
1.1 Redis6
Redis6.0 于 2020 年 5 月 2 日发布，已经经过了两年，也是目前使用人数最多的版本。
支持多线程处理网络数据的读写和协议解析。（IO处理多线程，执行命令仍单线程） 推出RESP3协议，提供更多的语义化响应，以开发使用旧协议难以实现的功能，实现 Client-side-caching（客户端缓存）功能。 支持SSL 提升了RDB日志加载速度 引入了 ACL（Access Control List），引入了用户概念，可以给每个用户分配不同的权限来控制权限。 ···
1.2 Redis7
Redis7.0 于 2022 年 4 月 24 日发布，至今最新已更新到 7.4.6 版本。
多AOF文件支持，为两种类型：基本文件(base files)、增量文件(incr files)，在 redis.conf文件中配置config命令增强，CONFIG GET/SET可以一次处理多个配置限制客户端内存使用， redis.conf中通过maxmemory-clients配置listpack紧凑列表替代ziplist的新数据结构，在 7.0 版本已经没有 ziplist 的配置了···
Redis 源码可到http://download.redis.io/releases/ 下载，以 Redis6.2.6 源码为例。
二、五大基本数据类型底层结构
使用 OBJECT ENCODING key 可以查看五大数据类型的底层数据结构
2.1 String
2.1.1 String简介
String 是 redis 中最基本的数据类型，一个 key 对应一个 value。
String 类型是二进制安全的，意思是 redis 的 string 可以包含任何数据。如数字，字符串，jpg 图片或者序列化的对象。
命令使用
| 命令 | 简述 | 使用 |
|---|---|---|
| GET | 获取存储在给定键中的值 | GET name |
| SET | 设置存储在给定键中的值 | SET name value |
| DEL | 删除存储在给定键中的值 | DEL name |
| INCR | 将键存储的值加1 | INCR key |
| DECR | 将键存储的值减1 | DECR key |
| INCRBY | 将键存储的值加上整数 | INCRBY key amount |
| DECRBY | 将键存储的值减去整数 | DECRBY key amount |
实战场景
缓存：经典使用场景，把常用信息，字符串，图片或者视频等信息放到 redis 中， redis 作为缓存层，mysql 做持久化层，降低 mysql 的读写压力。 计数器：redis 是单线程模型，一个命令执行完才会执行下一个，同时数据可以一步落地到其他的数据源。 session：常见方案 spring session + redis 实现 session 共享
2.1.2 String 底层结构
Redis 中字符串非 C 语言中的字符串，自己构建了简单动态字符串（Simple dynamic String）SDS，并作为默认字符串表示。
根据源码可以看到 SDS 定义了 5 种数据结构：sdshdr5,sdshdr8, sdshdr16,sdshdr32,sdshdr64，结构都相同，不同的是字节长度。
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* SDS 当前字符串的长度 */
uint8_t alloc; /* 分配给字符串的总容量，这个容量是不包含header和'\0'字符的容量 */
unsigned char flags; /* 表示属性，是sdshdr8还是sdshdr16等，用一个字节的低3位保存*/
char buf[];
};
为什么需要使用 5 种数据结构呢？因为 redis 会根据字符串的长度使用不同的 header 头，从而达到内存优化的目的。
当字符串的长度 len < 2^5且不为空的字符串的时候使用的是sdshdr5；当字符串的长度 2^5 >= len < 2^8或者字符串为空的时候使用sdshdr8；当字符串的长度 2^8 >= len < 2^16时候使用sdshdr16；当字符串的长度 2^16 >= len < 2^32并且系统是64位的时候使用sdshdr32；其他的情况使用 sdshdr64；
根据 SDS 的长度，如果进行追加，会进行自动扩容，类似 Java 的 ArrayList 扩容。
2.1.3 SDS 动态扩容
SDS 的动态扩容可以从下面的源码可以看出：
/* src/sds.c */
/* Return ASAP if there is enough space left. */
if (avail >= addlen) return s;
len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
reqlen = newlen = (len+addlen);
assert(newlen > len); /* Catch size_t overflow */
if (newlen < SDS_MAX_PREALLOC) // #define SDS_MAX_PREALLOC (1024*1024)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
初始分配时 alloc 值和字符串实际长度相同。 扩容时：
2.1.4 内存不对齐
注意到：SDS 定义时，参数里有 __attribute__ ((__packed__))，告诉编译器取消结构在编译过程中的优化对齐,按照实际占用字节数进行对齐，是 GCC 特有的语法。
CPU访问内存时，并不是逐个字节访问，而是以字长（word size）为单位访问，所以数据结构应该尽可能地在自然边界上对齐，如果访问未对齐的内存，处理器需要做两次内存访问，而对齐的内存访问仅需要一次访问，内存对齐后可以提升性能。
内存对齐后 CPU 访问内存的速度会大大提升，那为什么 SDS 选择看似的内存不对齐呢？是为了节省那缺省的字节空间吗？
printf("%ld\n", sizeof(struct sdshdr8)); // 3
printf("%ld\n", sizeof(struct sdshdr16)); // 5
printf("%ld\n", sizeof(struct sdshdr32)); // 9
printf("%ld\n", sizeof(struct sdshdr64)); // 17
可以看到
可以看到多了 pad 对齐项。从而如果要通过 buf - 1 访问 flag 是不可能的了，因为不同类型对齐字节数也不同，还需要进行类型判断，并且不同的系统可能有不同的对齐方式。
为了应对内存不对齐，Redis在 malloc 基础上封装了 zmalloc 将内存分配收敛，并解决了内存对齐的问题。
zmalloc分配内存源码如下：
/* zmalloc.c
/* Allocate memory or panic */
void *zmalloc(size_t size) {
void *ptr = ztrymalloc_usable(size, NULL);
if (!ptr) zmalloc_oom_handler(size);
return ptr;
}
/* Try allocating memory, and return NULL if failed.
* '*usable' is set to the usable size if non NULL. */
void *ztrymalloc_usable(size_t size, size_t *usable) {
ASSERT_NO_SIZE_OVERFLOW(size);
void *ptr = malloc(MALLOC_MIN_SIZE(size)+PREFIX_SIZE);
if (!ptr) return NULL;
#ifdef HAVE_MALLOC_SIZE
size = zmalloc_size(ptr);
update_zmalloc_stat_alloc(size);
if (usable) *usable = size;
return ptr;
#else
*((size_t*)ptr) = size;
update_zmalloc_stat_alloc(size+PREFIX_SIZE);
if (usable) *usable = size;
return (char*)ptr+PREFIX_SIZE;
#endif
}
通过阅读源码发现，zmalloc基于malloc，创建了自己的内存池，对内存池进行操作，相比于原生malloc，内存池可以极大地提升**内存分配和释放速度，并且可以防止内存泄漏**。并且在内存池分配内存前，malloc(MALLOC_MIN_SIZE(size)+PREFIX_SIZE)也进行了内存对齐。而内存池在设计的时候是需要内存对齐的，不然会出问题。
zmalloc是jemalloc的封装，jemalloc作为Redis的默认内存分配器，在减小内存碎片方面做的相对比较好。jemalloc在64位系统中，将内存空间划分为小、大、巨大三个范围；每个范围内又划分了许多小的内存块单位；当Redis存储数据时，会选择大小最合适的内存块进行存储。
所以Redis并不是没有进行内存对齐，而是通过内存池的方式进行内存对齐，极大减少了内存碎片的产生，同时对内存操作的效率也得到了很大的提升。
2.1.5 为什么不使用 C 语言的字符串呢？
不存在缓冲区溢出。对于C语言中
strcat()拼接如果空间不够会导致缓冲区溢出，SDS会通过len和alloc判断空间是否足够，如果不够就会进行相应的扩展。二进制安全
C语言中通过空字符作为字符串终止标志，而图片等二进制文件内容可能包含空串，因此无法正常读取，SDS都是以二进制来处理buf中的内容，以len属性来判断字符串的终止。
C语言由于不记录字符串的长度，所以如果要修改字符串，必须要重新分配内存（先释放再申请），因为如果没有重新分配，字符串长度增大时会造成内存缓冲区溢出，字符串长度减小时会造成内存泄露。
2.1.6 embStr和SDS有什么关系？
对于Sting字符串对象的编码可以是int，raw或者embstr。embstr保存长度小于44字节的字符串，是专门保存短字符串的一种优化编码、raw保存长度大于44字节的字符串。他们背后都使用SDS存储。
为什么是44字节？每个数据类型都有一个redisObject包含。
// src/server.h
typedef struct redisObject {
unsigned type:4; // 数据类型，4字节
unsigned encoding:4; // 数据编码，4字节
unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time). */
// 记录对象最后一次使用信息 ，24bit，3字节
int refcount; // 对象引用次数，32位下4字节
void *ptr; // 真实数据，32位下4字节
} robj;
可以算出一个RedisObject至少包含19字节，Redis认为超过64字节的String就属于长字符串，加上字符串结尾\0一个字节，所以相减后就得到一个embstr最大支持的字符串长度为44字节。
2.2 List
Redis3.2 之前使用双端链表实现 List，Redis2后引入了quicklist快表作为List的底层实现。但也还保留了链表的实现。
使用List结构，我们可以轻松地实现最新消息排队功能（比如新浪微博的TimeLine）。List的另一个应用就是消息队列，可以利用List的 PUSH 操作，将任务存放在List中，然后工作线程再用 POP 操作将任务取出进行执行。
命令使用
| 命令 | 简述 | 使用 |
|---|---|---|
| RPUSH | 将给定值推入到列表右端 | RPUSH key value |
| LPUSH | 将给定值推入到列表左端 | LPUSH key value |
| RPOP | 从列表的右端弹出一个值，并返回被弹出的值 | RPOP key |
| LPOP | 从列表的左端弹出一个值，并返回被弹出的值 | LPOP key |
| LRANGE | 获取列表在给定范围上的所有值 | LRANGE key 0 -1 |
| LINDEX | 通过索引获取列表中的元素。你也可以使用负数下标，以 -1 表示列表的最后一个元素， -2 表示列表的倒数第二个元素，以此类推。 | LINDEX key index |
使用列表的技巧
lpush+lpop=Stack(栈) lpush+rpop=Queue（队列） lpush+ltrim=Capped Collection（有限集合） lpush+brpop=Message Queue（消息队列）
Redis自己实现了链表
// src/adlist.h
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
typedef struct list{
//表头节点
listNode *head;
//表尾节点
listNode *tail;
//链表所包含的节点数量
unsigned long len;
//节点值复制函数
void (*free) (void *ptr);
//节点值释放函数
void (*free) (void *ptr);
//节点值对比函数
int (*match) (void *ptr,void *key);
}list;
提供了操作链表的函数
Redis链表特性：
①、双端：链表具有前置节点和后置节点的引用，获取这两个节点时间复杂度都为O(1)。
②、无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL,对链表的访问都是以 NULL 结束。
③、带链表长度计数器：通过 len 属性获取链表长度的时间复杂度为 O(1)。
④、多态：链表节点使用 void* 指针来保存节点值，可以保存各种不同类型的值。
2.2.1 QuickList快表
// src/quicklist.h
typedef struct quicklist {
quicklistNode *head; // quicklist的链表头
quicklistNode *tail; // quicklist的链表尾
unsigned long count; // 所有ziplist中的总元素个数
unsigned long len; // quicklistNodes的个数
int fill : QL_FILL_BITS; // 单独解释
unsigned int compress : QL_COMP_BITS; // 具体含义是两端各有compress个节点不压缩
...
} quicklist;
typedef struct quicklistNode {
struct quicklistNode *prev; //前一个quicklistNode
struct quicklistNode *next; //后一个quicklistNode
unsigned char *zl; //quicklistNode指向的ziplist
unsigned int sz; //ziplist的字节大小
unsigned int count : 16; //ziplist中的元素个数
unsigned int encoding : 2; //编码格式，原生字节数组或压缩存储
unsigned int container : 2; //存储方式
unsigned int recompress : 1; //数据是否被压缩
unsigned int attempted_compress : 1; //数据能否被压缩
unsigned int extra : 10; //预留的bit位
} quicklistNode;
QuickList 结构如下：
QuickList的优点有：
双向链表能在头尾在 O(1)下找到一个元素，若是在中部查找则平均复杂度也只是O(N)，N 是 Entry的个数。ziplist 使用了紧凑布局和可变编码方式大大降低了内存的使用。这就是 quicklis 作为 List 首选的实现方案。
QuickList查询时间复杂度为O(n)，因为访问两端时间复杂度为O(1)，所以用作队列进行push、pop时效率非常高。
2.3 Hash
Dict由两种数据类型实现：压缩列表ZipList和哈希表HashTable.
当数据量小且存储的为整数值或短字符串时使用ZipList作为Hash，其他情况使用HashTable。
ZipList压缩列表顾名思义非常节省内存。
Hash中的每一个键 key 都是唯一的，通过 key 可以对值来进行查找或修改。C 语言中没有内置这种数据结构的实现，所以字典依然是 Redis自己构建的。Redis 使用哈希表作为底层实现。
相比String存储，更节省空间，且使用于存储对象信息、能对对象其中的字段进行修改。
命令使用
| 命令 | 简述 | 使用 |
|---|---|---|
| HSET | 添加键值对 | HSET hash-key sub-key1 value1 |
| HGET | 获取指定散列键的值 | HGET hash-key key1 |
| HGETALL | 获取散列中包含的所有键值对 | HGETALL hash-key |
| HDEL | 如果给定键存在于散列中，那么就移除这个键 | HDEL hash-key sub-key1 |
2.3.1 哈希表定义
// src/dict.h
// 哈希表结构体定义
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，计算索引值，总是等于size-1
unsigned long sizemask;
// 已使用节点数量
unsigned long used;
} dictht;
// 哈希表Entry定义
typedef struct dictEntry {
// key
void *key;
// value
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
// 下一个节点
struct dictEntry *next;
} dictEntry;
一个哈希表dictht结构图如下：
2.3.2 字典 Dict
// src/dict.h
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash索引，未进行rehash时，值为-1
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
// rehash被暂停时，值>0， 代码错误时，值<0
int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;
typedef struct dictType {
// 计算哈希值
uint64_t (*hashFunction)(const void *key);
// 复制key
void *(*keyDup)(void *privdata, const void *key);
// 复制value
void *(*valDup)(void *privdata, const void *obj);
// 对比key
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
// 对比value
void (*keyDestructor)(void *privdata, void *key);
// 删除key
void (*valDestructor)(void *privdata, void *obj);
// 删除value
int (*expandAllowed)(size_t moreMem, double usedRatio);
} dictType;
type是一个指向dictType的指针，通过自定义的方式使得dict的key和value能够存储任何类型的数据。
注意到一个字典Dict有两个哈希表dictht，是为了实现渐进式 rehash。
什么叫渐进式 rehash？也就是说扩容和收缩操作不是一次性、集中式完成的，而是分多次、渐进式完成的。如果保存在Redis中的键值对只有几个几十个，那么 rehash 操作可以瞬间完成，但是如果键值对有几百万，几千万甚至几亿，那么要一次性的进行 rehash，势必会造成Redis一段时间内不能进行别的操作。所以Redis采用渐进式 rehash,这样在进行渐进式rehash期间，字典的删除查找更新等操作可能会在两个哈希表上进行，第一个哈希表没有找到，就会去第二个哈希表上进行查找。但是进行 **增加操作，一定是在新的哈希表上进行的**。
只有在rehash的过程中，ht[0]和ht[1]才都有效。而在平常情况下，只有ht[0]有效，ht[1]里面没有任何数据。
2.3.3 哈希算法与哈希冲突的解决
哈希表最重要的就是哈希算法，它决定了元素存放的位置。
Redis使用murmurHash2哈希算法，这种算法即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，计算速度非常快，使用简单。murmurHash2哈希算法源码可以查询阅读。
Dict的索引值计算过程如下：
// 1、使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);
// 2、使用哈希表的sizemask属性和第一步得到的哈希值，计算索引值
index = hash & dict->ht[x].sizemask;
有哈希算法就会产生哈希冲突，Redis解决哈希冲突的方式是使用了链地址法。和JDK1.7 HashMap的哈希冲突解决方法一样，如果产生冲突，采用头插法插入到链表的头部。
2.3.4 扩容与收缩（rehash）
扩容代码如下：
// src/dict.c
/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{
/* 如果rehash正在进行，返回. */
if (dictIsRehashing(d)) return DICT_OK;
/* 如果哈希表为空，则初始化容量为4 */
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了，需要进行扩容，扩容为原来的两倍
if (d->ht[0].used >= d->ht[0].size &&
(dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio) &&
dictTypeExpandAllowed(d))
{
return dictExpand(d, d->ht[0].used + 1);
}
return DICT_OK;
}
/* Our hash table capability is a power of two */
static unsigned long _dictNextPower(unsigned long size)
{
unsigned long i = DICT_HT_INITIAL_SIZE;
if (size >= LONG_MAX) return LONG_MAX + 1LU;
while(1) {
if (i >= size)
return i;
i *= 2;
}
}
阅读源码可知：
Dict初始化容量为4.如果负载因子大于1，则扩容为原来的两倍。 哈希表的容量始终为 2的n次方。
当哈希表保存的键值对太多或者太少时，就要通过rehash(重新散列）来对哈希表进行相应的扩展或者收缩,这个时候之前介绍的ht[1]就开始起作用了，rehash具体步骤：
为 ht[1]分配空间，同时持有ht[0]和ht[1]。如果执行扩展操作，会基于原哈希表创建一个大小等于 ht[0].used*2的哈希表ht[1]。相反如果执行的是收缩操作，每次收缩是根据已使用空间缩小一倍创建一个新的哈希表ht[1]。重新利用上面的哈希算法，计算索引值，然后将键值对放到新的哈希表位置上。 所有键值对都迁徙完毕后，释放原哈希表的内存空间。
触发扩容的条件：
服务器目前没有执行 BGSAVE命令或者BGREWRITEAOF命令，并且负载因子大于等于1。服务器目前正在执行 BGSAVE命令或者BGREWRITEAOF命令，并且负载因子大于等于5。
因为在执行BGSAVE命令或BGREWRITEAOF命令的过程中，Redis需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制（ copy-on-write）技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可能地避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要的内存写入操作，最大限度地节约内存。
ps：负载因子 = 哈希表已保存节点数量 / 哈希表大小。和Java HashMap类似。
int htNeedsResize(dict *dict) {
long long size, used;
size = dictSlots(dict);
used = dictSize(dict);
//当used的容量小于总hash槽总数的1/10的时候，返回true，最小为4
return (size > DICT_HT_INITIAL_SIZE &&
(used*100/size < HASHTABLE_MIN_FILL));
}
源码中提到当当前使用量小于容量1/10时，会进行收缩。
rehash源码如下：
// src/dict.c
int dictRehash(dict *d, int n) {
int empty_visits = n*10; /* Max number of empty buckets to visit. */
if (!dictIsRehashing(d)) return 0;
while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
/* Note that rehashidx can't overflow as we are sure there are more
* elements because ht[0].used != 0 */
assert(d->ht[0].size > (unsigned long)d->rehashidx);
while(d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
de = d->ht[0].table[d->rehashidx];
/* Move all the keys in this bucket from the old to the new hash HT */
while(de) {
uint64_t h;
nextde = de->next;
//获取在新的hash表的位置
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
//采用头插法
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}
/* Check if we already rehashed the whole table... */
// 如果ht[0]已经全部迁移到ht[1]，销毁ht[0]，将ht[1]赋值给ht[0]，重置ht[1]
if (d->ht[0].used == 0) {
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}
/* More to rehash... */
return 1;
}
rehash图如下：
如果ht[0]的节点数量非常多，导致一次rehash需要非常长的时间，这样就会影响客户端操作响应时间，因此使用渐进式rehash可以解决这个问题
渐进式rehash，即在上述rehash过程中，根据源码可以看到，可能随时暂停，因为需要响应客户端的操作。相比之下需要多维持一个rehashidx来表示rehash工作正在进行中。
渐进式rehash 的好处在于它采取分而治之的方式，将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的庞大计算量。
具体来说就是在渐进式rehash期间，如果有删改查操作时，如果index大于rehashindex，访问ht[0]，否则访问ht[1]。对于添加操作来说，只会在ht[1]上添加，可以避免一次复制。
2.4 Set
Redis的集合（Set）有两种实现：整数集合(IntSet)和哈希表hashtable.
当集合保存的元素都是整数值时会采用IntSet，当集合对象保存的元素数量超过512时会转为 Dict保存，数据作为key，对应的Value都为null，类似Java的HashSet实现。
2.4.1 整数集合IntSet
// src/intset.h
typedef struct intset {
// 编码方式
uint32_t encoding;
// 集合包含的元素数量
uint32_t length;
// 保存元素的数组
int8_t contents[];
} intset;
encoding 有多种编码：INTSET_ENC_INT16、INTSET_ENC_INT32 等,区别在于int字节数不同，表示的数的范围也不同。
2.4.2 IntSet扩容
IntSet扩容和普通数组扩容有一点区别，区别在于编码。
例如有一个IntSet有INT16整数1,2,3，现在需要往里面添加一个INT32整数65535。就与IntSet的encoding不符合了，需要进行升级（将所有INT16的整数升级为INT32）。
步骤如下：
计算所需的位数。原来占用的位数： 16*3 = 48位，都升级为INT32后占用的位数：32*4 = 128位，所以将数组空间开辟至128位。除新分配空间（96-127位）外，从后往前依次将原来的整数升级为 INT32在96-127位间添加 65535。encoding也修改为INTSET_ENC_INT32
因为需要对每个元素都进行提升移位，所以IntSet添加新元素的时间复杂度为O(n)
升级前后对比图如下：
类型的自动提升可以非常灵活地保存数据，并且可以减少不必要的内存浪费。
注意的是IntSet只支持升级，不支持降级，一旦升级以后就会至少保持当前状态。
2.5 Sorted Set（ZSet）
ZSet是Redis中的有序集合。它的实现也有两种数据结构：压缩列表ziplist和跳表skiplist，可以看到
当zset中的元素数量大于最大值128或所有元素长度大于64字节时，会使用跳表skiplist作为底层实现，否则使用压缩列表ziplist实现。
下面演示为了显示效果，将第二项配置改为6个字节。
2.5.1 压缩列表 ZipList
压缩列表时Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构。
zlbytes[4 字节]:压缩列表占用字节数。zltail[4 字节]: 表尾节点距离起始地址有多少字节，无需遍历即可确定表尾地址。zllen[2 字节]:包含的节点数量。entry[不定]: 节点Entryzlend[1 字节]:标记压缩列表末端。
如下压缩列表：
表示这个压缩列表包含5个节点(0x5)总长210字节(0xd2),从起始地址p后移179字节（0xb3）就可以到达最后一个元素。
一个直观的图表示压缩列表如下：
下面是Entry的结构：
其中第一项previous_entry_length表示前一个entry的长度。所以用当前地址减去第一项即可得到前一项的地址，实现从后往前遍历。
如果前一节点的长度 小于254字节，那么previous_entry_length属性需要用1字节长的空间来保存这个长度值。如果前一节点的长度 大于等于254字节，那么previous_entry_length属性需要用5字节长的空间来保存这个长度值。
一个存储"hello world"的Entry结构如下：
每个Entry可以保存一个字节数组或一个整数值。
// src/ziplist.h
/* Each entry in the ziplist is either a string or an integer. */
typedef struct {
/* When string is used, it is provided with the length (slen). */
unsigned char *sval;
unsigned int slen;
/* When integer is used, 'sval' is NULL, and lval holds the value. */
long long lval;
} ziplistEntry;
虽然最坏复杂度为O(n^2)，但是造成性能问题的几率是比较低的，要同时满足下面的条件才会全部连锁 更新：
所以ziplistpush等命令的平均时间复杂度为O(n)，可以放心使用。
因为我们发现压缩列表相比普通的数组或列表，既节省内存、减少内存碎片的产生又方便，所以也可以将其作为哈希表的底层实现。
所以ZSet的实现只需要在zipList基础上进行排序去重即可。
但ZipList也有缺点：
所以ZipList只作为数据量小时的一种很好的替代方案。数据量大的时候就需要用到跳表SkipList
2.5.2 跳表 SkipList
跳跃表（ skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找，还可以通过顺序性操作来批量处理节点。
在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单,所以有不少程序都使用跳跃表来代替平衡树。
跳表定义如下：
typedef struct zskiplistNode {
//层
struct zskiplistLevel{
//前进指针
struct zskiplistNode *forward;
//跨度
unsigned int span;
}level[];
//后退指针
struct zskiplistNode *backward;
//分值
double score;
//成员对象
robj *obj;
} zskiplistNode
特性：
由很多层结构组成； 每一层都是一个有序的链表，排列顺序为由高层到底层，都至少包含两个链表节点，分别是前面的head节点和后面的nil节点； 最底层的链表包含了所有的元素； 如果一个元素出现在某一层的链表中，那么在该层之下的链表也全都会出现（上一层的元素是当前层的元素的子集）； 链表中的每个节点都包含两个指针，一个指向同一层的下一个链表节点，另一个指向下一层的同一个链表节点；
对照图理解更直观：
跳表的思想类似二分法和多级索引，下一层的节点都比上一层多（非二分之一），查询非常快且有序。
2.5.3跳表的时间复杂度和空间复杂度
所以可以得到跳表查询的时间复杂度为：\(O(log_n)\)，媲美二分查找。
对于跳表的空间复杂度，可以得到总共所需的节点数= \(n +\dfrac{n}{2} + \dfrac{n}{4} + \dfrac{n}{8} + ··· \approx(2n)\)
跳表不仅支持查询，而且还支持\(O(log_n)\)级别的插入和删除操作。性能媲美红黑树。
类似红黑树，二叉平衡树是通过左右旋来保持左右子树的大小平衡，而跳表是借助随机函数来更新索引结构。
通过一个随机函数来决定，比如通过 随机函数得到某个值 K, 那么就将这个节点添加到第二层到第K层节点中，避免出现极端情况退化为单链表。
相比红黑树，跳表也更善于进行区间查询，查询到节点后只需要顺序输出即可，类似B+树作为数据库区间查询的过程，而且比红黑树更容易实现。
总之，跳表有着二分查找的性能，红黑树的插入删除效率，和B+树的区间查询效率，且简单灵活，非常强大。
跳表的缺点我认为就是使用了一些冗余的节点来表示同一个元素，不过影响也不大。
三、数据结构关系总结
五种数据结构及其底层数据结构关系图如下所示，编码类型即 OBJECT ENCODING 的值。
四 Redis 实战
Redis 博大精深，然而很多时候我们说到 Redis，却只知道缓存或者分布式锁，面试的时候也只能从这两个角度去准备。
但是在实际面试中，Redis 这块能够发挥的地方可太多了：
Redis 中 String 类型使用了什么样的数据结构？ 为什么每种数据类型几乎都设计了两种以上的数据结构？ 为什么要延迟双删？原因是什么 RedLock 解决了什么问题，为什么现在又被废弃了？现在用什么？ watchdog 什么情况下会失效？ Redis 挂了怎么办？ 如何实现百万级排行榜？ 。。。
还有很多，我就不一一列举了。
所以松哥今年出了一个 Redis 课程，取名就叫《Redis-不止缓存》，希望能和大家分享一下 Redis 在缓存这个领域之外的一些用法。
这套课程基于目前最新版的 Redis7 录制，从基本用法到原理分析讲了很多，大伙来看下目录：
课程有配套的源码和笔记，同时为了确保大家确确实实能够学会并且掌握 Redis，也提供了答疑群，实时解答课程相关的问题。
课程原价 799，限时 499。
五 关于松哥
9 年程序员生涯，Java畅销书作者，华为云最具价值专家，华为开发者社区之星，GitHub 知名项目作者。
目前产品有 Java项目课程、Java简历指导、1V1模拟面试等，如有需求欢迎来勾搭。
感兴趣小伙伴加微信备注 Redis
文章地址：
https://retainblog.top/2022/09/28/Redis%E4%BA%94%E5%A4%A7%E5%9F%BA%E6%9C%AC%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B%E5%BA%95%E5%B1%82%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E8%AF%A6%E8%A7%A3/
