Redis之五大基础数据类型

Redis 共有 5 种基本数据类型：String（字符串）、List（列表）、Set（集合）、Hash（散列）、Zset（有序集合）。

这 5 种数据类型是直接提供给用户使用的，是数据的保存形式，其底层实现主要依赖这 8 种数据结构：

简单动态字符串（SDS）、LinkedList（双向链表）、Dict（哈希表/字典）、SkipList（跳跃表）、Intset（整数集合）、ZipList（压缩列表）、QuickList（快速列表）

Redis底层通过C语言实现了这些数据结构，这些源码在Redis官网可以下载

我们发现基础数据类型都有对应的C语言文件

Redis是key-value存储系统，key一般为string类型的字符串，value是redis对象(object)

从上帝视角看看简单的set k1 v1

1.启动Redis server

2.形成redisdb

3.形成字典存储哈希键值对对象

4.指向5大基础数据类型后由对应底层数据结构完成实现

Redis借鉴了Java中对象的思想，定义了redisObject结构体来表示string，hash，list，set，zset

redis中每一个键值对都会有一个dictEntry

在dictEntry中的v指向对应的redisObject

键值对是如何存储并读取达到o（1）复杂度？

1.启动redis server后就会加载redisDb

2.redisDb加载进内存形成数据库

3.数据库读dict字典，形成字典后找哈希表

4.其中每一个kv键值对形成结构体dictEntry

5.dictEntry封装后形成redisObject

6.最终操作的是redisObject

redisObject+redis数据类型+redis编码方式的关系

redis6之前的数据类型和数据结构的关系

redis7的数据类型和数据结构的关系

从简单的set hello world说起

因为Redis是KV键值对的数据库，每个键值对都会有一个dictEntry(源码位置：dict.h)，里面指向了key和value的指针，next 指向下一个 dictEntry。

key 是字符串，但是 Redis 没有直接使用 C 的字符数组，而是存储在redis自定义的 SDS中。

value 既不是直接作为字符串存储，也不是直接存储在 SDS 中，而是存储在redisObject 中。

实际上五种常用的数据类型的任何一种，都是通过 redisObject 来存储的。

redisObject的作用

为了便于操作，Redis采用redisObjec结构来统一五种不同的数据类型，这样所有的数据类型就都可以以相同的形式在函数间传递而不用使用特定的类型结构。

同时，为了识别不同的数据类型，redisObjec中定义了type和encoding字段对不同的数据类型加以区别。简单地说，redisObjec就是string、hash、list、set、zset的父类，可以在函数间传递时隐藏具体的类型信息，所以作者抽象了redisObjec结构来到达同样的目的。

redisObject中各个字段的含义

五大基础数据类型结构解析

各个类型的数据结构的编码映射和定义

String

三种编码方式

int：保存long的64位（8个字节）长整形有符号整数（-2^63~263-1）

只有整数才会使用int 如果是浮点数，redis内部将其转为字符串后再存储

embstr：代表embstr格式的SDS（simple dynamic string 简单动态字符），保存小于44字节的字符串

embeded string 嵌入的字符串

raw：保存长度大于44字节的字符串

SDS（简单动态字符串）

SDS 是什么？

相信大家都学过 C 语言，对 C 中的字符串已经比较清楚了；在 C 中，如果我们要存储一个字符串，可以先定义一个字符数组 char[] 或者 char *p ，然后将字符串挨个存进去。

这种方式存在什么问题？

当我们想要获取字符串的实际长度时，需要遍历整个字符串 char[]；你可能觉得单次操作性能应该还行，然而 redis 服务的是以万+ 的QPS，这种操作就有些问题了。

显然，直接用 C 中的字符串不太现实，但可以在其之上，做一层数据结构封装，一款适用于高并发场景下，能高效的解决 C 字符串缺陷的特殊结构，这就是 SDS。

SDS 既然是字符串，那么首先需要一个字符串指针；为了方便上层的接口调用，该结构还需要记录一些关键信息，如当前数据长度和剩余容量等，数据结构如下：

struct sdshdr {
    unsigned int len;
    unsigned int free;
    char buf[];
};

其中，len 表示当前字符串长度、free 表示剩余可用空间、buf[] 存储实际数据。

