压缩列表

2018-01-31 10:57:52来源:网络收集作者:程序诗人人点击

分享

当列表键还有少量项 ,或者是小整数类型,或者短字符串  Redis采用压缩列表做底层实现


还有哈希键的底层实现


目的:节约内存


定义:由一系列连续编码的内存块组成的顺序型数据结构。


结构:


压缩列表


zlbytes 4字节  记录整个压缩列表占用的内存字节数  用途内存重分配或者zlen位置时使用过


zltail   4字节  记录尾节点位置  偏移量


zllen  2字节 记录节点数量   当属性值超过两个字节时需要遍历方可计算


entryX 不定  包含的各个节点


zlend 1字节 特殊值0XFF 用于标记压缩列表末端

压缩列表节点


保存字节数组或者一个整数


字节数组3中长度分别为  2^6   14 32 -1 


整数值有6中  4  1 3  4 8 16 

关于组成部分   3部分


previous_entry_length        前一节点长度  字节单位   1或者5   OXFE 作为5字节前缀  作用可通过指针运算计算前一节点的起始位置  这也是压缩列表从表尾部向头部遍历的原理


encoding  记录了content保存的类型和长度  1 2 5 字节长前缀一般表示类型   数组的长度是编码除去最高两位之后的其他位记录    关于具体数组编码可深入查阅了解


 content保存节点值   类型和长度 encoding决定

连锁更新    特殊情况的连续空间扩展     当在1字节保存的节点前新增一个5字节的节点  发生的连锁反应   还有删除操作也会


更新复杂度最差n2    但是造成的性能问题很低


实际需要的触发条件  多个连续的长度介于250 -253之间字节节点才会引发


因此ziplistPush命令平均复杂度On

压缩列表的API   就是前缀为ziplist的一系列的api


NEW   PUSH DELETE   INSERT INDEX   FIND  NEXT  PREW  GET DELETERANGE  BLOBLEAN  LEN


参考书籍


《redis设计与实现》


最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台