Redis--链表（linked-list）数据结构和常用命令

迷南。 2021-08-13 15:41 264阅读 0赞

#### Redis链表（linked-list）数据结构和常用命令 ####

链表结构是 Redis 中一个常用的结构，它可以存储多个字符串，而且它是有序的，能够存储 2 的 32 次方减 1 个节点（超过 40 亿个节点）。

Redis 链表是双向的，因此即可以从左到右，也可以从右到左遍历它存储的节点，链表结构如图 1 所示。

![图 1  链表结构][1]

由于是双向链表，所以只能够从左到右，或者从右到左地访问和操作链表里面的数据节点。但是使用链表结构就意味着读性能的丧失，所以要在大量数据中找到一个节点的操作性能是不佳的，因为链表只能从一个方向中去遍历所要节点。

比如从查找节点 10 000 开始查询，它需要按照节点 1、节点 2、节点 3……直至节点 10 000，这样的顺序查找，然后把一个个节点和你给出的值比对，才能确定节点所在。如果这个链表很大，如有上百万个节点，可能需要遍历几十万次才能找到所需要的节点，显然查找性能是不佳的。

而链表结构的优势在于插入和删除的便利，因为链表的数据节点是分配在不同的内存区域的，并不连续，只是根据上一个节点保存下一个节点的顺序来索引而已，无需移动元素。其新增和删除的操作如图 2 所示。

![图 2  链表的新增和删除操作][2]图 2 的阿拉伯数字代表新增的步骤，而汉字数字代表删除步骤。

**1）新增节点**  
对插入图中的节点 4 而言，先看从左到右的指向，先让节点 4 指向节点 1 原来的下一个节点，也就是节点 2，然后让节点 1 指向节点 4，这样就完成了从左到右的指向修改。再看从右到左，先让节点 4 指向节点 1，然后节点 2 指向节点 4，这个时候就完成了从右到左的指向，那么节点 1 和节点 2 之间的原有关联关系都已经失效，这样就完成了在链表中新增节点4的功能。

**2）删除节点**  
对删除图中的节点 3 而言，首先让节点 2 从左到右指向后续节点，然后让后续节点指向节点 2，这样节点 3 就脱离了链表，也就是断绝了与节点 2 和后继节点的关联关系，然后对节点 3 进行内存回收，无须移动任何节点，就完成了删除。

由此可见，链表结构的使用是需要注意场景的，对于那些经常需要对数据进行插入和删除的列表数据使用它是十分方便的，因为它可以在不移动其他节点的情况下完成插入和删除。而对于需要经常查找的，使用它性能并不佳，它只能从左到右或者从右到左的查找和比对。

因为是双向链表结构，所以 Redis 链表命令分为左操作和右操作两种命令，左操作就意味着是从左到右，右操作就意味着是从右到左。Redis 关于链表的命令如表 1 所示。