值得注意的是，以上结构是 redis3.2 版本之前的结构，3.2 已经做出了些许调整；至于原因，咱们继续往后看 ～

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

遵循空字符结尾这一惯例的好处是， SDS 可以直接重用一部分 C 字符串函数库里面的函数。

SDS 与 C 字符串的区别

根据传统， C 语言使用长度为 N+1 的字符数组来表示长度为 N 的字符串， 并且字符数组的最后一个元素总是空字符 ‘\0’ 比如：

C 语言使用的这种简单的字符串表示方式， 并不能满足 Redis 对字符串在安全性、效率、以及功能方面的要求， 本节接下来的内容将详细对比 C 字符串和 SDS 之间的区别， 并说明 SDS 比 C 字符串更适用于 Redis 的原因。

常数复杂度获取字符串长度

因为 C 字符串并不记录自身的长度信息， 所以为了获取一个 C 字符串的长度， 程序必须遍历整个字符串， 对遇到的每个字符进行计数， 直到遇到代表字符串结尾的空字符为止， 这个操作的复杂度为 O(N) 。

和 C 字符串不同， 因为 SDS 在 len 属性中记录了 SDS 本身的长度， 所以获取一个 SDS 长度的复杂度仅为 O(1) 。

设置和更新 SDS 长度的工作是由 SDS 的 API 在执行时自动完成的， 使用 SDS 无须进行任何手动修改长度的工作。

通过使用 SDS 而不是 C 字符串， Redis 将获取字符串长度所需的复杂度从 O(N) 降低到了 O(1) ， 这确保了获取字符串长度的工作不会成为 Redis 的性能瓶颈。

比如说， 因为字符串键在底层使用 SDS 来实现， 所以即使我们对一个非常长的字符串键反复执行 STRLEN 命令， 也不会对系统性能造成任何影响， 因为 STRLEN 命令的复杂度仅为 O(1) 。

杜绝缓冲区溢出

C 字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出（buffer overflow），分配内存空间超过后，会导致数组下标越级或者内存分配溢出

与 C 字符串不同， SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性： 当 SDS API 需要对 SDS 进行修改时， API 会先检查 SDS 的空间是否满足修改所需的要求， 如果不满足的话， API 会自动将 SDS 的空间扩展至执行修改所需的大小， 然后才执行实际的修改操作， 所以使用 SDS 既不需要手动修改 SDS 的空间大小， 也不会出现前面所说的缓冲区溢出问题

减少修改字符串时带来的内存重分配次数

因为 C 字符串并不记录自身的长度， 所以对于一个包含了 N 个字符的 C 字符串来说， 这个 C 字符串的底层实现总是一个 N+1 个字符长的数组（额外的一个字符空间用于保存空字符）。

因为 C 字符串的长度和底层数组的长度之间存在着这种关联性， 所以每次增长或者缩短一个 C 字符串， 程序都总要对保存这个 C 字符串的数组进行一次内存重分配操作：

• 如果程序执行的是增长字符串的操作， 比如拼接操作（append）， 那么在执行这个操作之前， 程序需要先通过内存重分配来扩展底层数组的空间大小 —— 如果忘了这一步就会产生缓冲区溢出。
• 如果程序执行的是缩短字符串的操作， 比如截断操作（trim）， 那么在执行这个操作之后， 程序需要通过内存重分配来释放字符串不再使用的那部分空间 —— 如果忘了这一步就会产生内存泄漏。

因为内存重分配涉及复杂的算法， 并且可能需要执行系统调用， 所以它通常是一个比较耗时的操作：

• 在一般程序中， 如果修改字符串长度的情况不太常出现， 那么每次修改都执行一次内存重分配是可以接受的。
• 但是 Redis 作为数据库， 经常被用于速度要求严苛、数据被频繁修改的场合， 如果每次修改字符串的长度都需要执行一次内存重分配的话， 那么光是执行内存重分配的时间就会占去修改字符串所用时间的一大部分， 如果这种修改频繁地发生的话， 可能还会对性能造成影响。

