Redis系列-14.Redis经典五大类型源码及底层实现（二）（上）:https://developer.aliyun.com/article/1414747
quicklistNode结构
quicklistNode中的*zl指向一个ziplist，一个ziplist可以存放多个元素
Redis7
listpack紧凑列表
是用来替代 ziplist 的新数据结构，在 7.0 版本已经没有 ziplist 的配置了（6.0版本仅部分数据类型作为过渡阶段在使用）
源码实现
本图最下方有lpush命令执行后直接调用pushGenericCommand命令
看看redis6的相同文件t_list.c
实现：object.c
Redis7的List的一种编码格式，list用quicklist存储，quicklist存储了一个双向链表，每个节点都是一个listpack
quicklist是listpack和linkedlist的结合体
Set数据结构介绍
Redis用intset或hashtable存储set。如果元素都是整数类型，就用intset存储。
如果不是整数类型，就用hashtable（数组+链表的存来储结构）。key就是元素的值，value为null。
Set的两种编码格式
intset
hashtable
源码分析
ZSet数据结构介绍
Redis6
当有序集合中包含的元素数量超过服务器属性 server.zset_max_ziplist_entries 的值（默认值为 128 ），或者有序集合中新添加元素的 member 的长度大于服务器属性 server.zset_max_ziplist_value 的值（默认值为 64 ）时，redis会使用跳跃表作为有序集合的底层实现。
否则会使用ziplist作为有序集合的底层实现
Redis7
ZSet的两种编码格式
redis6：ziplist + skiplist
redis7：listpack + skiplist
源码分析
Redis6
Redis7
skiplist
为什么引出跳表
先从一个单链表来讲
对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。
这样查找效率就会很低，时间复杂度会很高O(N)
但是存在痛点：
解决方法：升维，也叫空间换时间。
优化
从这个例子里，我们看出，加来一层索引之后，查找一个结点需要遍历的结点个数减少了，也就是说查找效率提高了。
优化二
画一个包含64个节点的链表，按照前面讲的这种思路，建立五级索引
是什么？
skiplist是一种以空间换取时间的结构。
由于链表，无法进行二分查找，因此借鉴数据库索引的思想，提取出链表中关键节点（索引），先在关键节点上查找，再进入下层链表查找，提取多层关键节点，就形成了跳跃表
but
由于索引也要占据一定空间的，所以，索引添加的越多，空间占用的越多
总体来讲 跳表 = 链表 + 多级索引
跳表时间 + 空间复杂度介绍
时间复杂度
跳表查询的时间复杂度分析，如果链表里有N个结点，会有多少级索引呢？
按照我们前面讲的，两两取首。每两个结点会抽出一个结点作为上一级索引的结点，以此估算：
第一级索引的结点个数大约就是n/2，
第二级索引的结点个数大约就是n/4，
第三级索引的结点个数大约就是n/8，依次类推…
也就是说，第k级索引的结点个数是第k-1级索引的结点个数的1/2，那第k级索引结点的个数就是n/(2^k)
空间复杂度
跳表查询的空间复杂度分析
比起单纯的单链表，跳表需要存储多级索引，肯定要消耗更多的存储空间。那到底需要消耗多少额外的存储空间呢？
我们来分析一下跳表的空间复杂度。
第一步：首先原始链表长度为n，
第二步：两两取首，每层索引的结点数：n/2, n/4, n/8 … , 8, 4, 2 每上升一级就减少一半，直到剩下2个结点,以此类推；如果我们把每层索引的结点数写出来，就是一个等比数列。
这几级索引的结点总和就是n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空间复杂度是O(n) 。也就是说，如果将包含n个结点的单链表构造成跳表，我们需要额外再用接近n个结点的存储空间。
第三步：思考三三取首，每层索引的结点数：n/3, n/9, n/27 … , 9, 3, 1 以此类推；
第一级索引需要大约n/3个结点，第二级索引需要大约n/9个结点。每往上一级，索引结点个数都除以3。为了方便计算，我们假设最高一级的索引结点个数是1。我们把每级索引的结点个数都写下来，也是一个等比数列
通过等比数列求和公式，总的索引结点大约就是n/3+n/9+n/27+…+9+3+1=n/2。尽管空间复杂度还是O(n) ，但比上面的每两个结点抽一个结点的索引构建方法，要减少了一半的索引结点存储空间。
所以空间复杂度是O(n)；
优缺点
优点：
跳表是一个最典型的空间换时间解决方案，而且只有在数据量较大的情况下才能体现出来优势。而且应该是读多写少的情况下才能使用，所以它的适用范围应该还是比较有限的
缺点：
维护成本相对要高，在单链表中，一旦定位好要插入的位置，插入结点的时间复杂度是很低的，就是O(1)
but
新增或者删除时需要把所有索引都更新一遍，为了保证原始链表中数据的有序性，我们需要先找到要动作的位置，这个查找操作就会比较耗时最后在新增和删除的过程中的更新，时间复杂度也是O(log n)
