内容简介:压缩列表是列表键与哈希键的底层实现之一。当一个列表键只包含少量的列表项,并且每个列表项要么就是小整数值,要么就是长度较短的字符串,那么Redis就会使用压缩列表来做列表键的底层实现。压缩列表是为了节约内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多的节点,每个节点可以保存一个字节数组或一个整数值。1、长度小于等于63字节的字节数组
压缩列表是列表键与哈希键的底层实现之一。当一个列表键只包含少量的列表项,并且每个列表项要么就是小整数值,要么就是长度较短的字符串,那么 Redis 就会使用压缩列表来做列表键的底层实现。
压缩列表是为了节约内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多的节点,每个节点可以保存一个字节数组或一个整数值。
压缩表可以包含:
1、长度小于等于63字节的字节数组
2、长度小于16383字节的字节数组
3、长度小于等于4294967295字节的字节数组
4、4位长度的无符号整数
5、1字节长度有符号整数
6、3字节长的有符号整数
7、int16类型的整数
8、int32类型的整数
9、int64类型的整数
每个压缩列表节点都由previous_entry_length、encoding、content三部分组成
说明:previous_entry_length 保存前一节点的长度,如果前一个节点长度小于254节点,那么previous_entry_length属性需要1字节长的空间来保存这个长度值;如果超度254则需要5个字节长的空间来保存这个长度。
连锁更新
由于是连续的内存片段,当在中间插入一个元素时,
e1节点的 previous_entry_length属性仅长1字节,当将new节点设置为前置节点时,由于e1的previous_entry_length 长度为1无法保存new节点的长度,所以需要将长度扩展到5个字节空间,因此需要对列表进行空间重新分配操作。同理,如果引发了对e2、e3.。。。的扩展,这种操作称为连锁更新。
连锁更新在最坏的情况下需要对压缩列表执行n次空间的重分配操作,每次空间重分配的最坏复杂度为O(N),所以连锁更新最坏的的复杂度为O(N 2 )。
-------- end --------
每天学一点,总会有收获。
说明:尊重作者知识产权,文中内容参考《Redis设计与实现》,仅在此做学习与大家分享。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- golang压缩和解压缩zip文件
- bitcoin:压缩公钥与未压缩公钥
- 一句话轻松实现压缩图片和文件压缩
- 基于Node.js实现压缩和解压缩的方法
- 一种 JNI 方法实现图片压缩,压缩率极高
- Java - 调用 echarts 提供的地图压缩方法压缩地图
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。