Redis底层数据结构

Cutewr大约 27 分钟

Redis底层数据结构

SDS

String是 Redis 中最简单同时也是最常用的一个数据类型。String的底层数据结构实现是SDS。

虽然 Redis 是用 C 语言写的，但是 Redis 并没有使用 C 的字符串表示，而是自己构建了一种简单动态字符串（Simple Dynamic String，SDS）。相比于 C 的原生字符串，Redis 的 SDS 不光可以保存可以用来存储任何类型的数据而且还是二进制安全的，除此之外SDS API也更安全，不会造成缓冲区溢出。并且获取字符串长度复杂度为 O(1)（C 字符串为 O(N)）,

数据结构

sds数据结构包含了下面这 4 个属性，redis在C语言原本字符数组的基础上，增加了三个元数据len、alloc、flags；用来解决C语言字符串的缺陷：

len：字符串的长度，也就是已经使用的字节数
alloc：总共可用的字符空间大小，alloc-len 就是 SDS 剩余的空间大小
buf[]：字符数组，用来保存实际数据
flags：用于保存不同类型的SDS。分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32和sdshdr64

SDS优点

SDS 相比于 C 语言中的字符串有如下提升：

二进制安全：C 语言中的字符串以空字符 \0 作为字符串结束的标识，这存在一些问题，像一些二进制文件（比如图片、视频、音频）就可能包括“\0”，C 字符串无法正确保存。SDS 使用 len 属性判断字符串是否结束，不存在这个问题。
可以避免缓冲区溢出：C 语言中的字符串被修改（比如拼接）时，一旦没有分配足够长度的内存空间，就会造成缓冲区溢出。SDS 结构中会先根据alloc-len检查空间大小是否满足要求，如果不满足，则先扩展至所需大小再进行修改操作。（⼩于1MB翻倍扩容，⼤于1MB按1MB 扩容）
减少内存分配次数：C语言修改字符串时，每次都需要重新分配内存。SDS 实现了空间预分配和惰性空间释放两种优化策略。当 SDS 需要增加字符串时，Redis 会为 SDS 分配好多余的内存，这样可以减少内存分配次数。当 SDS 需要减少字符串时，这部分内存不会立即被回收，会被记录下来，等待后续使用（支持手动释放，有对应的 API）。
获取字符串长度的复杂度较低：C 语言中的字符串的长度通常是经过遍历计数来实现的，时间复杂度为 O(n)。SDS 的长度获取直接读取 len 属性即可，时间复杂度为 O(1)。
节省内存空间。
1）SDS 结构中的flags变量，表示的是 SDS 类型。不同类型的sds数据结构中的len和alloc成员变量的数据类型不同。能灵活保存不同⼤⼩的字符串，从⽽有效节省内存空间。⽐如，在保存⼩字符串时，结构头占⽤空间也⽐较少。
2）除了设计不同类型的结构体，Redis 在编程上还使⽤了专⻔的编译优化来节省内存空间，即在 struct 声明了 attribute ((packed)) ，告诉编译器取消结构体在编译过程中的优化对⻬，按照实际占⽤字节数进⾏对⻬。
⽐如，sdshdr16 类型的 SDS，默认情况下，编译器会按照 16 字节对⻬的⽅式给变量分配内存，这意味着，即使⼀个变量的⼤⼩不到 16 个字节，编译器也会给它分配 16 个字节。

链表

简介

Redis的List数据类型的底层实现之⼀就是链表。

C 语言本身并没有实现链表，Redis 实现了自己的链表数据结构。Redis 的 List 的实现为一个双向链表，即可以支持反向查找和遍历，更方便操作。

list、listNode数据结构

typedefstruct listNode {
     //前置节点
struct listNode *prev;
     //后置节点
struct listNode *next;
     //节点的值
void*value;
} listNode;

typedefstruct list {
     //链表头节点
     listNode *head;
     //链表尾节点
     listNode *tail;
     //节点值复制函数
void*(*dup)(void*ptr);
     //节点值释放函数
void (*free)(void*ptr);
     //节点值⽐较函数
int (*match)(void*ptr,void*key);
     //链表节点数量
unsignedlong len;
} list;

list 结构为链表提供了链表头指针 head、链表尾节点 tail、链表节点数量 len、以及可以的自定义实现的dup【节点值复制函数】、free【节点值释放函数】、match【节点值比较函数】函数。

Redis 的链表优点