为了避免 C 字符串的这种缺陷， SDS 通过未使用空间解除了字符串长度和底层数组长度之间的关联： 在 SDS 中， buf 数组的长度不一定就是字符数量加一， 数组里面可以包含未使用的字节， 而这些字节的数量就由 SDS 的 free 属性记录。

通过未使用空间， SDS 实现了空间预分配和惰性空间释放两种优化策略。

空间预分配

SDS 修改后，len 长度小于 1M，那么将会额外分配与 len 相同长度的未使用空间。如果修改后长度大于 1M，那么将分配1M的使用空间。

惰性空间释放

有空间分配对应的就有空间释放。SDS 缩短时并不会回收多余的内存空间，而是使用 free 字段将多出来的空间记录下来。如果后续有变更操作，直接使用 free 中记录的空间，减少了内存的分配。

二进制安全

C 字符串中的字符必须符合某种编码（比如 ASCII）， 并且除了字符串的末尾之外， 字符串里面不能包含空字符， 否则最先被程序读入的空字符将被误认为是字符串结尾 —— 这些限制使得 C 字符串只能保存文本数据， 而不能保存像图片、音频、视频、压缩文件这样的二进制数据。

虽然数据库一般用于保存文本数据， 但使用数据库来保存二进制数据的场景也不少见， 因此， 为了确保 Redis 可以适用于各种不同的使用场景， SDS 的 API 都是二进制安全的（binary-safe）： 所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据， 程序不会对其中的数据做任何限制、过滤、或者假设 —— 数据在写入时是什么样的， 它被读取时就是什么样。

这也是我们将 SDS 的 buf 属性称为字节数组的原因 —— Redis 不是用这个数组来保存字符， 而是用它来保存一系列二进制数据。

比如说， 使用 SDS 来保存之前提到的特殊数据格式就没有任何问题， 因为 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束

	C语言	SDS
字符串长度处理	需要从头开始遍历，直到遇到 ‘\0’ 为止，时间复杂度O(N)	记录当前字符串的长度，直接读取即可，时间复杂度 O(1)
内存重新分配	分配内存空间超过后，会导致数组下标越级或者内存分配溢出	空间预分配SDS 修改后，len 长度小于 1M，那么将会额外分配与 len 相同长度的未使用空间。如果修改后长度大于 1M，那么将分配1M的使用空间。惰性空间释放有空间分配对应的就有空间释放。SDS 缩短时并不会回收多余的内存空间，而是使用 free 字段将多出来的空间记录下来。如果后续有变更操作，直接使用 free 中记录的空间，减少了内存的分配。
二进制安全	二进制数据并不是规则的字符串格式，可能会包含一些特殊的字符，比如 ‘\0’ 等。前面提到过，C中字符串遇到 ‘\0’ 会结束，那 ‘\0’ 之后的数据就读取不上了	根据 len 长度来判断字符串结束的，二进制安全的问题就解决了

SDS API

创建SDS

Redis 通过sdsnewlen方法创建 SDS。在方法中会根据字符串初始化长度选择合适的类型。

sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    void *sh;
    sds s;
    // 根据初始化长度判断 SDS 的类型
    char type = sdsReqType(initlen);
    // SDS_TYPE_5 强制转换为 SDS_TYPE_8
    // 这样侧面验证了 sdshdr5 从未被使用，创建这一步就GG了 ੯ੁૂ‧̀͡u\
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    // 获取头部大学
    int hdrlen = sdsHdrSize(type);
    // 指向 flags 的指针
    unsigned char *fp; /* flags pointer. */
    // 分配的空间
    size_t usable;
    // 防止溢出
    assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
    // 分配空间
    // s_trymalloc_usable: 尝试分配内存，失败则返回NULL
    // s_malloc_usable: 分配内存或者抛异常[不友好]
    sh = trymalloc?
        s_trymalloc_usable(hdrlen+initlen+1, &usable) :
        s_malloc_usable(hdrlen+initlen+1, &usable);
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    // s 此时指向buf
    s = (char*)sh+hdrlen;
    // 指向flags
    fp = ((unsigned char*)s)-1;
    usable = usable-hdrlen-1;
    // 对不同类型的 SDS 可分配空间进行截断
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        // ... 省略
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    // 末尾添加\0
    s[initlen] = '\0';
    return s;
}

