Redis五大数据类型——List列表

Redis五大数据类型：String（字符串），Hash（哈希），List（列表），Set（集合）及Zset(sorted set：有序集合)。一、介绍列表(list)用于存储多个有序的字符串。可以充当栈和队列的角色一般有序会采用数组或者是双向链表，其中双向链表由于有前后指针实际上会很浪费内存。二、操作命令操作类型命令添加rpush、lpush、linsert修改lset删除lpop、rp...

·梅花十三

11784人浏览 · 2021-12-17 09:50:02

·梅花十三 · 2021-12-17 09:50:02 发布

Redis五大数据类型：String（字符串），Hash（哈希），List（列表），Set（集合）及Zset(sorted set：有序集合)。

一、介绍

列表(list)用于存储多个有序的字符串。可以充当栈和队列的角色

一般有序会采用数组或者是双向链表，其中双向链表由于有前后指针实际上会很浪费内存。

二、数据结构

▶ 3.2版本前，Redis 列表list使用两种数据结构作为底层实现

压缩列表ziplist （插入元素过多或字符串太大，就需要调用 realloc 扩展内存）
双向链表linkedlist （需附加指针prev 和 next，较浪费空间，加重内存的碎片化）

双向链表占用的内存比压缩列表要多，所以当创建新列表时，会优先考虑使用压缩列表，并且在有需要的时候，才从压缩列表实现转换到双向链表实现。

压缩列表转化成双向链表条件

列表中某个字符串值超过 list_max_ziplist_value（默认64字节）
列表的元素个数超过 list_max_ziplist_entries（默认 512个）

注意：这两个条件是可以修改的，在 redis.conf 中：

list-max-ziplist-value 64
list-max-ziplist-entries 512

1、当元素个数 > 512个，转变为 linkedlist

