Redis数据结构之List

一、List类型简介

Redis 中列表（List）类型是用来存储多个有序的字符串，列表中的每个字符串成为元素 Eelement），一个列表最多可以存储 2^32-1 个元素，列表从一开始早期版本使用 LinkedList（双端列表）和 ZipList（压缩列表）作为 List 的底层实现，到 Redis 3.2 引入了由 LinkedList + ZipList 组成的 QuickList，再到 7.0 版本的时候使用 ListPack 取代 ZipList。

在 Redis 中，可以对列表两端插入（push）和弹出（pop），还可以获取指定范围的元素列表、获取指定索引下标的元素等。列表是一种比较灵活的数据结构，可以充当栈和队列的角色，在实际开发中有很多应用场景。

二、List使用场景

• Redis List用来创建消息队列。生产者可以使用LPUSH将任务推入列表，消费者可以使用BRPOP或BLPOP取出任务进行处理。
• Redis List来记录用户的行为，比如浏览历史、消息通知等。通过LPUSH将动作推入列表，通过LRANGE获取用户的动作记录。
• Redis List用来实现高效的分页。
• Redis List用来实现有序的排行榜，通过ZRANGE获取排行榜。
• Redis List用来实现时间轴功能。比如微博应用中用户发表一条微博就会被添加到自己的时间轴上，这个功能可以通过将每个用户的时间轴作为一个List来实现。
• 延迟任务队列

三、底层编码方式

在 Redis中List数据类型的底层实现采用了不同的编码方式，具体取决于存储的值大小。下面是 Redis中 List 数据类型的四种底层编码方式：

在 Redis3.2 版本前，Redis 列表 List 使用两种数据结构作为底层实现：

• 压缩列表 ZipList：插入元素过多或字符串太大，就需要调用 Realloc 扩展内存；
• 双向链表 LinkedList：需附加指针 Prev 和 Next，较浪费空间，加重内存的碎片化

Redis3.2 首先以 ZipList 进行存储,在不满足 ZipList 的存储要求后转换为 LinkedList 列表。当列表对象同时满足以下两个条件时,列表对象使用 ZipList 进行存储，否则用 LinkedList 存储。

• 列表对象保存的所有字符串元素的长度小于 64 字节；
• 列表对象保存的元素数量小于 512 个;

在 Redis3.2 版本后，Redis 列表使用 快速链表 QucikList 结构作为底层实现。

ListPack(紧凑列表)是Redis5版本出现的，作用是为了代替ZipList 。Redis7.0版本之后，listpack就完全替代了ZipList 。

四、List底层数据结构

Redis的List类型的储存结构,从redis所有版本包含的结构有四种，分别是LinkedList、ZipList、 QucikList 、ListPack，下面对这些结构分别进行分析。

①LINKEDLIST底层数据结构

LinkedList是一个双向链表，链表中每个节点都会存储指向上一个节点和指向下一个节点的指针。LinkedList因为每个节点的空间是不连续的，遍历的效率低下，同时当存储数据很小的情况下，指针占用的空间会超过数据占用的空间，因此可能会造成过多的空间碎片。

当列表对象满足以下两个条件的时候，List 将使用 ZipList 存储，否则使用 LinkedList

• List 的每个元素的占用的字节小于 64 字节。
• List 的元素数量小于 512 个。

Ⅰ、LINKEDLIST类对象

typedef struct list {   

// 头指针   

listNode *head;    

// 尾指针    

listNode *tail;   

// 节点值的复制函数    

void *(*dup)(void *ptr);    

// 节点值释放函数   

void (*free)(void *ptr);   

// 节点值比对是否相等    

int (*match)(void *ptr, void *key);    

// 链表的节点数量    unsigned long len;

} list;

• head指向链表的头节点
• tail指向链表的尾节点
• len表示这个链表共有多少个节点，这样就可以在O(1)的时间复杂度内获得链表的长度
• dup函数，用于链表转移复制时对节点value拷贝的一个实现，一般情况下使用等号足以，但在某些特殊情况下可能会用到节点转移函数，默认可以给这个函数赋值NULL，即表示使用等号进行节点转移
• free函数，用于释放一个节点所占用的内存空间，默认赋值NULL的话，可使用Redis自带的zfree()函数进行内存空间释放
• match函数，用来比较两个链表节点的value值是否相等，相等返回1，不等返回0

Ⅱ、LINKEDLIST中链表中每个节点类对象

typedef struct listNode {    

// 前驱节点    struct listNode *prev;    

// 后驱节点    struct listNode *next;    

// 指向节点的值    void *value;

} listNode;

Ⅲ、LINKEDLIST底层数据结构

②ZIPLIST底层数据结构

ZipList是经过特殊编码的双向链接列表，对于上面提到的LinkedList链表结构，由于内存中不是连续的，LinkedList多使用指针导致浪费内存空间、内存使用率都较低。为了解决这个问题，引入了 ZipList这种数据结构。 ZipList是一种有顺序、内存连续的数据结构。具备节省内存空间、提升内存使用率，适用于元素数量少且长度比较小的场景。在Redis 7.0版本之前是List、Hash、ZSet底层实现之一，但是自身也存在其他问题，因此在 Redis 7.0后被ListPack完全替换。

Ⅰ、ZIPLIST类对象

typedef struct ziplist{

     /*ziplist分配的内存大小*/

     uint32_t zlbytes;

     /*达到尾部的偏移量 */

     uint32_t zltail;

     /*存储元素实体个数*/

     uint16_t zllen;

     /*存储内容实体元素*/

     unsigned char* content[];

     /*尾部标识*/

     unsigned char zlend;

}ziplist;

• zlbytes：压缩列表的字节长度。
• zltail：压缩列表尾元素相对于压缩列表起始地址的偏移量（目的是为了直接定位到尾节点，方便反向查询）。
• zllen：压缩列表的元素个数。
• entry：各个节点数据。
• zlend：压缩列表的结尾，占一个字节，一直是0xFF（255）。

Ⅱ、ZIPLIST中节点(entry)类对象

typedef struct ziplistEntry {

    unsigned int pre_entry_len; // 前一个entry的长度编码大小

unsigned char encoding; // 节点编码方式

    unsigned char *content; // 指向当前entry数据的指针(节点的起始指针)

} ziplistEntry;

• pre_entry_length: 记录了前一个节点的长度，通过这个值，可以进行指针计算，从而跳转到上一个节点。
• 根据编码方式的不同， pre_entry_length 域可能占用 1 字节或者 5 字节。1 字节：如果前一节点的长度小于 254 字节，便使用一个字节保存它的值； 5字节：如果前一节点的长度大于等于 254 字节，那么将第 1 个字节的值设为 254 ，然后用接下来的 4 个字节保存实际长度。
• encoding表示编码类型

        字符串类型: 字符串类型有1、2、5三种编码长度，前两位表示编码类型，剩余位表示字符串长度。