Redis数据结构之list- 惊觉

演进：3.2 之前小 list 用 ziplist、大 list 用 linkedlist；3.2 起统一为 quicklist（双向链表 + 每节点挂一块 ziplist）；7.0 起节点内的 ziplist 换成 listpack。

3.2 以后 OBJECT ENCODING 对 list 始终返回 quicklist。

一、List 数据结构

1.1 基本特点

有序：元素按插入顺序排列，支持下标访问（下标从 0 开始，支持负数：-1 表示倒数第一个）；
可重复：允许相同元素；
两端高效：左/右两端的插入、弹出都是 O(1)，中间操作需要遍历，是 O(N)；
单列表最多 2³²−1 个元素。

1.2 quicklist 真实结构

quicklist（整个列表）
┌────────────────────────────────────────────────┐
│ head ──► node0 ◄──► node1 ◄──► node2 ◄── tail  │
│ count = 元素总数                                │
└────────────────────────────────────────────────┘
            │           │           │
            ▼           ▼           ▼
       ┌─────────┐ ┌─────────┐ ┌─────────┐
       │listpack │ │listpack │ │listpack │
       │ a b c d │ │ e f g h │ │ i j k l │   ← 每个节点管理一片连续紧凑内存
       └─────────┘ └─────────┘ └─────────┘

关键结构体（源码）：

typedef struct quicklist {
    quicklistNode *head;        // 头节点
    quicklistNode *tail;        // 尾节点
    unsigned long count;        // 所有节点元素总数
    ...
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev; // 前驱
    struct quicklistNode *next; // 后继
    unsigned char *entry;       // 指向 listpack（旧版为 ziplist）
    size_t sz;                  // listpack 的字节大小
    unsigned int count;         // 本节点元素数
    ...
} quicklistNode;

真正负责管理一片连续空间的是 quicklistNode 的 prev、next、entry（外加 sz、count 字段），而"数组"其实是每个节点里的 listpack。

二、常用命令

2.1 添加操作

1）右端插入

RPUSH key value [value ...]

2）左端插入

LPUSH key value [value ...]

返回插入后列表长度。

多个元素按顺序依次插入，注意 LPUSH key a b c 后列表顺序是 c b a（每个元素都从左边插入），而RPUSH key a b c 后列表顺序是 a b c

127.0.0.1:6379> rpush list1 a b c
(integer) 3
127.0.0.1:6379> lrange list1 0 -1
1) "a" 2) "b" 3) "c"
127.0.0.1:6379> flushall
OK
127.0.0.1:6379> rpush key a b c
3
127.0.0.1:6379> lrange key 0 -1
1)"a" 2) "b" 3)"c"

3）在指定元素前/后插入

LINSERT key BEFORE|AFTER pivot value

从左向右找第一个 pivot，在其前/后插入 value；
返回值：成功返回插入后的列表长度；pivot 不存在返回 -1；key 不存在返回 0；
时间复杂度 O(N)，需要遍历。

2.2 查找操作

1）获取指定范围（闭区间 [start, end]）

LRANGE key start end

超出范围时自动取有效交集，不会报错；
支持负数下标，LRANGE key 0 -1 取全部；
复杂度 O(S+N)，S 为偏移量、N 为返回数量。

2）获取指定下标元素

LINDEX key index

⚠️ 下标越界时返回 (nil)。复杂度 O(N)（要沿节点链表 + listpack 顺序查找）。

3）获取长度

LLEN key

O(1)，quicklist 头部维护 count。

2.3 删除操作

1）左端弹出

LPOP key

2）右端弹出

RPOP key

空列表返回 nil（6.2 起支持 LPOP key count 一次弹出多个）。

3）删除指定元素

LREM key count value

count	行为
count > 0	从左向右，最多删除 count 个与 value 相等的元素
count < 0	从右向左，最多删除 \|count\| 个
count = 0	删除全部与 value 相等的元素

返回实际删除的元素个数，O(N)。

4）按范围修剪（保留区间，删除其余）

LTRIM key start end

保留闭区间 [start, end] 内的元素，其余全部删除。常配合 LPUSH 实现定长列表，O(N)。

2.4 修改操作

LSET key index newValue