[127.0.0.1:6379> rpush mylist a1 a2 ... a512 a513
(integer) 513
[127.0.0.1:6379> object encoding mylist
"linkedlist"

2、当某个元素值 < 64字节，转变为 linkedlist

[127.0.0.1:6379> rpush listkey "one string is bigger than 64 byte..."
(integer) 4
[127.0.0.1:6379> object encoding listkey
"linkedlist"

▶ 3.2版本后，Redis 列表使用quciklist (快速链表) 数据结构作为底层实现

quicklist (快速链表)

[127.0.0.1:6379> rpush mylist a b c
(integer) 3
[127.0.0.1:6379> object encoding mylist
"quicklist"

一、双向链表linkedlist

linkedlist是标准的双向链表，Node节点包含prev和next指针，可以进行双向遍历；添加删除元素快O(1)，查找元素慢 O(n)，是高效实现 LPUSH 、RPOP、RPOPLPUSH 等命令的关键

LinkedList中，每个数据节点Node结构如下图所示：

在这里插入图片描述

1）当前节点的数据 item
2）前置节点的引用 prev，存放前置节点的地址
3）后置节点的引用 next，存放后置节点的地址

a. 第一次往链表中添加节点时：会新建一个节点，头指针first和尾指针last都指向该节点

在这里插入图片描述

b. 第二次添加：将last指针指向新加的节点，头节点的next指向新节点，新节点的prev指向头节点

在这里插入图片描述

c. 依次类推，每次添加节点，都会将尾节点指针后移，同时设置新节点的prev指向原来的尾节点，原来尾节点的next指向新节点

缺点：添加、删除元素快，但内存开销比较大！

每个节点上除了保存数据，还额外保存两个指针prev、next（16字节）
双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片

二、压缩列表 ziplist

压缩列表是一块连续的内存空间 (像内存连续的数组，但每个元素长度不同)，一个 ziplist 可以包含多个节点（entry）。元素之间紧挨着存储，没有任何冗余空隙。

ziplist 将表中每一项存放在前后连续的地址空间内，每一项因占用的空间不同，而采用变长编码。由于内存是连续分配的，所以遍历速度很快。

1、整个ziplist数据结构图如下：

压缩列表为了支持双向遍历， ztail_offset字段，用来快速定位到最后一个元素，然后倒着遍历。

2、增加元素

ziplist 都是紧凑存储，没有冗余空间。意味着插入一个新的元素就需要调用 realloc 扩展内存。

取决于内存分配器算法和当前的 ziplist 内存大小，realloc 可能会重新分配新的内存空间，并将之前的内容一次性拷贝到新的地址，也可能在原有的地址上进行扩展，这时就不需要进行旧内容的内存拷贝。

如果ziplist 占据内存太大，重新分配内存和拷贝内存就会有很大的消耗。故ziplist不适合存储大型字符串，存储的元素也不宜过多。

缺点：存储在一段连续的内存上，查询快，存储效率高。不利于修改，插入和删除操作需要频繁的申请和释放内存。特别是当ziplist长度很长的时候，一次realloc可能会导致大批量的数据拷贝。

3、ziplist节点entry结构

每一个存储节点（entry）都是一个zlentry (zip list entry)。

// 压缩列表节点
typedef struct zlentry {    
// prevrawlen是前一个节点的长度，prevrawlensize是指prevrawlen的大小，有1字节和5字节两种
    unsigned int prevrawlensize, prevrawlen;    
    unsigned int lensize, len;  // len为当前节点长度 lensize为编码len所需的字节大小
    unsigned int headersize;    // 当前节点的header大小
    unsigned char encoding; // 节点的编码方式
    unsigned char *p;   // 指向节点的指针
} zlentry;

可见，每一个存储节点 zlentry，都包含

prevrawlen 前一个 entry的长度
lensize 当前entry的长度

▶ 如何通过一个节点向前跳转到另一个节点？
指向当前节点的指针e - 前一个entry的长度 = 指向前一个节点的地址 p

▶ 完整的zlentry由以下3各部分组成：

prevrawlen：记录前一个 entry的长度，通过该值可计算出前一个节点的地址
len/encoding：记录当前节点content占有的内存字节数及其存储类型，用来解析content用
content：保存了当前节点的值。

▶ prevrawlen是变长编码，有两种表示方法：

前一节点的长度 < 254字节，则使用1字节来存储 prevrawlen；
前一节点的长度 >= 254字节，第 1 个字节的值设为 254 ，剩下4字节保存实际长度（5字节）

4、ziplist连锁更新问题

每个entry都存储着前一个节点所占的字节数，这个数值又是变长编码的，由此可知：

假设：一个压缩列表e1、e2、e3、e4…..，其中e1节点= 253字节，则e2.prevrawlen = 1字节 如果：此时在e2与e1之间插入一个新节点a，a长度= 254字节，则e2.prevrawlen需扩充到5字节；

以此类推，如果e2的长度变化又引起了e3.prevrawlen的长度变化，则e3也需扩充，直到表尾节点或某一节点的prevrawlen本身长度可容纳前一个节点的变化。每次扩充都需进行空间再分配操作。删除节点也是，一旦引起了节点的prevrawlen的变化，都可能产生连锁更新反应！

三、快速列表 quicklist

quicklist 是 ziplist 和 linkedlist 的混合体，将 linkedlist 按段切分，每一段使用 ziplist 来紧凑存储，多个 ziplist 之间使用双向指针串接起来。本质上来说，quicklist里面保存着一个一个小的ziplist

quickList就是一个标准的双向链表的配置，有head 有tail;
每一个节点是一个quicklistNode，包含prev和next指针。
每一个quicklistNode 包含一个ziplist，*zp 压缩链表里存储键值。
所以quicklist是对ziplist进行一次封装，使用小块的ziplist来既保证了少使用内存，也保证了性能。

ziplist 存多少元素?

quicklist 内部默认单个 ziplist 长度为 8k 字节，超出了这个字节数，就会新起一个ziplist。

list-compress-depth：压缩的实际深度（quicklist 默认压缩深度是 0，即不压缩）
list-max-ziplist-size：ziplist的长度

为了支持快速的 push和pop 操作，quicklist 的首尾两个 ziplist 都不压缩，此时深度就是 1 如果深度为 2，就表示 quicklist 的首尾第一个 ziplist 以及首尾第二个 ziplist 都不压缩。

三、操作命令

操作类型	命令
添加	rpush、lpush、linsert
修改	lset
删除	lpop、rpop、lrem、ltrim
查询	lrange、lindex、llen
阻塞操作	blpop、brpop
弹出/	rpoplpush

▶ 添加

1、Rpush 从列表右边插入元素

语法：Rpush key 元素1 [元素2 ...]

[127.0.0.1:6379> rpush mylist lisa jack rose  # 从List列表右侧依次插入元素
(integer) 3

# [lrange key start stop] 根据下标查询元素
[127.0.0.1:6379> lrange mylist 0 -1   #下标从0开始，-1表示最后的下标位置 
1) "lisa"
2) "jack"
3) "rose"

2、Lpush 从列表左边插入元素

语法：Lpush key 元素1 [元素2 ...]

[127.0.0.1:6379> lpush mylist a b c   # 从List列表左侧依次插入元素
(integer) 3

# [lrange key start stop] 根据下标查询元素
[127.0.0.1:6379> lrange mylist 0 -1 #下标从0开始，-1表示最后的下标位置 
1) "c"
2) "b"
3) "a"

3、Linsert 在目标元素前或后插入元素

语法：Linsert key before|after 目标元素 value

# 原mylist所有元素
[127.0.0.1:6379> lrange mylist 0 -1
1) "c"
2) "b"
3) "a"

# ————前：在列表mylist中，在元素“a“ 前面插入 新元素 “123”
[127.0.0.1:6379> linsert mylist before a 123
(integer) 4
# 插入后的mylist所有元素
[127.0.0.1:6379> lrange mylist 0 -1
1) "c"
2) "b"
3) "123"
4) "a"

