Redis压缩列表

区分一下

3.2之前 Redis中的List有两种编码格式 一个是LINKEDLIST 一个是ZIPLIST 这个ZIPLIST就是压缩列表

3.2之后来了一个QUICKLIST QUICKLIST是ZIPLIST和LINKEDLIST的结合体 也就是说Redis中没有ZIPLIST和LINKEDLIST了 然后在Redis5.0引入了LISTPACK用来替换QUiCKLIST中的ZIPLIST在REDIS7.0后完全取代了ZIPLIST

我们有说到压缩列表是List的底层数据结构，压缩列表主要用做为底层数据结构提供紧凑型的数据存储方式，能节约内存（节省链表指针的开销），小数据量的时候遍历访问性能好（连续+缓存命中率友好）。数据量少的时候会用它 

什么情况是数据量小的呢

1.列表对象保存的所有字符串对象长度都小于64字节；

2.列表对象元素个数少于512个，注意，这是LIST的限制，而不是ZIPLIST的限制；

满足以上两点 就会用ZIPLIST编码

ZIPLIST结构

zlbytes:表示该ZIPLIST一共占了多少字节数，这个数字是包含zlbytes本身占据的字节的。(夺大!)

zltail：ZIPLIST 尾巴节点相对于ZIPLIST的开头（起始指针）偏移的字节数。通过这个字段可以快速定位到尾部节点，例如现在有一个ZIPLIST，zl指向它的开头，如果要获取tail尾巴节点，即ZIPLIST里的最后一个节点，可以zl + zltail的值，这样定位到它。如果没有尾节点，就定位到 zlend

zllen:表示有多少个数据节点，在本例中就有3个节点。

entry1~entry3：表示压缩列表数据节点。

zlend：一个特殊的entry节点，表示ZIPLIST的结束。

ZIPLIST节点结构

就是上面的entry1 entry2....

他里面有三个字段

prevlen：表示上一个节点的数据长度。

encoding：编码类型。编码类型里还包含了一个entry的长度信息，可用于正向遍历

entry-data：实际的数据。

prevlen:

通过这个字段可以定位上一个节点的起始地址（或者说开头)也就是就是p-prevlen 可以跳到前一个节点的开头位置，实现从后往前操作，所以压缩列表才可以从后往前遍历。如果前一节点的长度，也就是前一个ENTRY的大小，小于254字节，那么prevlen属性需要用1字节长的空间来保存这个长度值，255是特殊字符，被zlend使用了如果前一节点的长度大于等于254字节，那么prevlen属性需要用5字节长的空间来保存这个长度值，注意5个字节中中第一个字节为11111110,也就是254,标志这是个5字节的prelen信息，剩下4字节来表示大小。(这也差太多了 看人家MYSQL里面的可变长度列 少了就1字节 长了就2字节)

encoding:

00pppppp  1字节 String类型，且字符串长度小于2へ6，即小于等于63

 01pppppplqqqqqqqq  2字节 String类型，长度小于2^14次方，即小于等于16383

10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt 5字节 String类型，长度小于2へ32次方

110000001 2个字节的 int16类型

110100001 4个字节的 int32类型

11111110     1个字节的 int64类型

费老劲了 别背 就记住前几位是标识类型 后几位标识长度 对于int类型只标识类型 长度不用标

ZIPLIST性能

查询数据总量

由于ZIPLIST的header定义了记录节点数量的字段zllen,所以通常是可以在O(1)时间复杂度直接返回的,但是呢 zllen是两个字节的 也就是说最多也就能存65534的长度 大于了就存不下了 就得遍历了

遍历去吧 大于65534的节点数 累死 所以他只是应用节点数少的时候

查询指定节点

在ZIPLIST中查询指定数据的节点，需要遍历这个压缩列表，平均时间复杂度是O（N)。

更新数据

ZIPLIST的更新就是增加、删除数据，ZIPLIST提供头尾增减的能力，但是操作平均时间复杂度是O（N），因为在头部增加一个节点会导致后面节点都往后移动，所以更新的平均时间复杂度，可以看作O（N)。其中要注意的是更新操作可能带来连锁更新。注意上面所说的增加节点导致后移，不是连锁更新。连锁更新是指这个后移，发生了不止一次，而是多次。比如增加一个头部新节点，后面依赖它的节点，需要prevlen字段记录它的大小，原本只用1字节记录，因为更新可能膨胀为5字节，然后这个entry的大小就也膨胀了。所以，当这个新数据插入导致的后移完成之后，还需要逐步迭代更新。这种现象就是连锁更新，时间复杂度是O（Nへ2），6.2已经优化为O（N），不用太过担心连锁更新的情况，实际的业务中，很少会刚好遇到需要迭代更新超过2个节点的情况，所以ZIPLIST更新平均时间复杂度，还是可以看作O（N)。不过，ZIPLIST最大的问题还是连锁更新导致性能不稳定。

LISTPACK优化

优化了连锁更新

LISTPACK是为了解决ZIPLIST最大的痛点——连锁更新，我们先来看，ZIPLIST的问题本源。我们知道，ZIPLIST需要支持LIST，LIST是一种双端访问结构，所以需要能从后往前遍历，上面有讲，ZIPLIST的数据节点的结构是这样的：

<prevlen> <encoding> <entry-data>

其中，prevlen就表示上一个节点的数据长度，通过这个字段可以定位上一个节点的数据，可以说，连锁更新问题，就是因为prevlen导致的。

所以我们需要一种不记录prevlen，并且还能找到上一个节点的起始位置的办法，Redis使用了很巧妙的一种方式。我们直接看LISTPACK的节点定义：

1 <encoding-type><element-data><element-tot-len>

encoding-type是编码类型

element-data是数据内容

element-tot-len存储整个节点除它自身之外的长度。

element-tot-len 所占用的每个字节的第一个bit用于标识是否结束。0是结束，1是继续，剩下7个bit来存储数据大小。当我们需要找到当前元素的上一个元素时，我们可以从后向前依次查找每个字节，找到上一个Entry的element-tot-len 字段的结束标识，就可以算出上一个节点的首位置了。举个例子：如果上个节点的element-tot-len为00000001 10000100,每个字节第一个bit标志是否结束，所以这里的element-tot-len一共就两个字节，大小为00000010000100,即132字节。

一些QS

1.ZIPLIST有什么优点

首先肯定是相对于LINKEDLIST

1.节约内存，内存利用率高 2.方便一次性分配 3.遍历时局部性更强

2.ZIPLIST是怎么压缩数据的？

就是看它的结构

然后entry的结构是

他里面的这个entry是紧密相连的 

 3.ZIPLIST下List可以从后往前和从前往后遍历吗

可以 它是双端队列结构 从结构分析 它里面有个encoding结构 包含了长度信息 实现了正向遍历

prelen上一个节点的长度 实现了反向遍历

4.压缩列表插入的时间复杂度是多少？

头部插入是O(N)  他要把后面的数据往后挤  尾部插入O(1)

5.连锁更新的原因如何解决

就跟多米诺骨牌似的 如果上一个节点小于254字节 那下一个节点的prevlen是1长度 要是正好处于这个阈值 更新到了255 那下一个节点就得提升4个字节 那下一个节点也可能提升 balabla

解决就是别保存上一个节点长度 LISTPACK记录的当前节点的长度