List 结构存储值与结构读写能力: 一个链表,链表上的每个节点都包含了一个字符串 从链表的两端推入或者弹出元素; 根据偏移量对链表进行修剪(trim); 读取单个或多个元素; 根据值查找或者移除元素. 存储可以重复的数据 List 其底层有 LinkedList，ZipList 和 QuickList 这三种存储方式。 链表 LinkedList 与 Java 中的 LinkedList 类似，Redis中的 LinkedList 使一个双向链表，也是由一个个节点组成的。Redis 中借助 C语言实现的链表节点结构如下所示：
//定义链表节点的结构体
typedf struct listNode{
//前一个节点
struct listNode *prev;
//后一个节点
struct listNode *next;
//当前节点的值的指针
void *value;
}listNode;
pre指向前一个节点，next 指向后一个节点，value 保存着当前节点对应的数据对象。listNode的示意图如下所示：
链表的结构如下
typedf struct list{
//头指针
listNode *head;
//尾指针
listNode *tail;
//节点拷贝函数
void *(*dup)(void *ptr);
//释放节点函数
void *(*free)(void *ptr);
//判断两个节点是否相等的函数
int (*match)(void *ptr,void *key);
//链表长度
unsigned long len;
}
链表 ZipList
typedf struct ziplist<T>{
//压缩列表占用字符数
int32 zlbytes;
//最后一个元素距离起始位置的偏移量，用于快速定位最后一个节点
int32 zltail_offset;
//元素个数
int16 zllength;
//元素内容
T[] entries;
//结束位 0xFF
int8 zlend;
}ziplist
zipList 结构如下
注意 zltail_offset 这个参数，有了这个参数就可以快速定位到最后一个 entry节点的位置，然后开始倒序遍历，也就是说 zipList 支持双向遍历。 下面是 entry的结构
typede struct entry{
//前一个entry的长度
int<var> prelen;
//元素类型编码
int<var> encoding;
//元素内容
optional byte[] content;
}entry
prelen 保存的是前一个entry 字节的长度，这样在倒序遍历时就可以通过这个参数定位到上一个 entry 的位置。encoding 保存了 content 的编码类型。content 则是保存的元素内容，它是 optional类型的，表示这个字段时可选的。当conteng 是很小的整数时，它会内联到 content字段的尾部。entry结构的示意图如下：
现在有一个问题，为什么有了 linkedList 还要设计一个 zipList，就像 zipList 的名字一样，它是一个压缩列表，是为了节约内存而开发的。相比于 linkedList，其少了 pre 和 next 两个指针。在 Redis中，pre 和 next 指针就要占用 16 个字节（64位系统一个指针就是8个字节）。另外，linkedList的每个节点的内存都是单独分配的，加剧内存的碎片化，影响内存的管理效率。与之相比的是，zipList是连续的内存组成的，这样一来，由于内存是连续的，就减少了许多内存碎片和指针的内存占用，进而节约了内存。 zipList 遍历时，现根据 zlBytes 和 zltail_offset 定位到最后一个 entry 的位置，然后再根据最后一个 entry 里的prelen确定前一个 entry 的位置。 连锁更新 上面说到了，zipList 的entry 中有一个 prelen字段，它的长度要么是 1 字节，要么都是 5 字节： 前一个节点的长度小于 254 个字节，则 prelen 长度为 1 字节。 前一个节点的长度大于等于 254个字节，则 prelen 长度为 5字节。 假设现在有一组压缩列表，长度都在 250 ~ 253 之间，突然新增一个 entry 节点，这个 entry节点长度大于等于 254字节。由于新的 entry 节点大于等于 254字节，这个 entry 节点的prelen为 5 个字节，随后会导致其余的所有 entry 节点的 prelen 增大为 5字节。
同样的，删除操作也会出现连锁更新这种情况，假设在某一时刻，插入一个长度大于等于 254 的 entry节点，同时删除其后面的一个长度小于 254的 entry 节点，由于小于等于 254 的entry 字节的删除，大于等于 254 个字节的entry 的节点将会与后面小于 254个字节的 entry 节点相连，此时就与新增一个长度等于 254 个字节的 entry 节点的情况一样，将会发生连续更新。发生连续更新时，Redis就需要不断地对压缩列表进行内存分配工作，直到结束。 linkedList 与 zipList 的对比 1. 当列表对象中的长度较小或者数量较少时，通常采用 zipList 来存储；当列表中元素的长度较大或者数量比较多的时候，则会转而使用双向链表 linkedList 来存储。 2. 双向链表 linkedList 便于在表的两端进行 push 和pop 操作，在插入节点复杂度上很低，但是它的内存开销比较大。首先，它在每个节点上除了要保存数据之外，还有额外保存两个指针；其次，双向链表都是单独维护的内存块，地址不连续，容易形成内存碎片。 3. zipList 存储在一块连续的内存上，所以存储效率很高。但是他不利于修改操作，插入和删除操作需要频繁的申请和释放内存。特别是当 zipList 长度很长时，一次 realloc 可能会导致大量的数据拷贝。
链表 quickList quickList 时由 zipList 和双向链表 linkedList 组成的混合体。他将 linkedList按段切分，每一段使用 zipList 来紧凑存储，多个zipList 之间使用使用双向指针串起来。示意图如下所示：
节点 quickListNode的定义如下：
typedf struct quicklistNode{
//前一个节点
quicklistNode* prev;
//后一个节点
quicklistNode* next;
//压缩列表
ziplist* zl;
//ziplist大小
int32 size;
//ziplist 中元素数量
int16 count;
//编码形式 存储 ziplist 还是进行 LZF 压缩储存的zipList
int2 encoding;
...
}quickListNode
quickList的定义如下所示：
typedf struct quicklist{
//指向头结点
quicklistNode* head;
//指向尾节点
quicklistNode* tail;
//元素总数
long count;
//quicklistNode节点的个数
int nodes;
//压缩算法深度
int compressDepth;
...
}quickList
标签：字节,Redis,zipList,List,链表,内存,entry,数据结构,节点 From： https://www.cnblogs.com/qiezi777/p/16877607.html