通过sdsnewlen方法我们可以获得以下信息：

• SDS_TYPE_5 会被强制转换为 SDS_TYPE_8 类型；
• 创建时默认会在末尾加'\0'；
• 返回值是指向 SDS 结构中 buf 的指针；
• 返回值是char *sds类型，可以兼容部分C函数。

释放SDS

为了优化性能，SDS 提供了不直接释放内存，而是通过重置len达到清空 SDS 目的的方法——sdsclear。改方法仅仅将 SDS 的len归零，而buf的空间并为真正被清空，新的数据可以复写，而不用重新申请内存。

void sdsclear(sds s) {
    sdssetlen(s, 0);// 设置len为0
    s[0] = '\0';//“清空”buf
}

若真正想清空 SDS 则可以调用sdsfree方法，底层通过调用s_free释放内存。

void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[-1]));
}

set方法

set k1 123

当字符串键值的内容可以用一个64位有符号整形来表示时，Redis会将键值转化为long型来进行存储，此时即对应 OBJ_ENCODING_INT 编码类型。内部的内存结构表示如下:

Redis 启动时会预先建立 10000 个分别存储 0~9999 的 redisObject 变量作为共享对象，这就意味着如果 set字符串的键值在 0~10000 之间的话，则可以

直接指向共享对象 而不需要再建立新对象，此时键值不占空间！

set k1 123

set k2 123

set k1 abc

对于长度小于 44的字符串，Redis 对键值采用OBJ_ENCODING_EMBSTR 方式，EMBSTR 顾名思义即：embedded string，表示嵌入式的String。从内存结构上来讲 即字符串 sds结构体与其对应的 redisObject 对象分配在同一块连续的内存空间，字符串sds嵌入在redisObject对象之中一样。

set k1 长度大于44的字符串

当字符串的键值为长度大于44的超长字符串时，Redis 则会将键值的内部编码方式改为OBJ_ENCODING_RAW格式，这与OBJ_ENCODING_EMBSTR编码方式的不同之处在于，此时动态字符串sds的内存与其依赖的redisObject的内存不再连续了

如果修改字符串，明明没有达到阈值，编码却改为了row

判断不出来，就取最大Raw

流程图

总结：

只有整数才会使用 int，如果是浮点数， Redis 内部其实先将浮点数转化为字符串值，然后再保存。

embstr 与 raw 类型底层的数据结构其实都是 SDS (简单动态字符串，Redis 内部定义 sdshdr 一种结构)。

那这两者的区别见下图：

1 int	Long类型整数时，RedisObject中的ptr指针直接赋值为整数数据，不再额外的指针再指向整数了，节省了指针的空间开销。
2 embstr	当保存的是字符串数据且字符串小于等于44字节时，embstr类型将会调用内存分配函数，只分配一块连续的内存空间，空间中依次包含 redisObject 与 sdshdr 两个数据结构，让元数据、指针和SDS是一块连续的内存区域，这样就可以避免内存碎片
3 raw	当字符串大于44字节时，SDS的数据量变多变大了，SDS和RedisObject布局分家各自过，会给SDS分配多的空间并用指针指向SDS结构，raw 类型将会调用两次内存分配函数，分配两块内存空间，一块用于包含 redisObject结构，而另一块用于包含 sdshdr 结构

redis内部会根据用户给的不同的键值而使用不同的编码格式，而这一切都对用户透明

Hash

redis6

hash-max-ziplist-entries：使用压缩列表保存时哈希集合中的最大元素个数。

hash-max-ziplist-value：使用压缩列表保存时哈希集合中单个元素的最大长度。

Hash类型键的字段个数 小于 hash-max-ziplist-entries 并且每个字段名和字段值的长度 小于 hash-max-ziplist-value 时，Redis才会使用 OBJ_ENCODING_ZIPLIST来存储该键，前述条件任意一个不满足则会转换为 OBJ_ENCODING_HT的编码方式

1.哈希对象保存的键值对数量小于512个

2.所有的键值对的键和值都小于64byte时用ziplist，否则使用hashtable

一旦从压缩列表转为了哈希表，Hash类型就会一直用哈希表进行保存而不会再转回压缩列表了。

