Redis常用数据类型的底层数据结构
约 910 字大约 3 分钟
2025-09-03
redis7由ziplist替换为listpack的原因
ziplist
ziplist是由连续内存块组成的顺序性数据结构,整个结构有点类似于数组。可以在任意一端进行push/pop操作时间复杂度都是O(1)。
ziplist这个 "数组" 的每一个元素节点(entry),就相当于hash数据类型的value里的一个键值对。
entry里分为三个部分
| previous_entry_length | encoding | content |
|---|---|---|
| 记录前一个节点的长度,占1个字节或5个字节 | content的编码属性(字符串还是整数),以及content的长度。占用1个字节。 | 负责保存节点的数据 |
绝大多数情况下,节点长度都很小。在 ziplist 这种为“小元素”设计的结构中,相邻节点长度小于 254 字节是普遍情况。此时每个 previous_entry_length 字段仅需 1字节,达到了极致的空间节省。
只有遇到极少数 “大节点” 时,才为其后继节点的 previous_entry_length 字段付出 5 字节的代价。这是一种典型的“按需付费”策略。
previous_entry_length字段的用处就是方便反向遍历,遍历时需要知道下一个元素的长度,反向遍历时,previous_entry_length就是下一个元素的长度。
如果在前面插入了一个内容很长的元素a,这个元素a的内容长度超过了254个字节,所以如果要记录元素a的长度则需要5个字节( 1个字节8bit,也就是这个字节能表示的最大数字是
listpack
| encoding | content | length |
|---|---|---|
| content的编码属性(字符串还是整数),以及content的长度。占用1个字节。 | 本元素节点的数据 | 本元素节点的长度 |
| 不再会因为其他元素的变动而影响到本元素节点。 |
length的目的是为了方便反向遍历,当反向遍历到本节点时,只需要拿反向第一个字节(length的值),就能知道这个元素节点的长度是多少,不需要将这个元素完整遍历完,可直接根据长度跳到下一个元素。
总结
| Redis版本 | string | hash | list | set | zset |
|---|---|---|---|---|---|
| Redis6 | SDS | hashtable+ziplist | quicklist+ziplist | insert+ziplist+hasstable | skiplist+ziplist |
| Redis7 | SDS | hashtable+listpack | quicklist+listpack | insert+listpack+hasstable | skiplist+listpack |
当数据量较小时,使用的都是 listpack ,后面数据量上来了,则 hash 会切换为 hashtable ,list 会切换为quicklist ,zset 会切换为 skiplist 。
skiplist
skiplist是一种用空间换时间的策略,是多层级索引(每级索引的构建,都是在上一级索引的基础上,进行跳过一个元素的规则),例如
集合数据:[1、2、3、4、5、6]
则构建索引如下
二级索引:1-->5
一级索引:1-->3-->5
原始联表:1-->2-->3-->4-->5-->6
如果要查询6,则是先到二级索引比较,大于5,则直接到原始表里从5开始往后找。
如果要查询4,则是先到二级索引比较,大于1小于5,则到一级索引比较,大于3,则可直接判定4在原始联表的位置为3之后一个。
所以在查询时效率较高,时间复杂度为 O (
