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，也就是这个字节能表示的最大数字是 $2^8$ = 256），如果元素a后面的元素b的previous_entry_length默认是1个字节，无法存储元素a的长度，这就需要往后扩充空间。元素b后面的元素c、d等等也需要一同扩充。效率很低 。

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 ( ${\log }_{}n$ ) ，空间复杂度为 O( n ) 。适合读多写少的场景。