javaee论坛

普通会员

225648

帖子

343

回复

357

积分

楼主
发表于 2019-11-08 13:35:33 | 查看: 71 | 回复: 3

列表键底层实现之一:当一个列表键只包含少量列表项,且每个列表项要么是小整数值,要么是长度比较短的字符串时,就使用压缩列表

哈希键底层实现之一:当一个哈希键只包含少量键值对,且每个键值对的键、值要么是小整数值,要么是长度比较短的字符串时,就使用压缩列表

目的:节约内存

使用OBJECTENCODING键可查看所用的底层数据结构

6.1压缩列表的构成

由一系列特殊编码的连续内存块组成的顺序型数据结构;一个压缩列表可以包含任意多个节点,每个节点可以保存一个字节数组或一个整数值

组成部分及各个组成部分的类型、长度、用途例子:

6.2压缩列表节点的构成

每个压缩列表节点可以保存一个字节数组或一个整数值其中字节数组可以是以下三种长度的一种:而整数值则可以是以下六种长度中的其中一种:每个节点都由previous_entry_length、encoding、content三个部分组成下面逐一介绍

6.2.1previous_entry_length

以字节为单位,记录了其前一个节点的长度,可以是1字节或5字节,选择如下:

作用:程序可以通过指针运算,根据当前节点的起始地址来计算出前一个节点的起始地址即当前节点起始地址的指针p1减掉当前节点previous_entry_length的值,就能得到指向前一个节点的起始地址的指针p2实现了压缩列表的从表尾向表头遍历的操作,即拥有表尾节点起始地址指针,逐个减previous_entry_length即可:6.2.2content

保存节点的值,可以是一个字节数组或整数,值的类型和长度由节点encoding属性决定

保存字节数组的例子:

保存整数值的例子:

6.2.3encoding

记录了节点content属性所保存数据的类型以及长度,使用不同长度和最高位来区分所有可用的字节数组编码:所有可用的整数编码:

6.3连锁更新

新增节点时:如果当前节点e1、e2…eN的长度介于250字节到253节点,插入new位254节点到表头,则程序需要对压缩列表执行空间重分配操作,且e1的previous_entry_length属性要扩展为5字节,e1长度变为介于254字节到257字节,则e2也要进行这样的操作,直到所有节点都完成删除节点时:如下图,假设big大于等于254字节,small小于254字节,则删除small后,e1的previous_entry_length属性需要扩展为5字节,并引发后续操作复杂度分析:但是因为出现率低,且出现时,只要被更新的节点数量不多,不像我们假设的全部都要更新,那么对性能影响问题不大

因此,ziplistPush等命令的平均复杂度仅为O(N),即遍历找到位置后插入,可以放心使用


普通会员

1

帖子

305

回复

312

积分
沙发
发表于 2019-11-19 01:03:32

如果这就是爱,再转身的时候就该留下

普通会员

0

帖子

295

回复

308

积分
板凳
发表于 2023-09-08 22:03:40

好好好

普通会员

0

帖子

348

回复

356

积分
地板
发表于 2024-02-26 08:19:54

很好

您需要登录后才可以回帖 登录 | 立即注册

触屏版| 电脑版

技术支持 历史网 V2.0 © 2016-2017