Redis 数据结构之 List - Redis 数据库 | 方家小白 = 和你一起遇见更好的自己

# 书接上回

上一篇文章 Redis 的数据结构 string 我们一起学习了这种类型的常用命令，并且还学习了 Redis 中的字符串的结构表示以及好处，这里我们接着学习另外一种数据结构 list 。

# `list` 简介

list , 一般都会称为列表。在 Redis 中，这种数据结构是一种比较灵活的结构，由于其元素的是有序的，所以可以充当栈和队列这两种数据结构。实际在开发总也有很多应用场景。

一个 List 最多可以包含 2^32-1 个元素。

很多人都会以为 list 是用数组来实现的，非也，非也。它内部是 quicklist 这种数据结构。想要先睹为快的，那么坐电梯直达吧。

# `list` 的相关命令

# `LPUSH` 命令

语法

LPUSH key value [value …]

解释

lpush : left push 。

将一个或者多个值插入到列表 key 的表头，返回列表的长度。元素可以是重复的。

如果 key 不存在，那么会先穿件一个列表，然后再执行 push 操作.

如果 key 值存在，但是 value 类型不是列表类型时，会返回一个错误。

演示

# 设置一个列表
127.0.0.1:6379> LPUSH k22 v22
(integer) 1
# 查询指定区间内的数据,使用lrange命令
127.0.0.1:6379> LRANGE k22 0 10
1) "v22"
# 一次插入多个值
127.0.0.1:6379> LPUSH k22 v22_1 v22_2 v22_3 v22_4
(integer) 5
127.0.0.1:6379> LRANGE k22 0 10
1) "v22_4"
2) "v22_3"
3) "v22_2"
4) "v22_1"
5) "v22"

# `lpushx` 命令

语法

LPUSHX key value

解释

仅当 key 存在的时候，才将 value 插入列表的表头。返回列表中元素的个数。

演示

# 当key值不存在的时候，不会放入列表中
127.0.0.1:6379> LPUSHX k23 v23
(integer) 0
# 再次尝试放入，也不可以。
127.0.0.1:6379> LPUSHX k23 v23
(integer) 0
# 先往数组放入一个元素
127.0.0.1:6379> lpush k23 v23
(integer) 1
# 再次尝试使用lpushx放入数据
127.0.0.1:6379> LPUSHX k23 v23_1
(integer) 2
# 再次尝试使用lpushx放入数据
127.0.0.1:6379> LPUSHX k23 v23_2
(integer) 3
# 查看列表 k23 中的数据。注意：和插入的顺序是相反的。
127.0.0.1:6379> Lrange k23 0 -1
1) "v23_2"
2) "v23_1"
3) "v23"

# `rpush` 命令

语法

RPUSH key value [value ...]

解释

rpush 就是 right push 。将一个或多个值 value 插入到列表 key 的表尾 (最右边)。返回列表的长度。

如果 key 不存在的时候，会创建一个空列表，然后在执行 rpush 操作。

如果 key 存在，但是不是一个列表类型时，返回一个错误。

演示

# 往列表中加入数据
127.0.0.1:6379> RPUSH k24 v24
(integer) 1
127.0.0.1:6379> RPUSH k24 v24_1 v25_2 v25_3
(integer) 4
127.0.0.1:6379> lrange k24 0 -1
1) "v24"
2) "v24_1"
3) "v25_2"
4) "v25_3"
# 演示 key 存在，但是不是一个列表类型
127.0.0.1:6379> set k24_1 v24_1
OK
127.0.0.1:6379> rpush k24_1 v24_1
(error) WRONGTYPE Operation against a key holding the wrong kind of value

# `rpushx` 命令

语法

rpushx key value

解释

与 lpushx 类似，如果 key 不存在时，什么都不会操作。如果 key 存在，才会将元素添加到表尾。

演示

# key不存在的时候，不会插入数据
127.0.0.1:6379> rpushx k25 v25
(integer) 0
# 先设置一个列表
127.0.0.1:6379> rpush k25 v25_1
(integer) 1
127.0.0.1:6379> rpushx k25 v25_2
(integer) 2
127.0.0.1:6379> rpushx k25 v25_3
(integer) 3
# 查看列表中的数据。注意和插入的顺序是一致的。
127.0.0.1:6379> lrange k25 0 -1
1) "v25_1"
2) "v25_2"
3) "v25_3"

