Redis之List数据结构底层原理
1：Redis链表实现的特性
双端：链表节点带有 prev 和 next 指针，获取某个节点的前置节点和后置节点复杂度都是O(1)。
⽆环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL，对链表的访问以NULL为终点。
带表头指针和表尾指针：通过list结构的 head 和 tail 指针，程序获取链表的表头节点和表尾结点的复杂度都是O(1)。
带链表长度计数器：程序使⽤ list 结构的 len属性对 list持有的链表节点进⾏计数，程序获取链表中节点数量的复杂度为O(1)。
多态：链表节点使⽤ void* 指针来保存节点值，并且通过 list 结构的 dup、 free、match 三个属性为节点值设置类型特定函数，所以链表可以⽤于保存各种不同类型的值。
2：应⽤场景
lpush+lpop=Stack（栈）
lpush+rpop=Queue（队列）
lpush+ltrim=Capped Collection（有限集合）
lpush+brpop=Message Queue（消息队列）
排⾏榜，数据最新列表等等
集合设置过期，只能给整个集合设置，不能单独给某⼀个元素设置，没有给单独元素设置过期时间的策略
3：存储⽅式
其底层有linkedList、zipList和quickList这三种存储⽅式
1：linkedList
与Java中的LinkedList类似，Redis中的linkedList是⼀个双向链表，也是由⼀个个节点组成的。Redis中借助C语⾔实现的链表节点结构如下所⽰
pre指向前⼀个节点，next指针指向后⼀个节点，value保存着当前节点对应的数据对象。listNode的⽰意图如下所⽰
链表的结构如下：
head指向链表的头节点
tail指向链表的尾节点
dup函数⽤于链表转移复制时对节点value拷贝的⼀个实现，⼀般情况下使⽤等号⾜以，但在某些特殊情况下可能会⽤到节点转移函数，默认可以给这个函数赋值NULL即表⽰使⽤等号进⾏节点转移
free函数⽤于释放⼀个节点所占⽤的内存空间，默认赋值NULL的话，即使⽤Redis⾃带的zfree函数进⾏内存空间释放
match函数是⽤来⽐较两个链表节点的value值是否相等，相等返回1，不等返回0
len表⽰这个链表共有多少个节点，这样就可以在O(1)的时间复杂度内获得链表的长度
链表的结构如下：
2：zipList类型
Redis的zipList结构如下所⽰
zipList的结构如下所⽰
注意到zltail_offset这个参数，有了这个参数就可以快速定位到最后⼀个entry节点的位置，然后开始倒序遍历，也就是说zipList⽀持双向遍历。
3：linkList与zipList的对⽐
1：当列表对象中元素的长度较⼩或者数量较少时，通常采⽤zipList来存储；当列表中元素的长度较⼤或者数量⽐较多的时候，则会转⽽使⽤双向链表linkedList来存储。
①列表对象保存的所有字符串元素的长度都⼩于64字节
②列表元素保存的元素数量⼩于512个
2：双向链表linkedList便于在表的两端进⾏push和pop操作，在插⼊节点上复杂度很低，但是它的内存开销⽐较⼤。⾸先，它在每个节点上除了要保存数据之外，还有额外保存两个指针；其次，双向链表的各个节点都是单独的内存块，地址不连续，容易形成内存碎⽚。
3：zipList存储在⼀块连续的内存上，所以存储效率很⾼。但是它不利于修改操作，插⼊和删除操作需要频繁地申请和释放内存。特别是当zipList长度很长时，⼀次realloc可能会导致⼤量的数据拷贝。
4：为什么有了linkedList还有设计⼀个zipList呢？就像zipList的名字⼀样，它是⼀个压缩列表，是为了节约内存⽽开发的。相⽐于linkedList，其少了pre和next两个指针。在Redis中，pre和next指针就要占⽤16个字节（64位系统的⼀个指针就是8个字节）。
另外，linkedList的每个节点的内存都是单独分配，加剧内存的碎⽚化，影响内存的管理效率。与之相对的是，zipList是由连续的内存组成的，这样⼀来，由于内存是连续的，就减少了许多内存碎⽚和指针的内存占⽤，进⽽节约了内存。
redis八种数据结构
4：quickList
1：起源
在Redis3.2版本之后，list的底层实现⽅式⼜多了⼀种，quickList。qucikList是由zipList和双向链表linkedList组成的混合体。它将linkedList按段切分，每⼀段使⽤zipList来紧凑存储，多个zipList之间使⽤双向指针串接起来。
⽰意图如下所⽰：
2：每个zipList可以存储多少个元素
quickList内部默认单个zipList长度为8k字节，即list-max-ziplist-size的值设置为-2，超出了这个阈值，就会重新⽣成⼀个zipList来存储数据。
根据注释可知，性能最好的时候就是就是list-max-ziplist-size为-1和-2，即分别是4kb和8kb的时候，当然，这个值也可以被设置为正数，当list-max-ziplist-szie为正数n时，表⽰每个quickList节点上的zipList最多包含n个数据项。
4：⼩结
1：linkedList
1：linkedList便于在表的两端进⾏ push 和 pop 操作，但是它的内存开销⽐较⼤
2：linkedList每个节点上除了要保存数据之外，还要额外保存两个指针
3：linkedList的各个节点是单独的内存块，地址不连续，节点多了容易产⽣内存碎⽚
2：ziplist
1：ziplist 由于是⼀整块连续内存，所以存储效率很⾼
2：ziplist 不利于修改操作，每次数据变动都会引发⼀次内存的 realloc
3：当 ziplist 长度很长的时候，⼀次 realloc 可能会导致⼤批量的数据拷贝，进⼀步降低性能
3：quicklist
1：空间效率和时间效率的折中
2：结合了双端链表和压缩列表的优点

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。