华为架构师整理Redis数据结构的大厂最佳实践( 三 ) _Redis

文章插图

记录前一个相邻的Entry的长度，便于双向遍历，类似linkedlist的prev指针。
ziplist是连续存储，指针由偏移量来承载。
Redis中实现了2种方式实现：

当前邻 Entry的长度小于254 时，使用1字节实现
否则使用5个字节

当前一个Entry长度变化时，可能导致后续的所有空间移动，虽然这种情况发生可能性较小。

Entry内容本身是自描述的，意味着第二部分（Entry内容）包含了几个信息：Entry内容类型、长度和内容本身。而内容本身包含：类型长度部分和内容本身部分。类型和长度同样采用变长编码：

00xxxxxx ：string类型；长度小于64，0~63可由6位bit 表示，即xxxxxx表示长度
01xxxxxx|yyyyyyyy ： string类型；长度范围是[64, 16383]，可由14位 bit 表示，即xxxxxxyyyyyyyy这14位表示长度。
10xxxxxx|yy…y(32个y) : string类型，长度大于16383.
1111xxxx ：integer类型，integer本身内容存储在xxxx 中，只能是1~13之间取值。也就是说内容类型已经包含了内容本身。
11xxxxxx ：其余的情况，Redis用1个字节的类型长度表示了integer的其他几种情况，如：int_32、int_24等。
由此可见，ziplist 的元素结构采用的是可变长的压缩方法，针对于较小的整数/字符串的压缩效果较好
LPUSH命令
在头部加入一个新元素
RPUSH命令
在尾部加入一个新元素

当在一个空的K执行这些操作时，会创建一个新列表。当一个操作清空了一个list时，该list对应的key会被删除。若使用一个不存在的K，就会使用一个空list 。

LPUSH mylist a# 现在list是 "a"LPUSH mylist b# 现在list是"b","a"RPUSH mylist c# 现在list是 "b","a","c" (注意这次使用的是 RPUSH)

list的最大长度是2^32 – 1个元素（4294967295，一个list中可以有多达40多亿个元素）。
从时间复杂度的角度来看，Redis list类型的最大特性是：即使是在list的头端或者尾端做百万次的插入和删除操作，也能保持稳定的很少的时间消耗。在list的两端访问元素是非常快的，但是如果要访问一个很大的list中的中间部分的元素就会比较慢了，时间复杂度是O(N)
适用场景

社交中使用List进行时间表建模，使用 LPUSH 在用户时间线中加入新元素，然后使用 LRANGE 获得最近加入元素
可以把[LPUSH] 和[LTRIM] 命令结合使用来实现定长的列表，列表中只保存最近的N个元素
做MQ，依赖BLPOP这种阻塞命令

Set类似List，但无序且其元素不重复。
向集合中添加多次相同的元素，集合中只存在一个该元素。在实际应用中，这意味着在添加一个元素前不需要先检查元素是否存在。
支持多个服务器端命令来从现有集合开始计算集合，所以执行集合的交集，并集，差集都很快。
set的最大长度是2^32 – 1个元素（一个set中可多达40多亿个元素）。
内存数据结构Set在Redis中以intset 或 hashtable存储：