【Redis】压缩列表

Metadata

title: 【Redis】 压缩列表
date: 2023-07-09 08:34
tags:
  - 行动阶段/完成
  - 主题场景/数据存储
  - 笔记空间/KnowladgeSpace/ProgramSpace/BasicsSpace
  - 细化主题/数据存储/Redis
categories:
  - 数据存储
keywords:
  - 数据存储/Redis
description: 【Redis】 压缩列表

概述

压缩列表是列表键和哈希键底层实现之一。当一个列表键只包含少量列表项，且每个列表项要么是小整数，要么是长度比较短的字符串，Redis 就使用压缩列表来做列表键的底层实现。

list

entry

压缩列表是一种为节约内存而开发的顺序型数据结构。
压缩列表被用作列表键和哈希键的底层实现之一。
压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。
添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的几率并不高。

压缩列表的构成

为节约内存而开发的，由一系列特殊编码的连续内存块组成的顺序型数据结构。

结构比较简单，属性如下：

zlbytes：记录整个压缩列表占用内存字节数，进行内存重分配或计算 zlend 时使用。
zltail：记录压缩列表尾节点距离压缩列表起始地址多少字节。
zllen：节点数量。小于 65535 时，表示节点数量；大于时，需要遍历才能计算得出。
entryx：列表节点。
zlend：特殊值 0xFF 用于标记压缩列表的末端。

压缩列表节点的组成

每个压缩列表节点可以是一个字节数组，也可以是一个整数。由previous_entry_length，encoding，content组成。

previous_entry_length

单位是字节，记录压缩列表前一个节点的长度。该属性长度为 1 字节或 5 字节，前两位表示该属性长度为 2 位还是 10 位。

前一个节点的长度 < 254 字节时，该属性只有 2 位，且前一节点的长度就保存在这两位。如 0x05，表示前一个字节长度为 5 字节。
前一个节点的长度 >=254 字节时，该属性有 10 位，且前两位表示这是一个 5 字节的长度，后 8 位表示前一个节点的长度。如 0xFE0000，表示前一个字节长度为 0x00002766，换算为 10 进制就是我们熟悉的数字。

encoding

encoding 记录了节点的 content 属性所保存数据类型和长度。高两位表示存储的是字节数组还是整数。

content

存储节点的值。

连锁更新

当多个连续的长度介于 250 字节到 253 字节之间的节点，插入新的头节点（长度大于等于 245 字节），后面节点的 previous_entry_length 就要新增 4 字节的空间（1 字节变成 5 字节），需要进行内存重分配，由于前一个节点的变更，每个节点的 previous_entry_length 属性也需要记录之前的长度而发生相应的变更，所以会出现连锁更新。除了新增节点，删除节点也可能会遇到这种情况。

因为连锁更新在最坏情况下需要对压缩列表执行 N 次空间重分配操作，每次重分配的的最坏时间复杂度为 $O(N)$ ，所以连锁更新的最坏时间复杂度为 $O(N^2)$

虽然代价很高，但是出现的几率比较低，而且只要更新节点的数量不多，就不会对性能产生影响。因此 ziplistPush 命令的平均复杂度为 $O(N)$ 。

压缩列表的时间复杂度

操作时间复杂度
将新节点插入	“平均O(N),最坏O(N2)”
返回给定索引节点	O(N)
查找并返回合定值的节点	“如果是字节数组和整数,检查节点的复杂度为0(N),查找列表的复杂度为O(N2)”
删除给定节点	“平均O(N),最坏O(N2)”
返回节点数量	“节点数小于65535时为O(1),大于65535时为O(N)”

压缩列表API

函数	作用	算法复杂度
ziplistNew	创建一个新的压缩列表	O(1)
ziplistPush	“创建一个包含给定值的新节点,并将这个新节点添加到压缩列表的表头或者表尾”	“平均0(N),最坏0(N)”
ziplistInsert	将包含给定值的新节点插人到给定节点之后	“平均O(N),最坏O(v)”
ziplistIndex	返回压缩列表给定索引上的节点	O(N)
ziplistFind	在压缩列表中查找并返回包含了给定值的节点	“因为节点的值可能是一个字节数组, 所以检查节点值和给定值是否相同的复杂度为O(N,而查找整个列表的复杂度则为0(N)”
ziplistNext	返回给定节点的下一个节点	O(1)
ziplistPrev	返回给定节点的前一个节点	O(1)
ziplistGet	获取给定节点所保存的值	O(1)
ziplistDelete	从压缩列表中删除给定的节点	“平均O(N),最坏O(N)”
ziplistDeleteRange	删除压缩列表在给定索引上的连续多个节点	“平均O(N),最坏O(v)”
ziplistBlobLen	返回压缩列表目前占用的内存字节数	O(1)
ziplistLen	返回压缩列表目前包含的节点数量	“节点数量小于65535时为0(1),大于 65 535 时为O(N)”