# `lpop` 命令

语法

LPOP key

解释

left pop ;

移除并返回列表的头元素。当 key 不存在的时候，返回 nil

演示

# key不存在的时候，返回nil
127.0.0.1:6379> LPOP k26
(nil)
# 设置一个列表，有三个元素
127.0.0.1:6379> lpush k26 v26_1 v26_2 v26_3
(integer) 3
# 查看列表中的元素
127.0.0.1:6379> lrange k26 0 -1
1) "v26_3"
2) "v26_2"
3) "v26_1"
# 依次pop出元素
127.0.0.1:6379> lpop k26
"v26_3"
127.0.0.1:6379> lpop k26
"v26_2"
127.0.0.1:6379> lpop k26
"v26_1"
127.0.0.1:6379> lpop k26
(nil)

tip： lpush + lpop => 栈， rpush + lpop => 队列。

# `rpop` 命令

语法

rpop key

解释

rpop ： right pop ;

和 lpop 相反。移除并返回列表的尾元素。如果 key 不存在返回 nil。

演示

# key 不存在，返回nil
127.0.0.1:6379> rpop k27
(nil)
# 先设置一个列表
127.0.0.1:6379> lpush k27 v27_1 v27_2 v27_3
(integer) 3
127.0.0.1:6379> lrange k27 0 -1
1) "v27_3"
2) "v27_2"
3) "v27_1"
# 一次pop每个值
127.0.0.1:6379> rpop k27
"v27_1"
127.0.0.1:6379> rpop k27
"v27_2"
127.0.0.1:6379> rpop k27
"v27_3"
127.0.0.1:6379> rpop k27
(nil)

tip: lpush + rpop => 队列， rpush + rpop => 栈。

# `lrange` 命令

语法

LRANGE key start stop

解释

获取指定区间内的元素。0 表示第一个元素。如果超过了实际范围就返回空数组。

演示

127.0.0.1:6379> LRANGE k22 0 10
1) "v22_4"
2) "v22_3"
3) "v22_2"
4) "v22_1"
5) "v22"
127.0.0.1:6379> LRANGE k22 0 1
1) "v22_4"
2) "v22_3"
127.0.0.1:6379> LRANGE k22 10 100
(empty list or set)

# `rpoplpush` 命令

语法

RPOPLPUSH source destination

解释

将 source 的尾元素插入到 destination 列表的头元素中，返回该元素。注意，这是一个原子操作。

比如: source : a,b,c

distination : 1,2,3

使用 RPOPLPUSH source distination , 则：

source : a,b

distination : c,1,2,3

演示

# 设置列表1
127.0.0.1:6379> lpush k28_1 v28_c v28_b v28_a
(integer) 3
# 设置列表2
127.0.0.1:6379> lpush k28_2 v28_3 v28_2 v28_1
(integer) 3
# 使用 rpoppush命令
127.0.0.1:6379> RPOPLPUSH k28_1 k28_2
"v28_c"
# 查看列表1
127.0.0.1:6379> lrange k28_1 0 -1
1) "v28_a"
2) "v28_b"
# 查看列表2
127.0.0.1:6379> lrange k28_2 0 -1
1) "v28_c"
2) "v28_1"
3) "v28_2"
4) "v28_3"

# `lrem` 命令

语法

LREM key count value

解释

至多移除列表中 count 个与参数 value 相等的元素。

有以下情況:

count > 0 : 从表头开始向表尾搜索，移除与 value 相等的元素，最多移除 count 个。

count < 0 : 从表尾开始向表头搜索，移除与 value 相等的元素，最多移除 |count| 个。

count = 0 : 移除表中所有与 value 相等的值。

演示