1、listNode 链表节点的结构⾥带有 prev 和 next 指针，获取某个节点的前置节点或后置节点的时间复杂度只需O(1)。

2、list 结构因为提供了表头指针 head 和表尾节点 tail，所以获取链表头尾节点的时间复杂度只需O(1)；

3、list 结构因为提供了链表节点数量 len，所以获取链表中的节点数量的时间复杂度只需O(1)；

4、listNode 链表节使⽤ void* 指针保存节点值，并且可以通过 list 结构的 dup、free、match 函数指针为节点设置该节点类型特定的函数，因此链表节点可以保存各种不同类型的值；

Redis链表的缺陷

1、链表每个节点之间的内存都是不连续的，意味着⽆法很好利⽤缓存。能很好利⽤ CPU 缓存的数据结构就是数组，因为数组的内存是连续的，这样就可以充分利⽤ CPU 缓存来加速访问。

2、保存⼀个链表节点的值都需要⼀个链表节点结构的分配，内存开销较⼤。

因此，Redis 3.0 的 List 对象在数据量⽐较少的情况下，会采⽤「压缩列表」作为底层数据结构的实现，它的优势是节省内存空间，并且是内存紧凑型的数据结构。

不过，压缩列表存在性能问题，所以 Redis 在 3.2 版本设计了新的数据结构quicklist，并将 List 对象的底层数据结构改由 quicklist 实现。

然后在 Redis 5.0 设计了新的数据结构 listpack，沿⽤了压缩列表紧凑型的内存布局，最终在最新的 Redis版本，将 Hash 对象和 Zset 对象的底层数据结构实现之⼀的压缩列表，替换成由 listpack 实现。

Redis 的 Hash 对象的底层实现之⼀是压缩列表（最新 Redis 代码已将压缩列表替换成 listpack）。Hash 对象的另外⼀个底层实现就是哈希表。

压缩列表

介绍一下压缩列表

1）简介

压缩列表是Redis节约内存而开发的，它是由连续内存块组成的顺序型数据结构，有点类似于数组。

2）压缩列表的数据结构

压缩列表的表头有三个字段：

zlbytes，记录整个压缩列表占用的内存字节数；
zltail，记录压缩列表「尾部」节点距离起始地址由多少字节，也就是列表尾的偏移量；
zllen，记录压缩列表包含的节点数量；

表尾字段：zlend，标记压缩列表的结束点，固定值 0xFF（⼗进制255）。

3）查找元素的效率和缺陷1

在压缩列表中，如果我们要查找定位第⼀个元素和最后⼀个元素，可以通过表头三个字段的⻓度直接定位，复杂度是 O(1)。⽽查找其他元素时，就没有这么⾼效了，只能逐个查找，此时的复杂度就是 O(N)了，因此压缩列表不适合保存过多的元素。

4）entry的组成

压缩列表节点包含三部分内容：

prevlen，记录了「前⼀个节点」的⻓度；
encoding，记录了当前节点实际数据的类型以及⻓度；
data，记录了当前节点的实际数据；

5）压缩列表怎么节省内存的？

当我们往压缩列表中插⼊数据时，压缩列表会根据数据类型和数据⼤⼩，使⽤不同空间⼤⼩的 prevlen 和 encoding 。这种根据具体数据进⾏不同的空间⼤⼩分配的设计思想，正是 Redis 为了节省内存⽽采⽤的。

具体：prevlen 和 encoding 是如何根据数据的⼤⼩和类型来进⾏不同的空间⼤⼩分配。压缩列表⾥的每个节点中的 prevlen 属性都记录了「前⼀个节点的⻓度」，⽽且 prevlen 属性的空间⼤⼩跟前⼀个节点⻓度值有关，⽐如：

如果前⼀个节点的⻓度⼩于 254 字节，那么 prevlen 属性需要⽤ 1 字节的空间来保存这个⻓度值；
如果前⼀个节点的⻓度⼤于等于 254 字节，那么 prevlen 属性需要⽤ 5 字节的空间来保存这个⻓度值；

**为什么要记录前一个节点的长度呢？**因为ziplist的设计是尾部遍历，所以需要记录前一个节点的长度，这样用当前尾部节点的地址减去前一个节点的长度，就能够拿到前一个节点了。

encoding 属性的空间⼤⼩跟数据是字符串还是整数，以及字符串的⻓度有关：

