1 介绍

在 Redis 中，List 数据结构包括两种主要实现方式：双向链表和压缩列表。这两者是互斥的，即在同一个 List 中，Redis 会根据一定的条件选择使用其中的一种数据结构。

2 重要概念

下面是关于 Redis 列表的一些重要概念和实现细节：

  1. 双向链表：双向链表是其中一种 Redis 列表的底层数据结构，它由多个节点组成。每个节点包含了一个字符串元素和指向前一个节点和后一个节点的指针。这使得在插入和删除操作时可以在 O (1) 时间内完成。
  2. 压缩列表：压缩列表也是其中一种 Redis 列表的底层数据结构，是一种在特定场景下（小型元素、数量较少）非常高效的数据结构，能够在存储和性能方面提供优势。
  3. 头部和尾部操作：Redis允许在列表的头部和尾部执行以下操作，它们都具有O(1)的复杂度：
    • LPUSH：将一个或多个元素添加到列表的头部。
    • RPUSH：将一个或多个元素添加到列表的尾部。
    • LPOP：移除并返回列表的头部元素。
    • RPOP：移除并返回列表的尾部元素。
  4. 范围操作：Redis列表还支持按范围获取元素，如LRANGE，它可以用来获取列表中指定范围内的元素。
  5. 阻塞操作：Redis还支持阻塞操作，如BLPOP和BRPOP，它们会在列表为空时等待元素的到来，然后执行操作。
  6. 索引操作：你可以使用LINDEX来获取列表中指定索引位置的元素。
  7. 长度操作：你可以使用LLEN来获取列表的长度（元素数量）。
  8. 修剪操作：你可以使用LTRIM来截取列表的一部分，保留指定范围内的元素。
  9. 阻塞弹出：BRPOPLPUSH操作允许你从一个列表尾部弹出元素，并将它插入到另一个列表的头部，这是原子操作，可以用于实现任务队列。 Redis 的列表是非常实用的数据结构，可用于实现各种数据结构，如队列、堆栈，消息队列，任务队列等。由于其高效的插入和删除操作，它在实时应用中经常被使用。

3 简单使用方式

在 Redis 中，我们可以使用列表（List）数据结构来存储一个有序的、可以重复的字符串元素集合。下面是 Redis 列表的一些简单使用示例以及对应的 Redis 命令：

1. 添加元素到列表：

使用 LPUSH 或 RPUSH 命令可以将一个或多个元素添加到列表的头部或尾部。例如：

LPUSH mylist "item1"       # 将 "item1" 添加到列表头部
RPUSH mylist "item2"       # 将 "item2" 添加到列表尾部

2. 获取元素：

使用 LRANGE 命令可以获取列表中指定范围内的元素。例如，要获取列表中的所有元素，可以执行：

LRANGE mylist 0 -1

3. 弹出元素：

使用 LPOP 或 RPOP 命令可以移除并返回列表的头部或尾部元素。例如：

LPOP mylist              # 移除并返回列表头部元素
RPOP mylist              # 移除并返回列表尾部元素

4. 获取列表长度：

使用 LLEN 命令可以获取列表的长度，即元素的数量。例如：

LLEN mylist

5. 阻塞弹出：

使用 BLPOP 或 BRPOP 命令可以进行阻塞弹出操作，等待列表中有元素后再执行。这可用于实现任务队列。例如：

BLPOP mylist 0           # 阻塞等待并移除列表头部元素

6. 列表修剪：

使用 LTRIM 命令可以截取列表的一部分，保留指定范围内的元素。例如，保留前 10 个元素：

LTRIM mylist 0 9

7. 阻塞弹出与发布与订阅（Pub/Sub）：

你可以使用 BLPOP 或 BRPOP 命令来创建阻塞式的任务队列，然后使用 Redis 的发布与订阅功能，让不同部分的应用程序之间实现实时消息传递。通过在列表上执行 BLPOP 来等待新任务的到来，然后将结果通过发布与订阅机制通知其他部分的应用程序。

8. 列表合并与集合运算：

