Redis学习笔记之链表

Redis 学习之链表

简介

• Redis lists 能保存 2^32 - 1 个元素，40 亿个元素
• Redis lists 是双向链表的数据结构

一、Redis 链表底层数据结构

1.1 节点定义

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

从图中可以看出，Redis list 结构采用双向链表的数据结构

1.2 Redis list 内部定义

typedef struct list {
    // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    // 链表所包含的节点数量
    unsigned long len;
    // 节点值复制函数(dup 函数用于复制链表节点所保存的值；)
    void *(*dup)(void *ptr);
    // 节点值释放函数(free 函数用于释放链表节点所保存的值；)
    void (*free)(void *ptr);
    // 节点值对比函数(match 函数则用于对比链表节点所保存的值和另一个输入值是否相等。)
    int (*match)(void *ptr, void *key);
} list;

1.3 Redis list 的特性

• 双端： 链表节点带有 prev 和 next 指针， 获取某个节点的前置节点和后置节点的复杂度都是 O(1) 。
• 无环： 表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL ， 对链表的访问以 NULL 为终点。
• 带表头指针和表尾指针： 通过 list 结构的 head 指针和 tail 指针， 程序获取链表的表头节点和表尾节点的复杂度为 O(1) 。
• 带链表长度计数器： 程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数， 程序获取链表中节点数量的复杂度为 O(1) 。
• 多态： 链表节点使用 void* 指针来保存节点值， 并且可以通过 list 结构的 dup 、 free 、 match 三个属性为节点值设置类型特定函数， 所以链表可以用于保存各种不同类型的值。

二、Redis list 常用命令学习

2.1 RPUSH 命令

#语法 RPUSH key value1 value2 ...
# 向存于 key 的列表的尾部插入所有指定的值
# 如果 key 不存在，那么会创建一个空的列表然后再进行 push 操作。
# 返回值为 list的长度
127.0.0.1:0>RPUSH mylist "Hello"
"1"
127.0.0.1:0>RPUSH mylist "World" "!"
"3"

2.2 RPUSHX 命令

# 将值 value 插入到列表 key 的表尾, 当且仅当 key 存在并且是一个列表。
# 当key不存在时，不做操作
# 返回值为 list的长度
127.0.0.1:0>RPUSHX mylist "Java"
"4"
# 因为myNewList 不存在，所以不会创建空的list，并进行push操作
127.0.0.1:0>RPUSHX myNewList "new"
"0"
# 查看keys
127.0.0.1:0>keys *
 1)  "num"
 2)  "mylist"
 3)  "age"
 4)  "num2"
 5)  "a"
 6)  "num4"
 7)  "num3"
 8)  "name"
 9)  "b"
 10)  "test"
 11)  "num1"
 12)  "mykey"

2.3 LLEN 命令

# 返回存储在 key 里的list的长度。
127.0.0.1:0>llen mylist
"4"
# 如果key 不存在，则返回0
127.0.0.1:0>llen myNewList
"0"
# 当存储在 key 里的值不是一个list的话，会返回error。
127.0.0.1:0>llen num
"WRONGTYPE Operation against a key holding the wrong kind of value"

2.4 LPUSH

# 与RPUSH 命令 类似
# 将所有指定的值插入到存于 key 的列表的头部。
# 在 push 操作后的 list 长度
127.0.0.1:0>LPush list1  Java python
"2"
127.0.0.1:0>lrange list1 0 -1
 1)  "python"
 2)  "Java"

2.5 LPUSHX

# RPUSHX 命令类似
# 将值 value 插入到列表 key 的表头, 当且仅当 key 存在并且是一个列表。
# 返回值为 list的长度
127.0.0.1:0>LPUSHX list1 c++
"3"
127.0.0.1:0>lrange list1 0 -1
 1)  "c++"
 2)  "python"
 3)  "Java"
 # 当key不存在时，不做操作
 127.0.0.1:0>LPUSHX list2 c++
"0"

2.6 LPOP 命令

# 移除并且返回 key 对应的 list 的第一个元素
# 当key 不存在时，返回null
127.0.0.1:0>lpop list1
"c++"
127.0.0.1:0>lpop  list3
null

2.7 RPOP 命令

# 移除并返回存于 key 的 list 的最后一个元素。
127.0.0.1:0>rpop list1
"Java"
127.0.0.1:0>rpop list3
null

2.8 LINDEX 命令

#返回列表里的元素的索引 index 存储在 key 里面。 下标是从0开始索引的
#list1 列表的长度为1
127.0.0.1:0>llen  list1
"1"
#取出第一位
127.0.0.1:0>lindex list1 0
"python"

2.9 LINSERT 命令

#把 value 插入存于 key 的列表中在基准值 pivot 的前面或后面。
#当 key 不存在时，这个list会被看作是空list，任何操作都不会发生。
#当 key 存在，但保存的不是一个list的时候，会返回error。
# 在列表list1 的元素python 前插入Java元素
127.0.0.1:0>LINSERT list1 BEFORE python Java
"2"
127.0.0.1:0>lrange list1 0 -1
1)  "Java"
2)  "python"
# 元素python 后插入Java元素
127.0.0.1:0>LINSERT list1 AFTER  python Java
"3"
127.0.0.1:0>lrange list1 0 -1
1)  "Java"
2)  "python"
3)  "Java"

2.10 LSET 命令

#设置 index 位置的list元素的值为 value
#设置地三个元素为c++
127.0.0.1:0>lset list1 2 c++
"OK"
127.0.0.1:0>lrange list1 0 -1
 1)  "Java"
 2)  "python"
 3)  "c++"

2.11 LREM 命令

#从存于 key 的列表里移除前 count 次出现的值为 value 的元素。
# count > 0: 从头往尾移除值为 value 的元素。
# count < 0: 从尾往头移除值为 value 的元素。
# count = 0: 移除所有值为 value 的元素。
#语法 LREM key count value
127.0.0.1:0>lpush list1 java
"4"
127.0.0.1:0>lpush list1 java
"5"
127.0.0.1:0>lpush list1 java
"6"
#删除前两次出现的java
127.0.0.1:0>lrem list1 2 java
"2"
127.0.0.1:0>lrange list1 0 -1
 1)  "java"
 2)  "Java"
 3)  "python"
 4)  "c++"

2.12 阻塞的命令

# BLPOP、BRPOP是阻塞式列表的弹出命令，当给定列表没有数据时，则会阻塞客户端，直到列表有元素
127.0.0.1:0>rpush list java
"1"
# 0 代表不设置超时，但不能为负数
127.0.0.1:0>brpop list 0
 1)  "list"
 2)  "java"
# list中没有元素阻塞
127.0.0.1:0>brpop list 0

三、了解 Redis list 的应用场景

• 事务模块使用双端链表依序保存输入的命令；
• 服务器模块使用双端链表来保存多个客户端；
• 订阅/发送模块使用双端链表来保存订阅模式的多个客户端；
• 事件模块使用双端链表来保存时间事件（time event)

参考

• 《Redis 设计与实现》
• http://www.redis.cn/commands/rpush.html
• https://redis.io/commands