Redis 学习之链表

简介

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

一、Redis 链表底层数据结构

1.1 节点定义

  1. typedef struct listNode {
  2.     // 前置节点
  3.     struct listNode *prev;
  4.     // 后置节点
  5.     struct listNode *next;
  6.     // 节点的值
  7.     void *value;
  8. } listNode;

redis之listNode图示.png

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

1.2 Redis list 内部定义

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

redis之list结构图示.png

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 命令

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

2.2 RPUSHX 命令

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

2.3 LLEN 命令

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

2.4 LPUSH

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

2.5 LPUSHX

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

2.6 LPOP 命令

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

2.7 RPOP 命令

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

2.8 LINDEX 命令

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

2.9 LINSERT 命令

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

2.10 LSET 命令

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

2.11 LREM 命令

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

2.12 阻塞的命令

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

三、了解 Redis list 的应用场景

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

参考