图解 Redis 数据结构篇之压缩列表，java 注解原理解析

如上图，展示了一个总长为 80 字节，包含 3 个节点的压缩列表。如果我们有一个指向压缩列表起始地址的指针 p，那么表为节点的地址就是 P+60。

2.2 Redis 压缩列表节点的构成[#](

)

每个压缩列表节点可以保存一个字节数组或者一个整数值。其中，字节数组可以是以下三种长度中的一种。

• 长度小于等于 63(2^6-1)字节的字节数组;

• 长度小于等于 16383(2^14-1)字节的字节数组

• 长度小于等于 4294967295(2^32-1)字节的字节数组

整数值可以是以下 6 种长度中的一种

• 4 位长,介于 0 至 12 之间的无符号整数

• 1 字节长的有符号整数

• 3 字节长的有符号整数

• int16_t 类型整数

• int32_t 类型整数

• int64_t 类型整数

节点的 previous_entry_length 属性以字节为单位,记录了压缩列表中前一个节点的长度。 previous_entry_length 属性的长度可以是 1 字节或者 5 字节。

• 如果前一节点的长度小于 254 字节,那么 previous_entry_length 属性的长度为 1 字节，前一节点的长度就保存在这一个字节里面。

• 如果前一节点的长度大于等于 254 字节,那么 previous_entry_length 属性的长度为 5 字节:其中属性的第一字节会被设置为 0xFE(十进制值 254),而之后的四个字节则用于保存前一节点的长度.

节点的 encoding 属性记录了节点的 content 属性所保存数据的类型以及长度。

• 一字节、两字节或者五字节长,值的最高位为 00、01 或者 10 的是字节数组编码这种编码表示节点的 content 属性保存着字节数组,数组的长度由编码除去最高两位之后的其他位记录。

• 一字节长,值的最高位以 11 开头的是整数编码:这种编码表示节点的 content 属性保存着整数值,整数值的类型和长度由编码除去最高两位之后的其他位记录。

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

• 编码的最高两位 00 表示节点保存的是一个字节数组。

• 编码的后六位 001011 记录了字节数组的长度 11。

• content 属性保存着节点的值"hello world"。

• 编码 11000000 表示节点保存的是一个 int16_t 类型的整数值;

• content 属性保存着节点的值 10086

2.3 常用操作的时间复杂度[#](

)

|

【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开：qq.cn.hn/FTf 免费领取

操作 | 时间复杂度 |

| --- | --- |

| 创建一个新的压缩列表 | O(1) |

| 创建一个包含给定值的新节点,并将这个新节点添加到压缩列表的表头或者表尾 | 平均 O(N)，最坏 O(N^2)(可能发生连锁更新) |

| 将包含给定值的新节点插人到给定节点之后 | 平均 O(N)，最坏 O(N^2)(可能发生连锁更新) |

| 返回压缩列表给定索引上的节点 | O(N) |

| 在压缩列表中査找并返回包含了给定值的节点 | 因为节点的值可能是一个字节数组,所以检查节点值和给定值是否相同的复杂度为 O(N),而查找整个列表的复杂度则为(N^2) |

| 返回给定节点的下一个节点 | O(1) |

| 返回给定节点的前一个节点 | O(1) |

| 获取给定节点所保存的值 | O(1) |

| 从压缩列表中删除给定的节点 | 平均 O(N)，最坏 O(N^2)(可能发生连锁更新) |

| 删除压缩列表在给定索引上的连续多个 | 平均 O(N)，最坏 O(N^2)(可能发生连锁更新) |

| 返回压缩列表目前占用的内存字节数 | O(1) |

| 返回压缩列表目前包含的节点数量 | 点数量小于 65535 时为 O(1),大于 65535 时为 O(N) |

本文重点[#](

)

• 压缩列表是 Redis 为节约内存自己设计的一种顺序型数据结构。

• 压缩列表被用作列表键和哈希键的底层实现之一。

• 压缩列表可以包含多个节点,每个节点可以保存一个字节数组或者整数值。

• 添加新节点到压缩列表,或者从压缩列表中删除节点,可能会引发连锁更新操作,但这种操作出现的几率并不高。

参考[#](

)