code前端网什么是 Redis 列表？三个底层数据结构原理分析
1.什么是 Redis List
作为 Java 开发者，这个词对你来说并不陌生。 Java 开发中几乎每天都会用到这种数据结构。
Redis 的 List 类似于 Java 中的 LinkedList。它是一种线性排序结构，可以按照元素被推入列表的顺序存储元素。可以满足“先进先出”的要求。这些元素可以是文本。该数据也可以是二进制数据。
您可以将其用作队列或堆栈。
2。修心
我叫Redis。 C语言没有现成的链表结构，所以antire专门为我设计了一套实现方法。
List类型背后的数据结构英雄有很多。antire大佬对其进行了优化，并创建了不同的数据结构来存储它。
从一开始，早期版本就使用linkedlist（双端列表）和ziplist（压缩列表）♓作为实现列表（压缩列表）♓♓。 Redis 3.2 引入了由 quicklist 组成的 linklist + ziplist，在 7.0 版本中，使用 listpackp 代替❿♓♓ 。 MySQL：“为什么有这么多数据结构？” antire z 这一切都是为了在开销和访问性能之间达到折中和平衡。跟随我深入了解每种类型。您了解设计理念和缺陷。 在Redis 3.2版本之前，底层的List数据结构是用linkedlist或者ziplist实现的，优先选择ziplist存储。 当列表对象满足以下两个条件时，使用ziplist保存列表，否则使用链表。 链表的节点由 链表的结构如图2-5所示。 图2-5 Redis链表实现的属性总结如下。 MySQL：“看起来没有问题，为什么需要ziplist？” 如你所知，我痴迷于追求速度和节省内存。 ziplist 被弃用的原因有两个。出生。 为了解决上述两个问题，antirez 创建了 ziplist 压缩列表，它是一种紧凑的内存数据结构，占用恒定的内存空间，提高内存利用率。 当列表中只有少量信息，并且每个列表项要么是一个小整数，要么是一个相对较短的字符串时，我在List应用程序的后台使用ziplist文件。 ziplist 可以包含多个输入节点。每个节点可以存储一个整数或字符串。其结构如图2-6所示。 图2-6 查找中间元素时，只能遍历链表尾部或尾部，时间复杂度为O(N)。 让我们看看实际存储数据的注释结构是什么样的。 图2-7 通常由三部分组成： prevlen 存储前一个条目使用的字节数。逆序遍历依靠该字段来确定前进多少字节才能获得前一个条目的首地址。 这部分是根据前一个条目的长度进行变长编码的（我担心节省内存）。变长方法如下。 encoding 简单来说就是用来表示当前条目的类型和长度。当前条目的长度和值由它是int还是string以及数据的长度决定。 前两个数字用于指示类型。如果当前两个数字是“11”，则表示该条目存储的是int类型的数据，另外两个表示存储的是字符串。 entry-data 实际保存数据的字段。需要注意的是，如果条目存储为int类型，则编码和输入数据合并为一个编码，并且没有输入数据字段。 目前结构变为 MySQL：“为什么 ziplist 节省内存？” MySQL：“听起来很完美，为什么要使用快速列表？” 很难同时满足需要和需求。 ziplist 节省内存，但它也有一些缺点。 链更新 每个条目都使用 prevlen 命令来存储前一个条目的长度。当新条目 A 添加到现有条目 B 之前时，会导致 B 的 prevlen 发生变化，并且条目 B 的大小也会发生变化。 。此外，必须更改位于条目 B 之后的条目 C。类似地，它可以导致链更新。 图2-8 链更新会导致ziplist内存空间被重新分配多次，直接影响ziplist查询性能。所以Redis 3.2版本中引入了Quicklist。 quicklist是一种考虑时间和空间效率的新数据结构。 结合了原始链接列表和zip列表的优点。本质上还是一个链表，但是链表中的每个节点都是一个ziplist。数据结构 在文件 quicklist.h 中定义。链表由 quicklist是双向链表，因此每个quicklist节点都有一个前序指针（ quicklist作为链表定义了头指针和尾指针，用于快速定位链表的头和尾。 连同 图2-9 从结构上来看，Pikalist是ziplist的更新版本。优化的关键点是控制每个ziplist中元素的大小或数量。 根配置非常重要。 Redis 提供 ，当 linkedlist（双端列表）
adlist.h/listNode结构表示。 typedef struct listNode {
// 前驱节点
struct listNode *prev;
// 后驱节点
struct listNode *next;
// 指向节点的值
void *value;
} listNode;
listNode通过前一个和后一个指针构造一个双向链表。另外，我还提供了adlist.h/list结构体，它提供了头指针head、尾指针tail以及一些实现多态性的特殊函数。 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;
图2-5ziplist（压缩列表）
图2-6
。如果超过这个大小，则使用链接列表来存储数据。每个值具有以下含义： 
图2-7 。
图2-8quicklist
quicklist 结构定义。每个节点都使用结构体定义quicklistNo de（源代码版本是6.2和7.0版本使用listpack而不是ziplist）。 *prev）和后序指针（t*t）。每个节点都是一个ziplist，因此还有一个指向ziplist的指针*zl。 typedef struct quicklistNode {
// 前序节点指针
struct quicklistNode *prev;
// 后序节点指针
struct quicklistNode *next;
// 指向 ziplist 的指针
unsigned char *zl;
// ziplist 字节大小
unsigned int sz;
// ziplst 元素个数
unsigned int count : 16;
// 编码格式，1 = RAW 代表未压缩原生ziplist，2=LZF 压缩存储
unsigned int encoding : 2;
// 节点持有的数据类型，默认值 = 2 表示是 ziplist
unsigned int container : 2;
// 节点持有的 ziplist 是否经过解压， 1 表示已经解压过，下一次操作需要重新压缩。
unsigned int recompress : 1;
// ziplist 数据是否可压缩，太小数据不需要压缩
unsigned int attempted_compress : 1;
// 预留字段
unsigned int extra : 10;
} quicklistNode;
typedef struct quicklist {
// 链表头指针
quicklistNode *head;
// 链表尾指针
quicklistNode *tail;
// 所有 ziplist 的总 entry 个数
unsigned long count;
// quicklistNode 个数
unsigned long len;
int fill : QL_FILL_BITS;
unsigned int compress : QL_COMP_BITS;
unsigned int bookmark_count: QL_BM_BITS;
// 柔性数组，给节点添加标签，通过名称定位节点，实现随机访问的效果
quicklistBookmark bookmarks[];
} quicklist;
quicklist和quicklistNode定义，链接到quicklist的列表结构如下图所示。 
图2-9list-max-ziplist-size -2、list-max-ziplist-size 为 ♿♷❓ 时，为负数 表示每个 ziplist 的内存大小限制ziplist 节点
版权声明
本文仅代表作者观点，不代表Code前端网立场。
本文系作者Code前端网发表，如需转载，请注明页面地址。