Redis 的列表还支持列表的合并操作，这意味着你可以将两个或多个列表合并成一个新列表，这对于实现交集、并集和差集等集合运算非常有用。你可以使用 BRPOPLPUSH 命令来原子性地将元素从一个列表弹出并插入到另一个列表中，从而实现集合运算。

9. 实现消息队列（Message Queue）：

Redis 列表是构建轻量级消息队列的理想选择。你可以使用 RPUSH 将消息推送到队列中，然后使用 BLPOP 来获取并处理消息。这种方式可以有效地实现任务分发和处理。

10. 定时任务调度：

你可以使用列表来实现定时任务调度，将任务和它们的执行时间存储在列表中，并使用定时程序（例如 Cron）来轮询列表，然后执行到期的任务。

11. 实现缓存淘汰策略：

列表还可以用于实现缓存淘汰策略。你可以使用 LPUSH 或 RPUSH 命令将新数据添加到列表中，同时使用 LTRIM 命令来控制列表的长度，以限制缓存的大小。这可以用于实现最近最少使用（LRU）等缓存策略。

Redis 列表是非常灵活的数据结构，你可以根据需要将其应用于各种场景，包括任务队列、消息队列、数据缓存等。结合不同的 Redis 命令和功能，你可以创建高效的、实时的应用程序。

4 两种实现

4.1.1 双向链表：

双向链表是 Redis 中 List 的常规实现方式，它使用 listNode 结构体来表示每个节点，并通过 list 结构体来维护整个链表。这种实现适用于元素较多或元素较大的情况，因为它提供了高灵活性和较低的复杂度，支持快速的头部和尾部插入、删除操作。 双向链表（Doubly Linked List）是一种常见的线性数据结构，它由节点构成，每个节点除了包含数据（或称为值）外，还包含两个指针，分别指向前一个节点（前驱）和后一个节点（后继）。这两个指针使得在双向链表中可以在节点间双向移动，这是与单向链表的主要区别。

4.1.1.1 双向链表的基本结构

在 C 语言中，双向链表可以通过如下的结构体表示：

typedef struct listNode {
    struct listNode *prev;  // 指向前一个节点的指针
    struct listNode *next;  // 指向后一个节点的指针
    void *value;            // 节点存储的值
} listNode;

typedef struct list {
    listNode *head;         // 指向链表头部的指针
    listNode *tail;         // 指向链表尾部的指针
    unsigned long len;      // 链表中节点的数量
    void *(*dup)(void *ptr);  // 复制节点值的函数指针
    void (*free)(void *ptr);  // 释放节点值的函数指针
    int (*match)(void *ptr, void *key);  // 比较节点值的函数指针
} list;

4.1.1.2 双向链表的基本操作

  1. 头部插入（Push Front）：

    • 在链表头部插入一个新节点。

  2. 尾部插入（Push Back）：

    • 在链表尾部插入一个新节点。

  3. 头部删除（Pop Front）：

    • 删除链表头部的节点。

  4. 尾部删除（Pop Back）：

    • 删除链表尾部的节点。

  5. 节点遍历：

    • 遍历整个链表，访问每个节点的值。

4.1.1.3 双向链表的优势

  1. 灵活性： 双向链表可以从头到尾或从尾到头遍历，提供了更灵活的遍历方式。
  2. 插入和删除高效： 在双向链表中，插入和删除节点的操作相对单向链表更加高效，因为在删除或插入节点时，只需修改相邻节点的指针即可。
  3. 反向遍历： 可以轻松实现反向遍历，从尾部到头部。

4.1.1.4 双向链表的劣势

  1. 额外的指针开销： 由于每个节点包含两个指针，占用了额外的内存空间。
  2. 不利于空间局部性： 在内存中并不是顺序存储的，可能导致缓存不命中。

4.1.2 压缩列表

压缩列表是一种紧凑的数据结构，适用于元素较小且数量较少的情况。它使用 ziplist 结构体来表示整个压缩列表，并通过 zlentry 结构体表示每个节点。压缩列表通过不同的编码方式来存储整数或字符串元素，以节省内存空间。

当 Redis 中的 List 数据结构中的元素较小、数量较少时，为了节省内存空间，Redis 使用一种称为压缩列表（ziplist）的特殊数据结构。

