(5) ziplist

概要：2数据结构（编码 ziplist entry结构、解码）

           3操作：1创建(分配空间，初始化)    2插入(编码，分配，拷贝)   3删除(算长度，拷贝、分配)   4遍历(向前更简单)       4连续更新 

特殊编码的双向链表，不存上下链表节点指针，存上个和当前节点长度，牺牲读写性能，换内存利用率

1、简介

本质是一个字节数组，节约内存，包含多个元素，每个是一个字节数组/整数

zset、hash、list数据少时候用。quicklist就是ziplist + 双向链表。创建哈希键并查看编码：

2、数据存储

2.1 编码

（1）ziplist  字节数组结构

1、zlbytes：字节长度，占4字节，因此最长(2^32)-1字节

2、zltail：尾元素相对于起始地址偏移量，占4字节

3、zllen：元素数目，占2字节；超过(2^16)-1，要遍历整个才能获取

4、entryX：存储元素，字节数组/整数

5、zlend：结尾，占1字节，恒为0xFF

假设char * zl指向首地址，Redis通过以下宏定义，实现压缩列表各个字段操作存取：

（2）元素编码 结构

1、previous_entry_length：前一元素长度，1）1或5个字节(前一元素长度<254字节时 1，>则5 )第一字节是固定标志0xFE，后4个字节才真正表示长度；2）假设当前元素首地址为p，那么（p-previous_entry_length）就是前一元素首地址，实现从尾到头遍历

2、encoding：当前元素编码，content字段数据类型（整数/字节数组），长度可变，节约内存

3、content：数据内容

2.2 解码  结构体entry

对于压缩列表元素，获取前一元素长度，判断数据类型，获取数据内容，经过复杂解码运算才行，解码结果应该被缓存，为此定义zlentry，表示解码后压缩列表元素：

zipEntry：解码压缩列表元素，存于zlentry结构体

2.3解码过程

1) 解码previous_entry_length，入参ptr指向元素首地址

2) 解码encoding字段，ptr指向previous_entry_length位置

根据ptr[0]前2个比特即可判类型，判断整数类型要ptr[0]前4个比特

三、基本操作

1、创建

1）分配初始存储空间（11=4+4+2+1个字节），2）初始化zlbytes、zltail、zllen和zlend字段

2、插入

1）编码为压缩列表的元素，2）重新分配空间，3）拷贝数据

zl 首地址，p 插入位置，s数据内容，slen数据长度，返回首地址

(1)编码：1）计算previous_entry_length、encoding和content字段内容。根据插入位置，获取前一长度：

        P0时，前空，即前一为0；  P1时，获取长度previous_entry_length；  P2时，entryN是尾元素，将其三个字段长度相加：

2）encoding：当前元素数据类型以及长度，编码先尝试解析为整数，成功则按整数存，失败按字节数组存   ps：整数数值存value，编码存encoding，还要计算整数所占字节数

3）reqlen存当前元素需空间大小：初始赋值content所需空间大小，再加previous_entry_length与encoding字段所需空间大小。

(2) 重新分配空间

大小不一定是“原+新”：插入前，entryX 128字节，entryX+1元素的previous_entry_length占1个字节；添加entryNEW元素，长1024字节，此时previous_entry_length要5字节；新插入位置指针P失效，预先计算好指针P偏移量，分配后再偏移

ziplistResize函数：3个参数，1)curlen插入前长度，2)reqlen插入元素长度，3)nextdiff 是entryX+1元素长度变化，0、4和-4。

-4时：需空间减少，重新分配空间小于zl指向空间，可能会导致数据丢失。避免发生，重新赋值nextdiff等于0，同时用forcelarge标记这种情况

nextdiff -4时，reqlen会小于4吗？连锁更新可能会

(3) 数据拷贝

  分配空间后，新元素插到位置P。假设entryX+1长度增加4（即nextdiff=4）,1)P后所有元素都要移动，偏移量：entryNew长度，移动数据块长度：P后所有元素长度+nextdiff，2)更新entryX+1元素previous_entry_length字段

 ps思考：第一次更新尾元素偏移量后，为什么不指向尾元素？

    entryX+1元素不知尾元素，且entryX+1长度改变，尾元素偏移量要加上nextdiff

3、删除元素

zl首地址，*p待删除元素首地址，返回首地址。

简单调用底层__ziplistDelete，可同时删除多个，p指向首个删除首地址，num待删除元素数

步骤：1）计算待删除元素总长度，2）数据拷贝，3）重新分配空间

1

(2) 数据拷贝

first与p间都是待删除，1）p指向zlend，不需拷贝，更新尾节点偏移量

2）p不指向zlend（所需空间减少，减少量！=删除长度），尾元素偏移量加上nextdiff

    例：删除后，entryX称为entryN前一元素，entryX长512字节，因此previous_entry_length需5字节

(3) 重新分配空间，同插入，但不会丢失数据

4、遍历压缩列表

  前/后向遍历，zl列表首地址，p访问元素首地址；ziplistNext返回后一元素首地址，ziplistPrev返回前一元素首地址

previous_entry_length存前长度，因此前向遍历简单，表达式(p-previous_entry_length)获取前一元素首地址。后向遍历，解码、计算当前元素，才能获取后一元素首地址

四、连锁更新

删除zl1位置P1的entryX，或zl2位置P2插入entryY，出现什么情况？

压缩列表zl1，previous_entry_length要5字节，entryX+1扩展至257字节；由于entryX+1长度增加，entryX+2的previous_entry_length同样改变。以此类推，每次扩展都重新分配内存，效率低

ps：添加/删除操作最坏O(N2)，连锁更新出现概率不高，一般O(N) 

https://segmentfault.com/a/1190000017328042