如果当前节点的数据是整数，则 encoding 会使⽤ 1 字节的空间进⾏编码。
如果当前节点的数据是字符串，根据字符串的⻓度⼤⼩，encoding 会使⽤ 1 字节/2字节/5字节的空间进⾏编码。

6）压缩列表的缺陷2——连锁更新

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

7）总结——压缩列表的缺陷

连锁更新⼀旦发⽣，就会导致压缩列表占⽤的内存空间要多次重新分配，这就会直接影响到压缩列表的访问性能。所以，虽然压缩列表紧凑型的内存布局能节省内存开销，但是如果增加元素或是修改元素，会导致内存重新分配，开销较大。而且压缩列表查找中间元素的时间复杂度是O(n)。

因此，压缩列表只会⽤于保存的节点数量不多的场景，节点数量⼩，即使发⽣连锁更新，也是能接受的。

Redis 针对压缩列表在设计上的不⾜，在后来的版本中，新增设计了两种数据结构：quicklist（Redis 3.2 引⼊）和 listpack（Redis 5.0 引⼊）。这两种数据结构的设计⽬标，就是尽可能地保持压缩列表节省内存的优势，同时解决压缩列表的「连锁更新」的问题。

因此，Redis 对象（List 对象、Hash 对象、Zset 对象）包含的元素数量较少，或者元素值不⼤的情况才会使用压缩列表作为底层数据结构。

哈希表

介绍

哈希表优点在于，它能以 O(1) 的复杂度快速查询数据。将 key 通过 Hash 函数的计算，就能定位数据在表中的位置，因为哈希表实际上是数组，所以可以通过索引值快速查询到数据。

但是可能存在哈希冲突，Redis 采⽤了「链式哈希」来解决哈希冲突。

哈希表的数据结构

typedefstruct dictht {
 //哈希表数组
 dictEntry **table;
 //哈希表⼤⼩
unsignedlong size;
 //哈希表⼤⼩掩码，⽤于计算索引值
unsignedlong sizemask;
 //该哈希表已有的节点数量
unsignedlong used;
} dictht;

哈希表是⼀个数组（dictEntry **table），数组的每个元素是⼀个指向「哈希表节点（dictEntry）」的指针。

哈希表节点(dictEntry)的数据结构

typedefstruct dictEntry {
 //键值对中的键
void*key;

 //键值对中的值
union {
void*val;
uint64_t u64;
int64_t s64;
double d;
 } v;
 //指向下⼀个哈希表节点，形成链表
struct dictEntry *next;
} dictEntry;

dictEntry 结构⾥不仅包含指向键和值的指针，还包含了指向下⼀个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对链接起来，以此来解决哈希冲突的问题，这就是链式哈希。 dictEntry 结构⾥键值对中的值是⼀个「联合体 v」定义的，因此，键值对中的值可以是⼀个指向实际值的指针，或者是⼀个⽆符号的 64 位整数或有符号的 64 位整数或double 类的值。这么做的好处是可以节省内存空间，因为当「值」是整数或浮点数时，就可以将值的数据内嵌在 dictEntry结构⾥，⽆需再⽤⼀个指针指向实际的值，从⽽节省了内存空间。

哈希冲突

哈希表实际上是⼀个数组，数组⾥每⼀个元素就是⼀个哈希桶。当⼀个键值对的键经过 Hash 函数计算后得到哈希值，再将(哈希值 % 哈希表⼤⼩)取模计算，得到的结果值就是该 key-value 对应的数组元素位置，也就是第⼏个哈希桶。

链式哈希是怎么实现的?

实现的⽅式就是每个哈希表节点都有⼀个 next 指针，⽤于指向下⼀个哈希表节点，因此多个哈希表节点可以⽤ next 指针构成⼀个单项链表，被分配到同⼀个哈希桶上的多个节点可以⽤这个单项链表连接起来，这样就解决了哈希冲突。

不过，链式哈希局限性也很明显，随着链表⻓度的增加，在查询这⼀位置上的数据的耗时就会增加，毕竟链表的查询的时间复杂度是 O(n)。要想解决这⼀问题，就需要进⾏ rehash，也就是对哈希表的⼤⼩进⾏扩展。

Redis实现rehash【对哈希表的大小进行拓展】

Redis 使⽤ dictht 结构体表示哈希表。不过，在实际使⽤哈希表时，Redis 定义⼀个 dict 结构体，这个结构体⾥定义了两个哈希表。 rehash 的时候就需要⽤上 2 个哈希表了。