# 演示 count>0 时
# 设置一个列表
127.0.0.1:6379> lpush k29_1 v29_1  v29  v29_2 v29 v29_3 v29
(integer) 6
# 从表头开始，移除2个 v29
127.0.0.1:6379> lrem k29_1 2 v29
(integer) 2
127.0.0.1:6379> lrange k29_1 0 -1
1) "v29_3"
2) "v29_2"
3) "v29"
4) "v29_1"
# 演示count<0 时
127.0.0.1:6379> lpush k29_2 v29_1 v29  v29_2 v29 v29_3 v29
(integer) 6
127.0.0.1:6379> lrem k29_2 -2 v29
(integer) 2
127.0.0.1:6379> LRANGE k29_2 0 -1
1) "v29"
2) "v29_3"
3) "v29_2"
4) "v29_1"

# 演示count=0时
127.0.0.1:6379> lpush k29_3 v29_1 v29  v29_2 v29 v29_3 v29
(integer) 6
127.0.0.1:6379> lrem k29_3 0 v29
(integer) 3
127.0.0.1:6379> LRANGE k29_3 0 -1
1) "v29_3"
2) "v29_2"
3) "v29_1"

# `llen` 命令

语法

LLEN key

解释

获取列表的长度。

如果 key 不存在的时候，返回 0 .

如果 key 对应类型不是 list ，则返回一个错误。

演示

127.0.0.1:6379> llen k30
(integer) 0
127.0.0.1:6379> lpush k30 v30_1 v30_2
(integer) 2
127.0.0.1:6379> llen k30
(integer) 2

# 删掉k30，演示，类型不是list的时候，报错
127.0.0.1:6379> del k30
(integer) 1
127.0.0.1:6379> set k30 v30
OK
127.0.0.1:6379> llen k30
(error) WRONGTYPE Operation against a key holding the wrong kind of value

# `lindex` 命令

语法

lindex key index

解释

返回列表中，下标为 index 的元素. -1 表示列表的最后一个元素，如果 key 不存在，或者 index 超出范围，返回 nil ，如果 key 不是一个列表类型，返回一个错误。

演示

127.0.0.1:6379> lpush k31 v31_3 v31_2 v31_1
(integer) 3
127.0.0.1:6379> LINDEX k31 2
"v31_3"
127.0.0.1:6379> LINDEX k31 1
"v31_2"
127.0.0.1:6379> LINDEX k31 0
"v31_1"

# `linsert` 命令

语法

linsert key BEFORE|AFTER pivot value

解释

将 value 插入到 key 队列 pivot 值之前或者之后。返回插入完成之后列表的长度。

如果 pivot 不存在或者 key 不存在，不执行任何操作。

如果 key 对应的不是一个列表类型，返回一个错误。

演示

127.0.0.1:6379> linsert k32 BEFORE k31_1 k31_0
(integer) 0
127.0.0.1:6379> lpush k32 v32_1
(integer) 1
# k32_3 => pivot不存在
127.0.0.1:6379> linsert k32 BEFORE v32_3 v31_2
(integer) -1
# pivot之前插入
127.0.0.1:6379> linsert k32 BEFORE v32_1 v31_0
(integer) 2
# pivot之后插入
127.0.0.1:6379> linsert k32 AFTER v32_1 v31_2
(integer) 3

# lset 命令

语法

lset key index value

解释

将列表中的索引为 index 的值设置为 value 。如果 index 超出范围，则返回一个错误

演示

127.0.0.1:6379> lpush k33 v33_3 v33_1
(integer) 2
127.0.0.1:6379> lrange k33 0 -1
1) "v33_1"
2) "v33_3"
## 将第二个值，索引为1，设置为v33_2
127.0.0.1:6379> lset k33 1 v33_2
OK
127.0.0.1:6379> lrange k33 0 -1
1) "v33_1"
2) "v33_2"

# 超出范围返回错误
127.0.0.1:6379> lset k33 2 v33_2
(error) ERR index out of range

# `ltrim` 命令

语法

ltrim key start stop

解释

保留列表从 start 到 stop 之间的元素。其他元素都将被删除。注意：包含 (不删除) start 和 stop 两个元素.

如果 key 不存在，直接返回 OK , 如果 key 对应的不是列表，直接返回错误。

演示