在节省内存空间方面哈希表就没有压缩列表高效了。

流程：

t_hash.c

在redis中，hashtable被称为字典（dictionary），它是一个数组+链表

OBJ_ENCODING_HT 这种编码方式内部才是真正的哈希表结构，或称为字典结构，其可以实现O(1)复杂度的读写操作，因此效率很高。

在 Redis内部，从 OBJ_ENCODING_HT类型到底层真正的散列表数据结构是一层层嵌套下去的，组织关系见面图：

字典：dict（dictht+type）

哈希表：dictht（dictEntry）

哈希条目：dictEntry（key+value key：string value：redisObject）

hset

编码方式的判断和转换

ziplist.c

Ziplist 压缩列表是一种紧凑编码格式，总体思想是多花时间来换取节约空间，即以部分读写性能为代价，来换取极高的内存空间利用率，

因此只会用于 字段个数少，且字段值也较小 的场景。压缩列表内存利用率极高的原因与其连续内存的特性是分不开的。

为了节约内存而开发的，它是由连续内存块组成的顺序型数据结构，有点类似于数组

ziplist是一个经过特殊编码的双向链表，它不存储指向前一个链表节点prev和指向下一个链表节点的指针next而是存储上一个节点长度和当前节点长度，通过牺牲部分读写性能，来换取高效的内存空间利用率，节约内存，是一种时间换空间的思想。只用在字段个数少，字段值小的场景里面

ziplist的各个单元的含义

在Java中有hashMap结构，底层是由数组+链表+红黑树组成，其中数组中存储我们的数据，Java为我们封装了一个静态内部类Node来封装我们的KV，所以是一个Node类型的数组

对比于redis的哈希结构，也在内部为我们封装了一种特有的数据结构来存储我们的KV键值对，为zlentry

属性含义

压缩列表zlentry节点结构：每个zlentry由前一个节点的长度、encoding和entry-data三部分组成

前节点：(前节点占用的内存字节数)表示前1个zlentry的长度，privious_entry_length有两种取值情况：1字节或5字节。取值1字节时，表示上一个entry的长度小于254字节。虽然1字节的值能表示的数值范围是0到255，但是压缩列表中zlend的取值默认是255，因此，就默认用255表示整个压缩列表的结束，其他表示长度的地方就不能再用255这个值了。所以，当上一个entry长度小于254字节时，prev_len取值为1字节，否则，就取值为5字节。记录长度的好处：占用内存小，1或者5个字节

enncoding：记录节点的content保存数据的类型和长度。

content：保存实际数据内容

为什么entry这么设计？记录前一个节点的长度？

链表在内存中，一般是不连续的，遍历相对比较慢，而ziplist可以很好的解决这个问题。如果知道了当前的起始地址，因为entry是连续的，entry后一定是另一个entry，想知道下一个entry的地址，只要将当前的起始地址加上当前entry总长度。如果还想遍历下一个entry，只要继续同样的操作。

压缩链表为什么优于链表

1 普通的双向链表会有两个指针，在存储数据很小的情况下，我们存储的实际数据的大小可能还没有指针占用的内存大，得不偿失。ziplist 是一个特殊的双向链表没有维护双向指针:previous next；而是存储上一个 entry的长度和当前entry的长度，通过长度推算下一个元素在什么地方。牺牲读取的性能，获得高效的存储空间，因为(简短字符串的情况)存储指针比存储entry长度更费内存。这是典型的“时间换空间”。

2 链表在内存中一般是不连续的，遍历相对比较慢而ziplist可以很好的解决这个问题，普通数组的遍历是根据数组里存储的数据类型找到下一个元素的(例如int类型的数组访问下一个元素时每次只需要移动一个sizeof(int)就行)，但是ziplist的每个节点的长度是可以不一样的，而我们面对不同长度的节点又不可能直接sizeof(entry)，所以ziplist只好将一些必要的偏移量信息记录在了每一个节点里，使之能跳到上一个节点或下一个节点。

备注:sizeof实际上是获取了数据在内存中所占用的存储空间，以字节为单位来计数。

3 头节点里有头节点里同时还有一个参数 len，和string类型提到的 SDS 类似，这里是用来记录链表长度的。因此获取链表长度时不用再遍历整个链表，直接拿到len值就可以了，这个时间复杂度是 O(1)