在正常服务请求阶段，插⼊的数据，都会写⼊到「哈希表 1」，此时的「哈希表 2 」并没有被分配空间。

随着数据逐步增多，触发了 rehash 操作，这个过程分为三步：

1）给「哈希表 2」分配空间，⼀般会⽐「哈希表 1」⼤ 2 倍；

2）将「哈希表 1 」的数据迁移到「哈希表 2」中；

3）迁移完成后，「哈希表 1 」的空间会被释放，并把「哈希表 2」设置为「哈希表 1」，然后在「哈希表 2」新创建⼀个空⽩的哈希表，为下次 rehash 做准备。

这个过程看起来简单，但是其实第⼆步很有问题，如果「哈希表1」的数据量⾮常⼤，那么在迁移⾄「哈希表2」的时候，因为会涉及⼤量的数据拷⻉，此时可能会对Redis造成阻塞，⽆法服务其他请求。

渐进式rehash

为了避免 rehash 在数据迁移过程中，影响 Redis 性能的情况，所以 Redis 采⽤了渐进式rehash，也就是将数据的迁移的⼯作不再是⼀次性迁移完成，⽽是分多次迁移。

渐进式 rehash 步骤如下：

给「哈希表 2」分配空间；
在 rehash 进⾏期间，每次哈希表元素进⾏查找或者更新操作时，Redis除了会执⾏对应的操作之外，还会顺序将「哈希表1」中索引位置上的所有key-value迁移到「哈希表2」上；新增⼀个 key-value 时，会被保存到「哈希表 2 」⾥⾯，⽽「哈希表1」则不再进⾏任何添加操作。查找⼀个 key 的值的话，先会在「哈希表 1」⾥⾯进⾏查找，如果没找到，就会继续到哈希表 2 ⾥⾯进⾏查找。保证了「哈希表 1 」的 key-value 数量只会减少，最终「哈希表 1 」就会变成空表。
随着处理客户端发起的哈希表操作请求数量越多，最终在某个时间点呢，会把「哈希表 1 」的所有key-value 迁移到「哈希表 2」，从⽽完成 rehash 操作。

这样就巧妙地把⼀次性⼤量数据迁移⼯作的开销，分摊到了多次处理请求的过程中，避免了⼀次性 rehash的耗时操作。

rehash触发条件

rehash 的触发条件跟负载因⼦（load factor）有关系。负载因⼦可以通过下⾯这个公式计算：

触发 rehash 操作的条件，主要有两个：

1）当负载因⼦⼤于等于 1 ，并且 Redis 没有在执⾏ bgsave 命令或者 bgrewiteaof 命令，也就是没有执⾏ RDB快照或没有进⾏AOF重写的时候，就会进⾏ rehash 操作。

2）当负载因⼦⼤于等于5时，此时说明哈希冲突⾮常严重了，不管有没有有在执⾏RDB快照或AOF重写，都会强制进⾏rehash操作。

整数集合

整数集合是set数据类型的底层实现之一。当⼀个 Set只包含整数值元素，并且元素数量不多时，就会使⽤整数集这个数据结构作为底层实现。

整数集合数据结构

整数集合本质上是⼀块连续内存空间

typedefstruct intset {
 //编码⽅式
uint32_t encoding;
 //集合包含的元素数量
uint32_t length;
 //保存元素的数组
int8_t contents[];
} intset;

保存元素的容器是⼀个 contents 数组，contents 数组的真正类型取决于 intset 结构体⾥的encoding 属性的值。⽐如：

如果 encoding 属性值为 INTSET_ENC_INT16，那么 contents 就是⼀个 int16_t 类型的数组，数组中每⼀个元素的类型都是 int16_t；
如果 encoding 属性值为 INTSET_ENC_INT32，那么 contents 就是⼀个 int32_t 类型的数组，数组中每⼀个元素的类型都是 int32_t；
如果 encoding 属性值为 INTSET_ENC_INT64，那么 contents 就是⼀个 int64_t 类型的数组，数组中每⼀个元素的类型都是 int64_t；

不同类型的 contents 数组，意味着数组的⼤⼩也会不同。

整数集合的升级操作

1）规则和具体操作