127.0.0.1:6379> lpush k34 v34_1 v34_2 v34_3 v34_4 v34_5 v34_6
(integer) 6
127.0.0.1:6379> ltrim k34 1 4
OK
127.0.0.1:6379> lrange k34  0 -1
1) "v34_5"
2) "v34_4"
3) "v34_3"
4) "v34_2"

# blpop 命令

语法

BLPOP key [key ...] timeout

解释

lpop 的阻塞版本。 block left pop

当给定列表内没有任何元素可供弹出的时候，连接将被 BLPOP 命令阻塞，直到等待超时或发现可弹出元素为止。
当给定多个 key 参数时，按参数 key 的先后顺序依次检查各个列表，弹出第一个非空列表的头元素。

演示

# push到三组列表，分别三个元素
127.0.0.1:6379> lpush k35 v35_1 v35_2 v35_3
(integer) 3
127.0.0.1:6379> lrange k35 0 -1
1) "v35_3"
2) "v35_2"
3) "v35_1"
127.0.0.1:6379> lpush k35_1 v35_1 v35_2 v35_3
(integer) 3
127.0.0.1:6379> lpush k35_2 v35_1 v35_2 v35_3
(integer) 3

# 阻塞调用lpop, 从左到右 依次pop元素，直到有一个元素可以pop。
127.0.0.1:6379> blpop k35 k35_1 k35_2 10
1) "k35"
2) "v35_3"
127.0.0.1:6379> blpop k35 k35_1 k35_2 10
1) "k35"
2) "v35_2"
127.0.0.1:6379> blpop k35 k35_1 k35_2 10
1) "k35"
2) "v35_1"
127.0.0.1:6379> blpop k35 k35_1 k35_2 10
1) "k35_1"
2) "v35_3"
127.0.0.1:6379> blpop k35 k35_1 k35_2 10
1) "k35_1"
2) "v35_2"
127.0.0.1:6379> blpop k35 k35_1 k35_2 10
1) "k35_1"
2) "v35_1"
127.0.0.1:6379> blpop k35 k35_1 k35_2 10
1) "k35_2"
2) "v35_3"
127.0.0.1:6379> blpop k35 k35_1 k35_2 10
1) "k35_2"
2) "v35_2"
127.0.0.1:6379> blpop k35 k35_1 k35_2 10
1) "k35_2"
2) "v35_1"
127.0.0.1:6379> blpop k35 k35_1 k35_2 10
# 没有元素的时候会阻塞一直到超时。
(nil)
(10.59s)

# `brpop` 命令

语法

BRPOP key [key ...] timeout

解释

rpop 的阻塞版本。 block right pop
当给定多个 key 的时候，按照 key 的先后顺序依次检查各个列表。直到弹出一个元素或者超时。

演示

# 设置两个列表
127.0.0.1:6379> lpush k36 v36_1 v36_2 v36_3
(integer) 3
127.0.0.1:6379> lpush k36_1 v36_1 v36_2 v36_3
(integer) 3
# 阻塞式的pop出每个值。
127.0.0.1:6379> BRPOP k36 k36_1 10
1) "k36"
2) "v36_1"
127.0.0.1:6379> BRPOP k36 k36_1 10
1) "k36"
2) "v36_2"
127.0.0.1:6379> BRPOP k36 k36_1 10
1) "k36"
2) "v36_3"
127.0.0.1:6379> BRPOP k36 k36_1 10
1) "k36_1"
2) "v36_1"
127.0.0.1:6379> BRPOP k36 k36_1 10
1) "k36_1"
2) "v36_2"
127.0.0.1:6379> BRPOP k36 k36_1 10
1) "k36_1"
2) "v36_3"
127.0.0.1:6379> BRPOP k36 k36_1 10
# 阻塞10s
(nil)
(10.61s)

Tips: lpush + brpop => 阻塞队列。

# `brpoplpush` 命令

语法

BRPOPLPUSH source destination timeout

解释

rpoplpush 的阻塞版本。 block right left push 。

当列表 source 为空的时候，该命令将阻塞，直到超时，或者 source 中有一个元素可以 pop。

演示