小结

ziplist为了节省内存，采用了紧凑的连续存储。

ziplist是一个双向链表，可以在时间复杂度为 O(1) 下从头部、尾部进行 pop 或 push。

新增或更新元素可能会出现连锁更新现象(致命缺点导致被listpack替换)。

不能保存过多的元素，否则查询效率就会降低，数量小和内容小的情况下可以使用。

redis7

listpack

hash-max-listpack-entries：使用压缩列表保存时哈希集合中的最大元素个数。

hash-max-listpack-value：使用压缩列表保存时哈希集合中单个元素的最大长度。

Hash类型键的字段个数 小于 hash-max-listpack-entries且每个字段名和字段值的长度 小于 hash-max-listpack-value 时，

Redis才会使用OBJ_ENCODING_LISTPACK来存储该键，前述条件任意一个不满足则会转换为 OBJ_ENCODING_HT的编码方式

还保留了ziplist保证版本兼容，但实际起作用的是listpack

第一步：创建hash对象（创建listpack并创建obj设置编码方式）

第二步：创建listpack

lpNew 函数创建了一个空的 listpack，一开始分配的大小是 LP_HDR_SIZE 再加 1 个字节。LP_HDR_SIZE 宏定义是在 listpack.c 中，它默认是 6 个字节，其中 4 个字节是记录 listpack 的总字节数，2 个字节是记录 listpack 的元素数量。此外，listpack 的最后一个字节是用来标识 **listpack 的结束，**其默认值是宏定义 LP_EOF。和 ziplist 列表项的结束标记一样，LP_EOF 的值也是 255（0xFF）

第三步：

紧凑列表为什么优于压缩列表

ziplist的连锁更新问题

压缩列表新增某个元素或修改某个元素时，如果空间不不够，压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时，可能会导致后续元素的 prevlen 占用空间都发生变化，从而引起「连锁更新」问题，导致每个元素的空间都要重新分配，造成访问压缩列表性能的下降。

案例说明：压缩列表每个节点正因为需要保存前一个节点的长度字段，就会有连锁更新的隐患

第一步：现在假设一个压缩列表中有多个连续的、长度在 250～253 之间的节点，如下图：

因为这些节点长度值小于 254 字节，所以 prevlen 属性需要用 1 字节的空间来保存这个长度值，一切OK，O(∩_∩)O哈哈~

第二步：这时，如果将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点，即新节点将成为entry1的前置节点，如下图：

因为entry1节点的prevlen属性只有1个字节大小，无法保存新节点的长度，此时就需要对压缩列表的空间重分配操作并将entry1节点的prevlen 属性从原来的 1 字节大小扩展为 5 字节大小。

第三步：连续更新问题出现

entry1节点原本的长度在250～253之间，因为刚才的扩展空间，此时entry1节点的长度就大于等于254，因此原本entry2节点保存entry1节点的 prevlen属性也必须从1字节扩展至5字节大小。entry1节点影响entry2节点，entry2节点影响entry3节点…一直持续到结尾。这种在特殊情况下产生的连续多次空间扩展操作就叫做「连锁更新」

listpack 是 Redis 设计用来取代掉 ziplist 的数据结构，它通过每个节点记录自己的长度且放在节点的尾部，来彻底解决掉了 ziplist 存在的连锁更新的问题

listpack结构

Total Bytes	为整个listpack的空间大小，占用4个字节，每个listpack最多占用4294967295Bytes。
num-elements	为listpack中的元素个数，即Entry的个数占用2个字节
element-1~element-N	为每个具体的元素
listpack-end-byte	为listpack结束标志，占用1个字节，内容为0xFF。

相比于ziplist

ziplist VS listpack

ziplist

和ziplist 列表项类似，listpack 列表项也包含了元数据信息和数据本身。不过，为了避免ziplist引起的连锁更新问题，listpack 中的每个列表项

不再像ziplist列表项那样保存其前一个列表项的长度。

list

Java中有ArrayList底层是由Object[]实现，LinkedList底层是由放入Node节点的双端链表实现

redis中的list我们学习redis6和7两个版本

redis6：quicklist+ziplist