4.1.2.1 压缩列表结构

压缩列表是一块紧凑的内存块，其中包含了一系列元素。压缩列表的结构由两个主要部分组成：ziplist 结构体和 zlentry 结构体。

  1. ziplist 结构体：

    • ziplist 结构体表示整个压缩列表。
    typedef struct ziplist {
    unsigned char *zl;
    unsigned int zlbytes, zltail, zllen, entrysize;
} ziplist;
    • zl 是指向压缩列表内存块的指针。
    • zlbytes 是压缩列表的总字节数。
    • zltail 是压缩列表的尾部偏移量。
    • zllen 是压缩列表中的元素数量。
    • entrysize 是一个用于保存元素大小的辅助变量，用于快速获取元素的大小。

  2. zlentry 结构体：

    • zlentry 结构体表示压缩列表中的每个节点，即每个元素。
    typedef struct zlentry {
    unsigned int prevrawlensize, prevrawlen;
    unsigned int lensize, len;
    unsigned int headersize;
    unsigned char encoding;
    unsigned char *p;
} zlentry;
    • prevrawlensize 和 prevrawlen 用于记录前一个节点（元素）的大小，这是为了支持快速反向遍历。
    • lensize 和 len 表示当前节点（元素）的大小。
    • headersize 表示节点头的大小，包括编码、长度等的大小。
    • encoding 表示元素的编码方式，可以是整数编码或字符串编码。
    • p 是指向元素内容的指针。

4.1.2.2 压缩列表编码方式

压缩列表通过不同的编码方式存储整数和字符串，这使得压缩列表在存储不同类型元素时更加灵活。

  1. 整数编码：

    压缩列表为整数提供了两种编码方式，取决于整数的大小：

    • 对于较小的整数（例如 12 位以内的正整数和负整数），压缩列表采用直接存储整数值的方式，不占用额外空间。这种编码方式非常紧凑，适用于小范围的整数。

    • 对于较大的整数，压缩列表采用变长编码方式。这种方式的特点是根据整数的大小动态选择使用 1 字节、2 字节、3 字节等不同长度的存储空间。这样，可以在保证存储整数准确的前提下，尽量减小存储空间的占用。

  2. 字符串编码：

    压缩列表为字符串提供了两种编码方式，根据字符串的长度决定：

    • 对于较短的字符串，压缩列表采用字节数加前缀长度的方式存储。这意味着字符串的长度被编码为一个字节，然后跟随着字符串的实际内容。这种方式适用于小型字符串，避免了额外的长度开销。

    • 对于较长的字符串，压缩列表采用字节数加后缀长度的方式存储。这种方式在编码时需要额外的字节数来表示字符串的长度，但可以更灵活地适应较大的字符串。压缩列表通过动态选择编码方式，平衡了空间利用率和读取效率。

通过这种灵活的编码方式，压缩列表在存储不同类型和大小的元素时能够更好地平衡内存占用和读写效率。

4.1.2.3 压缩列表的优势

  1. 紧凑的内存布局： 压缩列表通过将多个元素存储在一个紧凑的内存块中，减少了指针和节点的开销，从而降低了内存占用。
  2. 灵活的编码方式： 压缩列表采用不同的编码方式，根据元素的实际大小灵活选择编码方式，提高了存储效率。
  3. 快速的读写操作： 压缩列表的紧凑结构和简单的编码方式使得读取和写入操作变得更加高效。

4.1.2.4 压缩列表的劣势

  1. 不适用于大型元素： 由于压缩列表是将多个元素存储在一个内存块中，对于大型元素可能导致内存碎片和性能下降。

  2. 不适用于频繁的插入和删除操作： 压缩列表对插入和删除操作的支持不如双向链表高效。

5 小结

Redis中的List数据结构包括双向链表和压缩列表两种实现方式。双向链表适用于元素较多、较大的场景，提供高灵活性和高效的插入删除操作。压缩列表适用于小型、数量较少的场景，通过紧凑的内存布局和灵活的编码方式降低内存占用，适合读取操作频繁的情况。Redis会根据实际情况动态选择最优的数据结构以平衡性能和内存占用。