List存储结构
- Redis3.2前,底层是用压缩列表zipList\双向循环链表linkedList
当list存储的数据量比较少,且同时满足下面两个条件时,list就使用zipList存储数据
- list保存的每个元素长度小于64字节
- 列表中数据个数少于512个
- Redis3.2及之后的底层实现方式:quickList
quickList是双向链表,而且是一个基于zipList的双向链表,quickList的每个节点都是一个zipList,结合了双向链表和zipList的优点.
压缩列表(zipList)
压缩链表. 好处:节省内存空间,因为它存储的内容都是在连续的内存区域当中的.当列表对象元素不大,每个元素也不大的时候,就采用zipList存储. 但当数据量过大时,zipList就不那么好用了. 因为为了保证它存储内容在内存中的连续性,插入的复杂度为O(N),即每次插入都会重新进行realloc.
zipList的结构如下:
zipList的数据结构
- zlbytes: 用于记录整个压缩列表占用的内存字节数.
- zltail:记录列表尾节点距离压缩列表的起始地址有多少字节
- zllen:记录了压缩列表包含的节点数量
- entryX:列表包含的各个节点
- zlend:用于标记压缩列表的末端
为什么数据量大的时候不用zipList?
因为zipList是一段连续的内存,插入的时间复杂度O(n),而且每当插入新的元素需要realloc做内存拓展;而且如果超出zipList内存大小,还会做重新分配的内存空间,并将内容复制到新的地址. 如果数量大的话,重新分配内存和拷贝内存会消耗大量时间. 所以不适合大型字符串,也不适合存储量多的元素.
快速列表(quickList)
是zipList和linkedList的混合体,是将linkedList按段切分,每一段用zipList来紧凑存储,多个zipList之间使用双向指针链接.
为什么不直接使用linkedList?
linkedList的附加空间相对太高,prev和next指针就要占去16字节,而且每个节点都是单独分配,会加剧内存的碎片化,影响内存管理效率.
quickList结构如下
typedef struct quicklist {
// 指向quicklist的头部
quicklistNode *head;
// 指向quicklist的尾部
quicklistNode *tail;
unsigned long count;
unsigned int len;
// ziplist大小限定，由list-max-ziplist-size给定
int fill : 16;
// 节点压缩深度设置，由list-compress-depth给定
unsigned int compress : 16;
} quicklist;
typedef struct quicklistNode {
// 指向上一个ziplist节点
struct quicklistNode *prev;
// 指向下一个ziplist节点
struct quicklistNode *next;
// 数据指针，如果没有被压缩，就指向ziplist结构，反之指向quicklistLZF结构
unsigned char *zl;
// 表示指向ziplist结构的总长度(内存占用长度)
unsigned int sz;
// ziplist数量
unsigned int count : 16; /* count of items in ziplist */
unsigned int encoding : 2; /* RAW==1 or LZF==2 */
// 预留字段，存放数据的方式，1--NONE，2--ziplist
unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */
// 解压标记，当查看一个被压缩的数据时，需要暂时解压，标记此参数为1，之后再重新进行压缩
unsigned int recompress : 1; /* was this node previous compressed? */
unsigned int attempted_compress : 1; /* node can't compress; too small */
// 扩展字段
unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;
typedef struct quicklistLZF {
// LZF压缩后占用的字节数
unsigned int sz; /* LZF size in bytes*/
// 柔性数组，存放压缩后的ziplist字节数组
char compressed[];
} quicklistLZF;
结构图如下:
quickList结构图
zipList的长度
内部默认单个zipList的长度为8K字节,超出了这个字节数,就会新起一个zipList.关于长度可以使用list-max-zipList-size决定.
压缩深度
quickList是由多个zipList组成的,同时为了进一步节省空间,Redis还会对zipList进行压缩存储,使用LZF算法压缩,可以选择压缩深度.quickList默认压缩深度为0,即不压缩. 压缩的实际深度由配置参数list-compress-depth决定.为了支持快速push/pop操作,quickList的首尾两个zipList不压缩,此时深度就是1.如果深度为2,就表示quickList的首尾第一个zipList以及首尾第二个zipList都不压缩.
网友评论