redis7：quicklist+listpack

redis6

(1) ziplist压缩配置：list-compress-depth 0

​ 表示一个quicklist两端不被压缩的节点个数。这里的节点是指quicklist双向链表的节点，而不是指ziplist里面的数据项个数

参数list-compress-depth的取值含义如下：

0: 是个特殊值，表示都不压缩。这是Redis的默认值。

1: 表示quicklist两端各有1个节点不压缩，中间的节点压缩。

2: 表示quicklist两端各有2个节点不压缩，中间的节点压缩。

3: 表示quicklist两端各有3个节点不压缩，中间的节点压缩。

依此类推…

(2) ziplist中entry配置：list-max-ziplist-size -2

当取正值的时候，表示按照数据项个数来限定每个quicklist节点上的ziplist长度。比如，当这个参数配置成5的时候，表示每个quicklist节点的ziplist最多包含5个数据项。当取负值的时候，表示按照占用字节数来限定每个quicklist节点上的ziplist长度。这时，它只能取-1到-5这五个值，

每个值含义如下：

-5: 每个quicklist节点上的ziplist大小不能超过64 Kb。（注：1kb => 1024 bytes）

-4: 每个quicklist节点上的ziplist大小不能超过32 Kb。

-3: 每个quicklist节点上的ziplist大小不能超过16 Kb。

-2: 每个quicklist节点上的ziplist大小不能超过8 Kb。（-2是Redis给出的默认值）

-1: 每个quicklist节点上的ziplist大小不能超过4 Kb。

在Redis3.0之前，list采用的底层数据结构是ziplist压缩列表+linkedList双向链表

然后在高版本的Redis中底层数据结构是quicklist(替换了ziplist+linkedList)，而quicklist也用到了ziplist

结论：quicklist就是「双向链表 + 压缩列表」组合，因为一个 quicklist 就是一个链表，而链表中的每个元素又是一个压缩列表

quicklist 实际上是 zipList 和 linkedList 的混合体，它将 linkedList按段切分，每一段使用 zipList 来紧凑存储，多个 zipList 之间使用双向指针串接起来。

quicklist

quicklist中*zl指向一个ziplist，一个ziplist可以存放多个元素

redis7

listpack紧凑列表

是用来替代 ziplist 的新数据结构，在 7.0 版本已经没有 ziplist 的配置了（6.0版本仅部分数据类型作为过渡阶段在使用）

t_list.c

创建object对象

发现6和7底层都是创建quicklist（但6的quicklist装ziplist，但7装的是listpack）

set

Redis用intset或hashtable存储set。如果元素都是整数类型，就用intset存储。

如果不是整数类型，就用hashtable（数组+链表的存来储结构）。key就是元素的值，value为null。

zset

redis6

ziplist+skiplist

当有序集合中包含的元素数量超过服务器属性 server.zset_max_ziplist_entries 的值（默认值为 128 ），

或者有序集合中新添加元素的 member 的长度大于服务器属性 server.zset_max_ziplist_value 的值（默认值为 64 ）时，

redis会使用跳跃表作为有序集合的底层实现。

否则会使用ziplist作为有序集合的底层实现

redis7

listpack+skiplist

当有序集合中包含的元素数量超过服务器属性 server.zset_max_listpack_entries 的值（默认值为 128 ），

或者有序集合中新添加元素的 member 的长度大于服务器属性 server.zset_max_listpack_value 的值（默认值为 64 ）时，

redis会使用跳跃表作为有序集合的底层实现。

否则会使用listpack作为有序集合的底层实现

跳表skiplist

相比于单链表

对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。

这样查找效率就会很低，时间复杂度会很高O(N)

解决方法：升维，也叫空间换时间。

从这个例子里，我们看出，加来一层索引之后，查找一个结点需要遍历的结点个数减少了，也就是说查找效率提高了。

skiplist是一种以空间换取时间的结构。

由于链表，无法进行二分查找，因此借鉴数据库索引的思想，提取出链表中关键节点（索引），先在关键节点上查找，再进入下层链表查找，提取多层关键节点，就形成了跳跃表
but

由于索引也要占据一定空间的，所以，索引添加的越多，空间占用的越多

