Sortedset底层存储结构
sortedset同时会由两种数据结构支持,ziplist和skiplist.
只有同时满足如下条件是,使用的是ziplist,其他时候则是使用skiplist
- 有序集合保存的元素数量小于128个
- 有序集合保存的所有元素的长度小于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)