# ————后：：在列表mylist中，在元素“c“ 后面插入 新元素 “456”
[127.0.0.1:6379> linsert mylist after c 456
(integer) 5
# 插入后的mylist所有元素
[127.0.0.1:6379> lrange mylist 0 -1
1) "c"
2) "456"
3) "b"
4) "123"
5) "a"

▶ 修改

1、Lset 更新指定下标的值

语法：Lset key index value

# 原mylist所有元素
[127.0.0.1:6379> lrange mylist 0 -1
1) "c"
2) "456"
3) "b"
4) "123"
5) "a"

# 在mylist列表中，更新下标1的值
[127.0.0.1:6379> lset mylist 1 jack
OK
[127.0.0.1:6379> lrange mylist 0 -1
1) "c"
2) "jack"  # ——原本“456” 替换为“jack”
3) "b"
4) "123"
5) "a"

[127.0.0.1:6379> lset mylist 7 rose    # 注1：更新不存在元素的下标报错
(error) ERR index out of range
[127.0.0.1:6379> lset mylist2 0 hello  # 注2：更新不存在的列表报错
(error) ERR no such key

▶ 删除

1、Lpop 从列表左端弹出元素

语法：Lpop key [弹出元素数量count可选]

# 原列表所有元素
[127.0.0.1:6379> lrange mylist 0 -1
1) "d"
2) "c"
3) "b"
4) "a"

# ——1.针对不存在的列表，执行弹出元素操作，返回nil
[127.0.0.1:6379> lpop otherlist
(nil)

# ——2.从mylist列表的左端弹出一个元素
[127.0.0.1:6379> lpop mylist
"d"  # 返回被弹出的元素

# 查看列表内所有元素（“d”元素已被弹出）
[127.0.0.1:6379> lrange mylist 0 -1
1) "c"
2) "b"
3) "a"

# ——3.从mylist列表的左端弹出2个元素
[127.0.0.1:6379> lpop mylist 2
1) "c" # 返回被弹出的元素
2) "b"

# 查看列表内所有元素（“c”、“b”元素已被弹出）
[127.0.0.1:6379> lrange mylist 0 -1
1) "a"

2、Rpop 从列表右端弹出元素

语法：Rpop key [弹出元素数量count可选]

# 原列表所有元素
[127.0.0.1:6379> lrange mylist 0 -1
1) "d"
2) "c"
3) "b"
4) "a"

# ——1.从mylist列表的右端弹出2个元素
[127.0.0.1:6379> rpop mylist 2
1) "a"
2) "b"

# 查看列表内所有元素（“a”、“b”元素已被弹出）
[127.0.0.1:6379> lrange mylist 0 -1
1) "d"
2) "c"

3、Lrem 删除n个指定的元素

语法：Lrem key count [指定要删除的元素值]

# 原列表所有元素
[127.0.0.1:6379> lrange mylist 0 -1
1) "d"
2) "c"
3) "c"
4) "b"
5) "a"

# ——1.在mylist列表中移除 1个 “a" 元素
[127.0.0.1:6379> lrem mylist 1 a
(integer) 1

# 移除后的所有元素（“a"元素已被移除）
127.0.0.1:6379> lrange mylist 0 -1
1) "d"
2) "c"
3) "c"
4) "b"

# ——2.在mylist列表中移除 2个 “c" 元素
[127.0.0.1:6379> lrem mylist 2 c
(integer) 2

# 移除后的所有元素（2个“c"元素已被移除）
[127.0.0.1:6379> lrange mylist 0 -1
1) "d"
2) "b"

4、Ltrim 剪裁list列表

语法：Ltrim key [开始下标] [结束下标]

——下标从0开始，支持负下标，-1表示最右端的元素

例：列表 list [01234]，执行：Ltrim list 1 -2 结果： [123]

注意：超出范围的索引不会产生错误

开始下标 > 列表的末尾 / 开始下标 > 结束下标：结果为空列表（会导致key被删除）
结束下标>列表的末尾：则Redis会将其视为列表的最后一个元素。

# 原列表所有元素
[127.0.0.1:6379> lrange mylist 0 -1
1) "a"
2) "b"
3) "c"
4) "d"
5) "e"

# 截取mylist列表，下标从1-2位置的元素
[127.0.0.1:6379> ltrim mylist 1 2
OK

# 截取后的列表如下：
[127.0.0.1:6379> lrange mylist 0 -1
1) "b"
2) "c"

▶ 查询

1、Lrange 获取指定范围的元素