整数集合会有⼀个升级规则，就是当我们将⼀个新元素加⼊到整数集合⾥⾯，如果新元素的类型（int32_t）⽐整数集合现有所有元素的类型（int16_t）都要⻓时，整数集合需要先进⾏升级，也就是按新元素的类型（int32_t）扩展 contents 数组的空间⼤⼩，然后才能将新元素加⼊到整数集合⾥，当然升级的过程中，也要维持整数集合的有序性。

整数集合升级的过程不会重新分配⼀个新类型的数组，⽽是在原本的数组上扩展空间，然后在将每个元素按间隔类型⼤⼩分割，如果 encoding 属性值为 INTSET_ENC_INT16，则每个元素的间隔就是 16 位。

举个例⼦，假设有⼀个整数集合⾥有 3 个类型为 int16_t 的元素。

现在，往这个整数集合中加⼊⼀个新元素 65535，这个新元素需要⽤ int32_t 类型来保存，所以整数集合要进⾏升级操作，⾸先需要为 contents 数组扩容，在原本空间的⼤⼩之上再扩容多 80位（4x32-3x16=80），这样就能保存下4个类型为int32_t的元素。

扩容完 contents 数组空间⼤⼩后，需要将之前的三个元素转换为 int32_t 类型，并将逐步将转换后的元素放置到正确的位上⾯，整个转换过程如下：

2）好处

节省内存资源

如果要让⼀个数组同时保存 int16_t、int32_t、int64_t 类型的元素，最简单做法就是直接使⽤ int64_t 类型的数组。不过这样的话，当如果元素都是 int16_t 类型的，就会造成内存浪费的情况。

整数集合升级就能避免这种情况，如果⼀直向整数集合添加 int16_t 类型的元素，那么整数集合的底层实现就⼀直是⽤ int16_t 类型的数组，只有在我们要将 int32_t 类型或 int64_t 类型的元素添加到集合时，才会对数组进⾏升级操作。

3）整数集合不支持降级操作

⼀旦对数组进⾏了升级，就会⼀直保持升级后的状态。⽐如前⾯的升级操作的例⼦，如果即时删除了大类型的数据，整数集合的数组还是大类型的，并不会因此降级。

跳表

Redis 在有序集合Zset数据类型的底层实现⽤到了跳表，跳表的优势是能⽀持平均 O(logN) 复杂度的节点查找。

Zset 对象在使⽤跳表作为底层实现的时候，并不是指向跳表数据结构，⽽是指向了zset结构，它包含两个数据结构。⼀个是跳表，⼀个是哈希表。这样的好处是既能进⾏⾼效的范围查询，也能进⾏⾼效的单点权重查询。

Zset 对象能⽀持范围查询（如 ZRANGEBYSCORE 操作），这是因为它的数据结构设计采⽤了跳表；⽽⼜能以常数复杂度获取元素权重（如 ZSCORE 操作），这是因为它同时采⽤了哈希表进⾏索引。

跳表数据结构

链表在查找元素的时候，因为需要逐⼀查找，所以查询效率⾮常低，时间复杂度是O(N)，于是就出现了跳表。跳表实现了⼀种「多层」的有序链表，这样的好处是能快读定位数据。

那跳表⻓什么样呢？我这⾥举个例⼦，下图展示了⼀个层级为 3 的跳表。

图中头节点有 L0~L2 三个头指针，分别指向了不同层级的节点，然后每个层级的节点都通过指针连接起来：

1）L0 层级共有 5 个节点，分别是节点1、2、3、4、5；

2）L1 层级共有 3 个节点，分别是节点 2、3、5；

3）L2 层级只有 1 个节点，也就是节点 3 。

如果我们要在链表中查找节点 4 这个元素，只能从头开始遍历链表，需要查找 4 次，⽽使⽤了跳表后，只需要查找 2 次就能定位到节点 4，因为可以在头节点直接从 L2 层级跳到节点 3，然后再往前遍历找到节点4。

可以看到，这个查找过程就是在多个层级上跳来跳去，最后定位到元素。当数据量很⼤时，跳表的查找复杂度就是 O(logN)。

跳表节点的数据结构

那跳表节点是怎么实现多层级的呢？这就需要看「跳表节点」的数据结构了，如下：

typedefstruct zskiplistNode {
     //Zset 对象的元素值
     sds ele;
     //元素权重值
double score;
     //后向指针 指向前⼀个节点，⽬的是为了⽅便从跳表的尾节点开始访问节点，这样倒序查找时很⽅便
struct zskiplistNode *backward;

     //节点的level数组，保存每层上的前向指针和跨度
struct zskiplistLevel {
struct zskiplistNode *forward;
unsignedlong span;
  } level[];
 } zskiplistNode;