<table>  表 1 Redis关于链表的命令  
 <tbody> 
  <tr> 
   <th> 命&nbsp;&nbsp; 令</th> 
   <th> 说&nbsp;&nbsp; 明</th> 
   <th> 备&nbsp;&nbsp; 注</th> 
  </tr> 
  <tr> 
   <td> lpush key node1 [node2.].....&nbsp;</td> 
   <td> 把节点 node1 加入到链表最左边</td> 
   <td> 如果是 node1、node2 ...noden 这样加入， 那么链表开头从左到右的顺序是 noden...node2、node1</td> 
  </tr> 
  <tr> 
   <td> rpush key node1[node2]......</td> 
   <td> 把节点 node1 加入到链表的最右边</td> 
   <td> 如果是 node1、node2....noden 这样加&nbsp; 入，那么链表结尾从左到右的顺序是 node1、node2,node3...noden</td> 
  </tr> 
  <tr> 
   <td> lindex key index</td> 
   <td> 读取下标为 index 的节点</td> 
   <td> 返回节点字符串，从 0 开始算</td> 
  </tr> 
  <tr> 
   <td> llen key</td> 
   <td> 求链表的长度</td> 
   <td> 返回链表节点数</td> 
  </tr> 
  <tr> 
   <td> lpop key</td> 
   <td> 删除左边第一个节点，并将其返回</td> 
   <td> ——</td> 
  </tr> 
  <tr> 
   <td> rpop key</td> 
   <td> 删除右边第一个节点，并将其返回</td> 
   <td> <br> ——</td> 
  </tr> 
  <tr> 
   <td> linsert key before|after pivot node</td> 
   <td> 插入一个节点 node，并且可以指定在值为pivot 的节点的前面（before）或者后面（after)）</td> 
   <td> 如果 list 不存在，则报错；如果没有值为对应 pivot 的，也会插入失败返回 -1</td> 
  </tr> 
  <tr> 
   <td> lpushx list node&nbsp;</td> 
   <td> 如果存在 key 为 list 的链表，则插入节点 node, 并且作为从左到右的第一个节点&nbsp;</td> 
   <td> 如果 list 不存在，则失败</td> 
  </tr> 
  <tr> 
   <td> rpushx list node&nbsp;</td> 
   <td> 如果存在 key 为 list 的链表，则插入节点 node，并且作为从左到右的最后个节点</td> 
   <td> 如果 list 不存在，则失败</td> 
  </tr> 
  <tr> 
   <td> lrange list start end</td> 
   <td> 获取链表 list 从 start 下标到 end 下标的节点值</td> 
   <td> 包含 start 和 end 下标的值</td> 
  </tr> 
  <tr> 
   <td> lrem list count value</td> 
   <td> 如果 count 为 0，则删除所有值等于 value 的节 点：如果 count 不是 0，则先对 count 取绝对值，假设记为 abs，然后从左到右删除不大于 abs 个等于 value 的节点</td> 
   <td> 注意，count 为整数，如果是负数，则 Redis 会先求取其绝对值，然后传递到后台操作</td> 
  </tr> 
  <tr> 
   <td> lset key index node</td> 
   <td> 设置列表下标为 index 的节点的值为 node</td> 
   <td> ——</td> 
  </tr> 
  <tr> 
   <td> ltrim key start stop</td> 
   <td> 修剪链表，只保留从 start 到 stop 的区间的节点，其余的都删除掉</td> 
   <td> 包含 start 和 end 的下标的节点会保留</td> 
  </tr> 
 </tbody> 
</table>

**示例**  
在Redis中，List类型是按照插入顺序排序的字符串链表。和数据结构中的普通链表 一样，我们可以在其头部(left)和尾部(right)添加新的元素。在插入时，如果该键并不 存在，Redis将为该键创建一个新的链表。与此相反，如果链表中所有的元素均被移 除，那么该键也将会被从数据库中删除。List中可以包含的最大元素数量是 4294967295。

从元素插入和删除的效率视角来看，如果我们是在链表的两头插入或删除元素，这将 会是非常高效的操作，即使链表中已经存储了百万条记录，该操作也可以在常量时间 内完成。然而需要说明的是，如果元素插入或删除操作是作用于链表中间，那将会是 非常低效的。相信对于有良好数据结构基础的开发者而言，这一点并不难理解。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70]

1.  **lpush key value1 value2…：** 在指定的key所关联的list的头部插入所有的 values，如果该key不存在，该命令在插入的之前创建一个与该key关联的空链 表，之后再向该链表的头部插入数据。插入成功，返回元素的个数。
2.  **rpush key value1、value2…：** 在该list的尾部添加元素
3.  **lrange key start end：** 获取链表中从start到end的元素的值，start、end可 为负数，若为-1则表示链表尾部的元素，-2则表示倒数第二个，依次类推…

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 1]  
4. **lindex key index:** 读取下标为 index 的节点 返回节点字符串，从 0 开始算  
5. **llen key:** 求链表的长度 返回链表节点数  
6. **lpop key:** 删除左边第一个节点，并将其返回  
7. **rpop key:** 删除右边第一个节点，并将其返回  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 2]  
8. **linsert key before|after pivot value：** 在pivot元素前或者后插入value这个元素。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 3]  
9. **lpushx key value：** 仅当参数中指定的key存在时（如果与key管理的list中没 有值时，则该key是不存在的）在指定的key所关联的list的头部插入value。  
10. **rpushx key value：** 在该list的尾部添加元素

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 4]  
11. **lrem key count value：** 删除count个值为value的元素，如果count大于0，从头向尾遍历并删除count个值为value的元素，如果count小于0，则从尾向头遍历并删除。如果count等于0，则删除链表中所有等于value的元素。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 5]  
12. **lset key index value：** 设置链表中的index的脚标的元素值，0代表链表的头元 素，-1代表链表的尾元素。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 6]  
13. **ltrim key start stop:** 修剪链表，只保留从 start 到 stop 的区间的节点，其余的都删除掉 包含 start 和 end 的下标的节点会保留

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 7]