优点：

跳表是一个最典型的空间换时间解决方案，而且只有在数据量较大的情况下才能体现出来优势。而且应该是读多写少的情况下才能使用，所以它的适用范围应该还是比较有限的

缺点：

维护成本相对要高，

在单链表中，一旦定位好要插入的位置，插入结点的时间复杂度是很低的，就是O(1)

but

新增或者删除时需要把所有索引都更新一遍，为了保证原始链表中数据的有序性，我们需要先找

到要动作的位置，这个查找操作就会比较耗时最后在新增和删除的过程中的更新，时间复杂度也是O(log n)

设计跳表：

class Skiplist {
    static final int MAX_LEVEL = 32;//节点最大的层数不允许超过MAX_LEVEL
    static final double P_FACTOR = 0.25;//如果一个节点有第i层(i>=1)指针（即节点已经在第1层到第i层链表中），那么它有第(i+1)层指针的概率为P_FACTOR
    //当P_FACTOR=1/4时，每个节点所包含的平均指针数目为1.33
    private SkiplistNode head;
    private int level;
    private Random random;

    public Skiplist() {
        this.head = new SkiplistNode(-1, MAX_LEVEL);
        this.level = 0;
        this.random = new Random();
    }
    //search：从跳表的当前的最大层数 level层开始查找，在当前层水平地逐个比较直至当前节点的下一个节点大于等于目标节点，然后移动至下一层进行查找，
    // 重复这个过程直至到达第 1 层。此时，若第 1 层的下一个节点的值等于 target，则返回 true；反之，则返回 false

    public boolean search(int target) {
        SkiplistNode curr = this.head;
        for (int i = level - 1; i >= 0; i--) {//从最高层开始找
            //当前层水平地逐个比较直至当前节点的下一个节点大于等于目标节点
            while (curr.forward[i] != null && curr.forward[i].val < target) {
                curr = curr.forward[i];
            }
        }
        curr = curr.forward[0];
        /* 检测当前元素的值是否等于 target */
        if (curr != null && curr.val == target) {
            return true;
        }
        return false;
    }

    public void add(int num) {
        SkiplistNode[] update = new SkiplistNode[MAX_LEVEL];
        Arrays.fill(update, head);
        SkiplistNode curr = this.head;
        for (int i = level - 1; i >= 0; i--) {
            /* 找到第 i 层小于且最接近 num 的元素*/
            while (curr.forward[i] != null && curr.forward[i].val < num) {
                curr = curr.forward[i];
            }
            update[i] = curr;
        }
        int lv = randomLevel();
        level = Math.max(level, lv);
        SkiplistNode newNode = new SkiplistNode(num, lv);
        for (int i = 0; i < lv; i++) {
            /* 对第 i 层的状态进行更新，将当前元素的 forward 指向新的节点 */
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }

    public boolean erase(int num) {
        SkiplistNode[] update = new SkiplistNode[MAX_LEVEL];
        SkiplistNode curr = this.head;
        for (int i = level - 1; i >= 0; i--) {
            /* 找到第 i 层小于且最接近 num 的元素*/
            while (curr.forward[i] != null && curr.forward[i].val < num) {
                curr = curr.forward[i];
            }
            update[i] = curr;
        }
        curr = curr.forward[0];
        /* 如果值不存在则返回 false */
        if (curr == null || curr.val != num) {
            return false;
        }
        for (int i = 0; i < level; i++) {
            if (update[i].forward[i] != curr) {
                break;
            }
            /* 对第 i 层的状态进行更新，将 forward 指向被删除节点的下一跳 */
            update[i].forward[i] = curr.forward[i];
        }
        /* 更新当前的 level */
        while (level > 1 && head.forward[level - 1] == null) {
            level--;
        }
        return true;
    }

    private int randomLevel() {
        int lv = 1;
        /* 随机生成 lv */
        while (random.nextDouble() < P_FACTOR && lv < MAX_LEVEL) {
            lv++;
        }
        return lv;
    }
}

class SkiplistNode {
    int val;
    SkiplistNode[] forward;

    public SkiplistNode(int val, int maxLevel) {
        this.val = val;
        this.forward = new SkiplistNode[maxLevel];
    }
}