# 设置一个列表
127.0.0.1:6379> lpush k37_source v37_1 v37_2 v37_3 v37_4
(integer) 4
# 将source移动到distination中。
127.0.0.1:6379> BRPOPLPUSH k37_source k37_distination 10
"v37_1"
# 查看下distination。
127.0.0.1:6379> lrange k37_distination 0 -1
1) "v37_1"
127.0.0.1:6379> BRPOPLPUSH k37_source k37_distination 10
"v37_2"
127.0.0.1:6379> BRPOPLPUSH k37_source k37_distination 10
"v37_3"
127.0.0.1:6379> BRPOPLPUSH k37_source k37_distination 10
"v37_4"

# 这时我们启动两个客户端,演示阻塞直到另一个客户端执行source列表中的插入操作。
# 客户端1中继续执行 BRPOPLPUSH, 然后马上在客户端2中，输入"LPUSH k37_source v37_5".

# 客户端1
127.0.0.1:6379> BRPOPLPUSH k37_source k37_distination 10
"v37_5"
(3.02s)
# 客户端2
127.0.0.1:6379> LPUSH k37_source v37_5
(integer) 1

# `list` 内部结构之 `quicklist`

# `quicklist`

我们来看一下 list 的内部实现 quicklist 结构.

特别注明： quicklist 是双向的链表结构。

在 Redis 中使用如下结构体表示.

typedef struct quicklist {
    // 头结点
    quicklistNode *head;
    // 尾结点
    quicklistNode *tail;
    // 列表的元素个数
    unsigned long count;
    // 链表的长度
    unsigned long len;
    // 单个节点的填充因子
    int fill : 16;
    // 不进行节点压缩的最大深度
    // 超过这个节点就会进行节点压缩
    unsigned int compress : 16;
} quicklist;

quicklist 是回一个通用的双向链接快速列表实现。它的每个节点用 quicklistNode 表示。

一起来看下 qucklistNode 是什么吧。

# `quicklistNode`

typedef struct quicklistNode {
    // 前一个节点
    struct quicklistNode *prev;
    // 后一个节点
    struct quicklistNode *next;
    // 数据指针。
    // 如果指向的数据没有被压缩,那么会指向zipList结构。
    // 如果进行了压缩，那么会指向 quickLZF结构。
    unsigned char *zl;
    // 当前节点的大小
    unsigned int sz;
    // 元素的个数
    unsigned int count : 16;
    // 编码方式，1=RAW，2=LZF
    // 1 表示未被压缩
    // 2 表示使用LZF结构进行的压缩
    unsigned int encoding : 2;   
    // 使用的容器是什么？1=NONE,2=ZIPLIST
    unsigned int container : 2;
    // 前一个节点是否被压缩
    unsigned int recompress : 1; 
    // 是否压缩
    unsigned int attempted_compress : 1; 
    // 暂时留出来，以后使用。
    unsigned int extra : 10;
} quicklistNode;

quicklistNode 是一个 32byte 的结构体，用于描述一个 quicklist 的一个节点。从代码中可看出，使用了位图来节约空间。在上面的代码中我们还提到两种数据结构，对应的是代码中 zl 指针，指向的位置，如果数据被压缩，指向 quicklistLZF 和没有数据没有被压缩就是指向 ziplist .

# `ziplist`

ziplist 这种结构比较复杂，而且在源码中也没有给出明确定义。那 ziplist 这么神秘的结构到底是什么样的呢？

别着急，我们先大体熟悉下 ziplist 这种结构的设计意图。

ziplist 是一个经过特殊编码的双向链表，它的设计意图就是提高存储效率， ziplist 可以用于存储字符串或者整数，其中整数是按照真正的二进制进行编码的。它能以 O(1) 的效率在表的两端进行 pop 和 push 操作。

我们都知道，普通的链表每项都是一块独立的内存空间，各项之间都是通过指针连接起来的。这种方式，会带来大量的空间碎片，指针引用也会占用部分空间内存。所以 ziplist 是将表中每项放在连续的空间内存中 (类似数组)， ziplist 还对值采取了一个可变长度的存储方式，大的值就用大空间，小的值就用小空间。

# ziplist 结构的官方定义。