实现跳表的关键在于跳表节点数据结构中的level数组，保存了每一层的前向指针以及该层的跨度

跳表数据结构

typedefstruct zskiplist {
struct zskiplistNode *header, *tail;
unsignedlong length;
int level;
} zskiplist;

跳表结构⾥包含了：

1)跳表的头尾节点，便于在O(1)时间复杂度内访问跳表的头节点和尾节点；

2)跳表的⻓度，便于在O(1)时间复杂度获取跳表节点的数量；

3)跳表的最⼤层数，便于在O(1)时间复杂度获取跳表中层⾼最⼤的那个节点的层数量；

跳表查询过程

跳表会从头节点的最⾼层开始，逐⼀遍历每⼀层。在遍历某⼀层的跳表节点时，会⽤跳表节点中的 SDS 类型的元素和元素的权重来进⾏判断，共有两个判断条件：

1)如果当前节点的权重「⼩于」要查找的权重时，跳表就会访问该层上的下⼀个节点。

2)如果当前节点的权重「等于」要查找的权重时，并且当前节点的 SDS 类型数据「⼩于」要查找的数据时，跳表就会访问该层上的下⼀个节点。

如果上⾯两个条件都不满⾜，或者下⼀个节点为空时，跳表就会使⽤⽬前遍历到的节点的 level 数组⾥的下⼀层指针，然后沿着下⼀层指针继续查找，这就相当于跳到了下⼀层接着查找

查找时间复杂度分析

查找元素的过程是从最高级索引开始，一层一层遍历最后下沉到原始链表。所以，时间复杂度 = 索引的高度 * 每层索引遍历元素的个数。

索引高度：上一层的元素大致为下面一层的1/2，最高层索引一般有两个元素，所以式子为2=n/2^h，得出高度h=logn-1。理想状况每两个元素抽一个作为上层索引的节点，每层最多遍历三个元素，因此查找时间复杂度为3logn，省略常数为O(nlogn)

空间复杂度分析

假如原始链表包含 n 个元素，则一级索引元素个数为 n/2、二级索引元素个数为 n/4、三级索引元素个数为 n/8 以此类推。所以，索引节点的总和是：n/2 + n/4 + n/8 + … + 8 + 4 + 2 = n-2，空间复杂度是 O(n)。

插入元素时间复杂度分析

插入元素类似于查找元素，时间复杂度为O(logn)。但是假如一直往原始列表中添加数据，不更新索引，就可能出现两个索引节点之间数据非常多的情况，极端情况，跳表退化为单链表，从而使得查找效率从 O(logn) 退化为 O(n)。

所以需要节点的维护，跳表是通过概率模型来做的。1/2的概率不需要建索引，只需要插到原始链表；1/4的概率把当前插入的元素加入一级索引；1/8的概率把当前插入的元素加入二级索引，依次类推。

所以插入数据维护索引的时间复杂度，最好情况就是只插入原始单链表，时间复杂O(1)，最坏情况就是要插入每层索引，时间复杂度为O(logn)，所以整个插入的时间复杂度为O(logn)

删除元素时间复杂度分析

删除元素的过程跟查找元素的过程类似，只不过在查找的路径上如果发现了要删除的元素 x，则执行删除操作。跳表中，单链表删除元素的时间复杂度为 O(1)，索引层数为 logn 表示最多需要删除 logn 个元素，所以删除元素的总时间包含 查找元素的时间 加 删除 logn个元素的时间 为 O(logn) + O(logn) = 2 O(logn)，忽略常数部分，删除元素的时间复杂度为 O(logn)。

为什么用跳表？

不用平衡二叉树的原因：因为维持平衡需要比较大的开销
不用红黑树的原因：相比红黑树，跳表的实现更加简单；对于范围查询，红黑树的效率没有跳表高
不用B+树的原因：
1. B+树由于存储效率高，非叶子节点可以存储更多的key的特性，更适合作为数据库和文件系统中常用的索引结构之一，核心思想是通过可能少的 IO 定位到尽可能多的索引来获得查询数据。而Redis 是内存数据库，不可能存储大量的数据，所以对于索引不需要通过 B+树这种方式进行维护，节约内存。
2. 而且使用跳表实现相较B+树来说更简单一些，在进行插入时只需通过索引将数据插入到链表中合适的位置再随机维护一定高度的索引即可，也不需要像 B+树那样插入时发现失衡时还需要对节点分裂与合并，维护涉及的节点树比B+树小，成本更低。