修改指定下标元素，这个命令 index 越界会报错（ERR index out of range），注意与 LINDEX 越界返回 nil 区分。O(N)。

2.5 阻塞式弹出 BLPOP / BRPOP

BLPOP key [key ...] timeout
BRPOP key [key ...] timeout

行为规则：

按参数中 key 的从左到右顺序检查，对第一个非空列表执行弹出，立即返回 [key, 弹出的值] 两个元素；
所有 key 都为空时：
- timeout > 0：阻塞等待 timeout 秒（单位秒），超时返回 nil；
- timeout = 0：一直阻塞，直到有数据；
多个客户端同时阻塞在同一个 key 上时，数据到达按先到先得唤醒。

# 客户端 A
127.0.0.1:6379> blpop task 0
# 此时阻塞……

# 客户端 B
127.0.0.1:6379> lpush task job1
# 客户端 A 立即被唤醒并返回：
1) "task"
2) "job1"

阻塞到底发生在哪里？（重点）

Redis 服务器不会阻塞！执行 BLPOP 时，服务器发现列表为空，就把这个客户端挂到该 key 的阻塞等待链表上，然后继续处理其他客户端的命令；
当其他客户端对该 key 执行 LPUSH/RPUSH 时，服务器检查阻塞链表，主动唤醒等待者并把数据推给它；
阻塞只体现在客户端（连接上没有响应返回，客户端等待）。

三、quicklist 的内部编码细节

3.1 编码结论

3.2 以后所有 list 统一使用 quicklist
7.0 起 quicklist 节点的容器由 ziplist 变为 listpack，消除连锁更新风险；
OBJECT ENCODING key 返回 quicklist。

3.2 两个关键配置

# 每个 quicklist 节点的大小限制
list-max-listpack-size -2          # 旧版叫 list-max-ziplist-size

# 两端各保留多少个节点不压缩
list-compress-depth 0

list-max-listpack-size 取值：

取值	含义
正数 n	单个节点最多存 n 个元素
-1	单个节点最大 4KB
-2（默认）	最大 8KB
-3 / -4 / -5	16KB / 32KB / 64KB

list-compress-depth（LZF 压缩）：

0：不压缩（默认）；
1：两端各留 1 个节点不压缩，中间节点用 LZF 压缩；
2：两端各留 2 个不压缩，以此类推。

两端节点不压缩是因为两端操作最频繁，中间节点访问少，压缩以牺牲少量 CPU 换取内存节省。

3.3 时间复杂度汇总

命令	复杂度
LPUSH / RPUSH / LPOP / RPOP / BLPOP / BRPOP	O(1)
LLEN	O(1)
LINSERT / LREM / LTRIM / LINDEX / LSET	O(N)
LRANGE	O(S+N)

四、使用场景

4.1 四种经典组合

组合	效果
`LPUSH + LPOP`	Stack（栈）：同端进出，后进先出 LIFO
`LPUSH + RPOP`	Queue（队列）：异端进出，先进先出 FIFO
`LPUSH + LTRIM`	Capped Collection（定长集合）：只保留最新 N 条
`LPUSH + BRPOP`	Message Queue（阻塞消息队列）

定长列表示例（只保留最新 10 条动态）：

LPUSH feeds user:1:newpost
LTRIM feeds 0 9

4.2 阻塞消息队列

生产者 LPUSH task job，消费者 BRPOP task 0 阻塞等待，天然实现任务分发。

局限（需要知道边界）：

消息一旦 POP 就从 Redis 删除，没有 ACK 确认机制，消费者处理到一半宕机，消息就丢了；
没有消费组、广播、消息回溯等能力；
复杂可靠的消息流应使用 Redis 5.0 的 Stream（或专业 MQ）。

4.3 与 Hash 配合：文章列表

Hash 存文章正文（每个对象一个 hash，多对象的同一类属性）：

hset article:1 title xxx timestamp xxx content xxx
hset article:k title yyy timestamp yyy content yyy

List 存文章 ID 顺序：

lpush user:1:articles article:1 article:2

查询时两级查找：先从 list 按时间顺序取出文章 ID，再用 ID 去 hash 里取正文：

lrange user:1:articles 0 9        # 先取最新 10 篇的 ID
hgetall article:1                 # 再取正文

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/bksczm/article/details/168974971

Redis数据结构之list