网站推广计划书怎么写,wordpress windows 权限,教育网站建设规划书,大连网页制作美工区分一下
3.2之前 Redis中的List有两种编码格式 一个是LINKEDLIST 一个是ZIPLIST 这个ZIPLIST就是压缩列表
3.2之后来了一个QUICKLIST QUICKLIST是ZIPLIST和LINKEDLIST的结合体 也就是说Redis中没有ZIPLIST和LINKEDLIST了 然后在Redis5.0引入了LISTPACK用来替换QUiCKLIST中的…区分一下
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本身占据的字节的。(夺大!)
zltailZIPLIST 尾巴节点相对于ZIPLIST的开头起始指针偏移的字节数。通过这个字段可以快速定位到尾部节点例如现在有一个ZIPLISTzl指向它的开头如果要获取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中查询指定数据的节点需要遍历这个压缩列表平均时间复杂度是ON)。
更新数据
ZIPLIST的更新就是增加、删除数据ZIPLIST提供头尾增减的能力但是操作平均时间复杂度是ON因为在头部增加一个节点会导致后面节点都往后移动所以更新的平均时间复杂度可以看作ON)。其中要注意的是更新操作可能带来连锁更新。注意上面所说的增加节点导致后移不是连锁更新。连锁更新是指这个后移发生了不止一次而是多次。比如增加一个头部新节点后面依赖它的节点需要prevlen字段记录它的大小原本只用1字节记录因为更新可能膨胀为5字节然后这个entry的大小就也膨胀了。所以当这个新数据插入导致的后移完成之后还需要逐步迭代更新。这种现象就是连锁更新时间复杂度是ONへ26.2已经优化为ON不用太过担心连锁更新的情况实际的业务中很少会刚好遇到需要迭代更新超过2个节点的情况所以ZIPLIST更新平均时间复杂度还是可以看作ON)。不过ZIPLIST最大的问题还是连锁更新导致性能不稳定。 LISTPACK优化
优化了连锁更新
LISTPACK是为了解决ZIPLIST最大的痛点——连锁更新我们先来看ZIPLIST的问题本源。我们知道ZIPLIST需要支持LISTLIST是一种双端访问结构所以需要能从后往前遍历上面有讲ZIPLIST的数据节点的结构是这样的
prevlen encoding entry-data
其中prevlen就表示上一个节点的数据长度通过这个字段可以定位上一个节点的数据可以说连锁更新问题就是因为prevlen导致的。
所以我们需要一种不记录prevlen并且还能找到上一个节点的起始位置的办法Redis使用了很巧妙的一种方式。我们直接看LISTPACK的节点定义
1 encoding-typeelement-dataelement-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记录的当前节点的长度