quicklist

quicklist简介

在 Redis 3.0 之前，List 对象的底层数据结构是双向链表或者压缩列表。然后在 Redis 3.2 的时候，List 对象的底层改由 quicklist 数据结构实现。

其实 quicklist 就是「双向链表 + 压缩列表」组合，因为 quicklist 本身是一个链表，⽽链表节点会指向是⼀个压缩列表。

在向 quicklist 添加⼀个元素的时候，不会像普通的链表那样，直接新建⼀个链表节点。⽽是会检查插⼊位置的压缩列表是否能容纳该元素，如果能容纳就直接保存到 quicklistNode 结构⾥的压缩列表，如果不能容纳，才会新建⼀个新的 quicklistNode 结构。通过控制每个链表节点中的压缩列表的⼤⼩或者元素个数，来规避连锁更新的问题。因为压缩列表元素越少或越⼩，连锁更新带来的影响就越⼩，从⽽提供了更好的访问性能。

quicklistNode结构设计

quicklist 的结构体跟链表的结构体类似，都包含了表头和表尾，区别在于 quicklist 的节点是quicklistNode。

quicklistNode的结构：

typedefstruct quicklistNode {
     //前⼀个quicklistNode
struct quicklistNode *prev; //前⼀个quicklistNode
     //下⼀个quicklistNode
struct quicklistNode *next; //后⼀个quicklistNode
     //quicklistNode指向的压缩列表
unsignedchar*zl;
     //压缩列表的的字节⼤⼩
unsignedint sz;
     //压缩列表的元素个数
unsignedint count : 16; //ziplist中的元素个数
 ....
} quicklistNode;

quicklistNode 结构体⾥包含了前⼀个节点和下⼀个节点指针，这样每个 quicklistNode 形成了⼀个双向链表。但是链表节点的元素不再是单纯保存元素值，⽽是保存了⼀个压缩列表，所以quicklistNode 结构体⾥有个指向压缩列表的指针 *zl。

quicklist 数据结构

在向 quicklist 添加⼀个元素的时候，会检查插⼊位置的压缩列表是否能容纳该元素，如果能容纳就直接保存到压缩列表，如果不能容纳，才会新建⼀个新的 quicklistNode 结构。

quicklist 会控制 quicklistNode 结构⾥的压缩列表的元素个数，来减少连锁更新的代价，但是这并没有完全解决连锁更新的问题。

listpack数据结构

简介

Redis 在 5.0 新设计⼀个数据结构叫 listpack，⽬的是替代压缩列表，它最⼤特点是 listpack 中每个节点不再包含前⼀个节点的⻓度了，压缩列表每个节点正因为需要保存前⼀个节点的⻓度字段，就会有连锁更新的隐患。

我看了 Redis 的 Github，在最新 6.2 发⾏版本中，Redis Hash 对象、Set 对象的底层数据结构的压缩列表还未被替换成 listpack，⽽ Redis 的最新代码（还未发布版本）已经将所有⽤到压缩列表底层数据结构的 Redis 对象替换成listpack 数据结构来实现，估计不久将来，Redis 就会发布⼀个将压缩列表为listpack 的发⾏版本。

listpack 结构设计

listpack 采⽤了压缩列表的很多优秀的设计，⽐如还是⽤⼀块连续的内存空间来紧凑地保存数据，并且为了节省内存的开销，listpack 节点会采⽤不同的编码⽅式保存不同⼤⼩的数据。

listpack 结构：

listpack 头包含两个属性，分别记录了 listpack 总字节数和元素数量，然后 listpack 末尾也有个结尾标识。

listpack节点结构

图中的 listpack entry 就是 listpack 的节点了。

每个 listpack 节点结构如下：

主要包含三个⽅⾯内容：

1）encoding，定义该元素的编码类型，会对不同⻓度的整数和字符串进⾏编码；

2）data，实际存放的数据；

3）len，encoding+data的总⻓度；

可以看到，listpack 没有压缩列表中记录前⼀个节点⻓度的字段了，listpack只记录当前节点的⻓度，当我们向listpack加⼊⼀个新元素的时候，不会影响其他节点的⻓度字段的变化，从⽽避免了压缩列表的连锁更新问题。