Redis-Sorted-Set底层数据结构
⾯试被问到了SortedSet(ZSet)的底层数据结构..只记得是跳表.然⽽并不了解底层实现.
所以本⽂是对于SortedSet的学习记录
Sortedset底层存储结构
sortedset同时会由两种数据结构⽀持,ziplist和skiplist.
只有同时满⾜如下条件是，使⽤的是ziplist，其他时候则是使⽤skiplist
有序集合保存的元素数量⼩于128个
redis八种数据结构
有序集合保存的所有元素的长度⼩于64字节
当ziplist作为存储结构时候，每个集合元素使⽤两个紧挨在⼀起的压缩列表结点来保存，第⼀个节点保存元素的成员，第⼆个元素保存元素的分值.
当使⽤skiplist作为存储结构时，使⽤skiplist按序保存元素分值，使⽤dict来保存元素和分值的对应关系
参考资料
跳跃表(skiplist)
跳跃表是⼀种基于有序链表的扩展，简称跳表.跳表会维护多个索引链表和原链表.
不断得提升新的关键节点形成新的有序链表，通过空间换时间.
对有序链表进⾏关键点的提升，作为插⼊对⽐的索引
提取关键点
插⼊逻辑
链表插⼊新的元素，只需对⽐新元素的值和关键点链表，这样就能将对⽐次数缩减.
插⼊逻辑
关键节点提取逻辑
因为在跳表中，使⽤空间换时间，会有多层的索引链表，每⼀层索引链表都是上⼀层的⼀半，当数据量较⼤的时候，就能够很轻松的降低链表查询消耗的性能.
⾄于提取的极限，是同⼀层只有两个节点
⼀个节点是没有⽐较意义的
这样的多层链表结构，就是所谓的跳跃表
提取新的索引节点
跳表采⽤抛硬币的做法，在插⼊之后会随机判断新插⼊的元素是否称为新的关键点
跳表插⼊节点的流程
1.新节点和各层索引节点逐⼀⽐较，确定原链表的插⼊位置O(logN)
2.把索引插⼊到原链表,O(1)
3.利⽤抛硬币的随机⽅式，决定新界店是否提升为上⼀级索引.O(logN)
总体上跳表插⼊的时间复杂度是O(logN)，空间复杂度是O(N)
节点删除的流程
1.在索引层到响应节点进⾏删除，删除每⼀层的相同节点O(logN)
3.如果某⼀层在删除节点后只剩下⼀个节点，那么这个链表就可以删除了.O(logN)
跳表删除的时间复杂度是O(logN)
SortedSet使⽤场景

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