一、redis原理之list底层数据结构ziplist和quicklist。

快速列表 quicklist【quicklist = 链表+ziplist】

• 首先在列表元素较少的情况下会使用一块连续的内存存储，这个结构是 ziplist ，即压缩列表 . 它将所有的元素紧挨着一起存储，分配的是一块连续的内存
• 当数据量比较多才会改成 quicklist.

本质上来说，quicklist里面保存着一个一个小的ziplist

 quickList就是一个标准的双向链表的配置，有head 有tail;

每一个节点是一个quicklistNode，包含prev和next指针。

每一个quicklistNode 包含 一个ziplist，*zp 压缩链表里存储键值。

所以quicklist是对ziplist进行一次封装，使用小块的ziplist来既保证了少使用内存，也保证了性能。

为啥不用普通的链表：因为普通的链表需要的附加指针空间太大，会比较浪费空间，而且会加重内存的碎片化 .

ziplist的结构：

struct ziplist<T> {
	int32 zlbytes; // 整个压缩列表占用字节数
	int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
	int16 zllength; // 元素个数
	T[] entries; // 元素内容列表，挨个挨个紧凑存储
	int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}

压缩列表ziplist是一块连续的内存空间，元素之间紧挨着存储，没有任何冗余空隙。

压缩列表为了支持双向遍历，所以才会有 ztail_offset 这个字段，用来快速定位到最后一 个元素，然后倒着遍历。

entry的结构：

struct entry {
	int<var> prevlen; // 前一个 entry 的字节长度
	int<var> encoding; // 元素类型编码
	optional byte[] content; // 元素内容
}

它的 prevlen 字段表示前一个 entry 的字节长度，当压缩列表倒着遍历时，需要通过这个字段来快速定位到下一个元素的位置。

ziplist 存多少元素?

quicklist 内部默认单个 ziplist 长度为 8k 字节，超出了这个字节数，就会新起一个ziplist。