1.  **rpoplpush resource destination：** 将链表中的尾部元素弹出并添加到头部  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 8]

这里展示了关于 Redis 链表的常用命令，只是对于大量数据操作的时候，我们需要考虑插入和删除内容的大小，因为这将是十分消耗性能的命令，会导致 Redis 服务器的卡顿。对于不允许卡顿的一些服务器，可以进行分批次操作，以避免出现卡顿。

需要指出的是，之前这些操作链表的命令都是进程不安全的，因为当我们操作这些命令的时候，其他 Redis 的客户端也可能操作同一个链表，这样就会造成并发数据安全和一致性的问题，尤其是当你操作一个数据量不小的链表结构时，常常会遇到这样的问题。

为了克服这些问题，Redis 提供了链表的阻塞命令，它们在运行的时候，会给链表加锁，以保证操作链表的命令安全性，如表 2 所示。

<table>  表 2 链表的阻塞命令  
 <tbody> 
  <tr> 
   <th> 命&nbsp;&nbsp; 令</th> 
   <th> 说&nbsp;&nbsp; 明</th> 
   <th> 备&nbsp;&nbsp; 注</th> 
  </tr> 
  <tr> 
   <td> blpop key timeout</td> 
   <td> 移出并获取列表的第一个元索，如果列表没有元素会阻塞列表直到等待超时或发现可弹出元索为止&nbsp;</td> 
   <td> 相对于 lpop 命令，它的操作是进程安全的</td> 
  </tr> 
  <tr> 
   <td> brpop key timeout</td> 
   <td> 移出并获取列表的最后一个元素，如果列表没有元素会阻塞列表直到等待超时或发现可弹出元素为止</td> 
   <td> 相对于 rpop 命令，它的操作是进程安全的</td> 
  </tr> 
  <tr> 
   <td> rpoplpush key sre dest</td> 
   <td> 按从左到右的顺序，将一个链表的最后一个元素移除，并插入到目标链表最左边</td> 
   <td> 不能设置超时时间</td> 
  </tr> 
  <tr> 
   <td> brpoplpush key src dest timeout</td> 
   <td> 按从左到右的顺序，将一个链表的最后一个元素移除，并插入到目标链表最左边，并可以设置超时时间</td> 
   <td> 可设置超时时间</td> 
  </tr> 
 </tbody> 
</table>

当使用这些命令时，Redis 就会对对应的链表加锁，加锁的结果就是其他的进程不能再读取或者写入该链表，只能等待命令结束。加锁的好处可以保证在多线程并发环境中数据的一致性，保证一些重要数据的一致性，比如账户的金额、商品的数量。

不过在保证这些的同时也要付出其他线程等待、线程环境切换等代价，这将使得系统的并发能力下降，关于多线程并发锁，未来还会提及，这里先看 Redis 链表阻塞操作命令，如图 4 所示。

![图四][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 9]

在实际的项目中，虽然阻塞可以有效保证了数据的一致性，但是阻塞就意味着其他进程的等待，CPU 需要给其他线程挂起、恢复等操作，更多的时候我们希望的并不是阻塞的处理请求，所以这些命令在实际中使用得并不多，后面还会深入探讨关于高并发锁的问题。

[1]: /images/20210813/90137a8607ea4eb79f41cbf8d95409fa.png
[2]: /images/20210813/ab33836d39024644b248ee96315408bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70]: /images/20210813/18fc5aeb8596453f988fb4ab525c370d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 1]: /images/20210813/64468d31b1ab4c4491e180b0987afb35.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 2]: /images/20210813/51f8d50ccfbc4c51a0e017eb9eaa4b67.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 3]: /images/20210813/248f2287fc4f4385898dfa74f8e57488.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 4]: /images/20210813/682b045155c8415091094545e663c72b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 5]: /images/20210813/fdb958eb5cd84b078e16618b7ade32f3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 6]: /images/20210813/bb7af4b10b434e0cb1c9f503da9fc50a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 7]: /images/20210813/a3ca7f83f8e6457dbc040e33e892e700.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 8]: /images/20210813/d220039b69ba433aaf672db89cde8fe2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 9]: /images/20210813/7ef47e2755a94173bfd5f5a8c8106cbb.png