语法：Lrange key [开始下标] [结束下标]

——范围获取元素，下标从0开始，支持负下标，-1表示最右端的元素

注：超出范围的索引不会产生错误

开始下标 > 列表的末尾：则返回一个空列表。
结束下标 > 列表的实际末尾：则Redis会将其视为列表的最后一个元素。

# 查询mylist列表，从下标0到 倒数第一个（即最后一个）
[127.0.0.1:6379> lrange mylist 0 -1  #下标从0开始，-1表示最后的下标位置 
1) "a"
2) "b"
3) "c"
4) "d"

# 查询mylist列表，从下标0到 倒数第二个位置
[127.0.0.1:6379> lrange mylist 0 -2
1) "a"
2) "b"
3) "c"

2、Lindex 删除n个指定的元素

语法：Lindex key count [指定要删除的元素value]

——索引从0开始，支持负索引，-1末尾最后一个元素；索引越界，返回null

# 查询mylist列表，从下标0到 倒数第一个（即最后一个）
[127.0.0.1:6379> lrange mylist 0 -1  #下标从0开始，-1表示最后的下标位置 
1) "a"
2) "b"
3) "c"
4) "d"

# 查询下标3的元素
[127.0.0.1:6379> lindex mylist 3
"d"

# 索引越界，返回nil
[127.0.0.1:6379> lindex mylist 5
(nil)

3、Llen 获取list长度

语法：Llen key

# 查询mylist列表所有元素
[127.0.0.1:6379> lrange mylist 0 -1  #下标从0开始，-1表示最后的下标位置 
1) "a"
2) "b"
3) "c"
4) "d"

# 获取列表长度
[127.0.0.1:6379> llen mylist
(integer) 4

▶ 特殊操作

1、RpopLpush 右边弹出，左边推入

语法：RpopLpush [源列表] [目标列表]

(可理解为 right pop，left push），从源list 的最右端弹出一个元素，推入到目标list的最左端（移除原列表队列尾部的元素到新列表的队列头部），原子操作。
——如源列表不存在，返回 nil ，且不会执行任何操作！

# 查询源mylist列表
[127.0.0.1:6379> lrange mylist 0 -1  #下标从0开始，-1表示最后的下标位置 
1) "d"
2) "c"
3) "b"
4) "a"

# 从mylist列表中右边推出一个元素，推入到新列表中（newlist不存在库中，等同新建）
[127.0.0.1:6379> rpoplpush mylist newlist
"a" # 右边被推出的元素

# 查询源mylist列表（元素“a"被推出去了）
[127.0.0.1:6379> lrange mylist 0 -1
1) "d"
2) "c"
3) "b"

# 查询新列表newlist（元素“a"被推入进来）
[127.0.0.1:6379> lrange newlist 0 -1
1) "a"

▶ 阻塞操作

1、BRpopLpush 右边弹出，左边推入（阻塞版）

语法：BRpopLpush [源列表] [目标列表] timeout

原列表存在元素：此命令的行为与RpopLpush完全相同。
原列表为空：Redis 将阻止连接，直到另一个客户端将元素推入源list或超时到达为止。

# 从mylist列表的右边弹出一个元素，从左边推入到newlist列表，超时5秒自动断连
[127.0.0.1:6379> brpoplpush mylist newlist 5
(nil)
(5.01s)  # 未到5秒前，一直保持连接，直到mylist存在元素，或者超过5秒自动断连

2、BLpop 从列表左端弹出元素（阻塞）

语法：BLpop key1 key2... timeout

BLpop 是 Lpop 的阻塞版本，不同是 key不存在value时，Lpop返回null，BLpop则一直阻塞，直到 key中有元素或者达到超时时间，BLpop支持多个key！

# ————1、有一个列表存在，有一个不存在：
[127.0.0.1:6379> lpush mylist a b  # 初始化mylist列表，增加 “a"、"b" 两个元素
(integer) 2

# 从mylist、mylist2两个列表的左端各弹出一个元素（mylist2不存在！）
[127.0.0.1:6379> blpop mylist mylist2 5
1) "mylist“  # mylist 弹出元素“b"成功，mylist2不存在，故不会弹出
2) "b"

# mylist列表所有元素
[127.0.0.1:6379> lrange mylist 0 -1
1) "a"

# mylist2列表所有元素
[127.0.0.1:6379> lrange mylist2 0 -1
(empty array)


# ————2、列表不存在：
[127.0.0.1:6379> blpop mylist 5 # 从mylist列表中的左端弹出一个元素，设置超时5秒
(nil)
(5.05s)  # 未达到5秒前，一直保持连接，5秒后自动断连

结论：指定的key列表中有一个不为null，就不会被阻塞，而是返回该key和弹出的元素。如果有多个key都不为空，依次从左往右，找到第一个不为null的，然后返回！