The general layout of the ziplist is as follows:
<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
<uint32_t zlbytes> is an unsigned integer to hold the number of bytes that the ziplist occupies, including the four bytes of the zlbytes field itself. This value needs to be stored to be able to resize the entire structure without the need to traverse it first.
<uint32_t zltail> is the offset to the last entry in the list. This allows a pop operation on the far side of the list without the need for full traversal.
<uint16_t zllen> is the number of entries. When there are more than 2^16-2 entries, this value is set to 2^16-1 and we need to traverse the entire list to know how many items it holds.
<uint8_t zlend> is a special entry representing the end of the ziplist. Is encoded as a single byte equal to 255. No other normal entry starts with a byte set to the value of 255.

根据上面中解释我们可以得出以下这种模型：

如果没有特殊指定的话，都是采用小尾数法存储的。

zlbytes : 存储一个无符号整数，用于存储 ziplist 的所用的字节数，(包括 zlbytes 字段本身的四个字节)，当重新分配内容的时候，不需要遍历整个列表来计算内存大小。
zltail : 一个无符号整数，表示 ziplist 中最后一个元素的偏移字节数，这样可以方便的找到最后一个元素，从而可以以 O (1) 的复杂度在尾端进行 pop 和 push。
zllen：压缩列表包含的结点的个数，即entry的个数。
这里的 zllen 是占用 16bit , 也就是说最多存储 2^16-2 个。但是 ziplist 超了 2^16-2 个也是可以表示的。那种情况就是 16 个 1 的时候，只需要从头遍历到尾就好了。
entry : 真正存放数据的数据项，每个数据项都有自己的内部结构。
zlend : ziplist 的最后一个字节，值固定等于 255 ，就是一个结束标记。

# entry 结构

entry 是由三部分构成的。

previous length（pre_entry_length） ：表示前一个数据节点占用的总字节数，这个字段的用处是为了让 ziplist 能够从后向前遍历（从后一项的位置，只需向前偏移 previous length 个字节，就找到了前一项）。这个字段采用变长编码。
encoding （ encoding&cur_entry_length ）：表示当前数据节点 content 的内容类型以及长度。也采用变长编码。
entry-data ：表示当前节点存储的数据， entry-data 的内容类型有整数类型和字节数组类型，且某些条件下 entry-data 的长度可能为 0 。

所以我们可以得出 ziplist 是一个这样的结构。

有时，encoding 也可以代表 entry 本身，就像小整数一样。

这里就是大体的了解下 ziplist 这种数据结构。

这里是一篇关于 ziplist 详细解读的文章。

# `quicklistLZF`

看完了比较神秘的 ziplist 结构，我们来看一个比较简单的 quicklist 的压缩节点的结构 quicklistLZF 。

/**
 * quicklistLZF是一个4 + N字节的 struct。
 * sz 是 compressed 字段的字节长度。'compressed' 是长度为 sz的 LZF数据。
 *
 * 未被压缩的长度保存到 quicklistNode->sz中。
 *
 * 当压缩了quicklistNode->zl时，quicklistNode->zl指向的是一个 quicklistLZF类型的数据。
 * 未压缩的时候，指向的是ziplist.
 */
typedef struct quicklistLZF {
    ///compressed数组长度 
    unsigned int sz; 
    char compressed[];
} quicklistLZF;

# 总结

list 相关的命令。以及常见的应用场景。比如栈和队列等等。
list 其实是一种链表结构，但是不是一个普通的链表结构。
list 是由 quicklist 这种数据结构实现的。 quicklist 中的每个节点是 quicklistNode , 而 quicklist 中 zl 指针，指向的是一个 ziplist 或者 quickListLZF 。
ziplist 是一个比较神秘的数据结构，有 5 部分构成，是连续存储的，可以实现 O(1) 的尾端 pop 和 push 操作。

# 最后

期望与你一起遇见更好的自己

Redis

# 书接上回

# list 简介

# list 的相关命令

# LPUSH 命令

# lpushx 命令

# rpush 命令

# rpushx 命令

# lpop 命令

# rpop 命令

# lrange 命令

# rpoplpush 命令

# lrem 命令

# llen 命令

# lindex 命令

# linsert 命令