rediszset怎么排序_Redis有序集合zset的底层实现
1. 编码
redis五种数据结构zset的编码有ziplist和skiplist两种。
底层分别使⽤ziplist(压缩链表)和skiplist(跳表)实现。
什么时候使⽤ziplist什么时候使⽤skiplist？
当zset满⾜以下两个条件的时候，使⽤ziplist：
保存的元素少于128个 保存的所有元素⼤⼩都⼩于64字节
不满⾜这两个条件则使⽤skiplist。
(注意：这两个数值是可以通过f的zset-max-ziplist-entries 和 zset-max-ziplist-value选项 进⾏修改。)
2. 实现
ziplist编码
关于什么是ziplist(压缩链表)，可以参见这篇⽂章：Redis源码分析-压缩列表ziplist
ziplist 编码的有序集合对象使⽤压缩列表作为底层实现，每个集合元素使⽤两个紧挨在⼀起的压缩列表节点来保存，第⼀个节点保存元素的成员，第⼆个节点保存元素的分值。并且压缩列表内的集合元素按分值从⼩到⼤的顺序进⾏排列，⼩的放置在靠近表头的位置，⼤的放置在靠近表尾的位置。
从⼩到⼤排列
ziplist结构
skiplist编码
skiplist 编码的有序集合对象使⽤ zet 结构作为底层实现，⼀个 zset 结构同时包含⼀个字典和⼀个跳表：
typedef struct zset{    //跳跃表    zskiplist *zsl;    //字典    dict *dice;} zset;
字典的键保存元素的值，字典的值则保存元素的分值；跳跃表节点的 object 属性保存元素的成员，跳跃表节点的 score 属性保存元素的分值。
这两种数据结构会通过指针来共享相同元素的成员和分值，所以不会产⽣重复成员和分值，造成内存的浪费。
说明：其实有序集合单独使⽤字典或跳跃表其中⼀种数据结构都可以实现，但是这⾥使⽤两种数据结构组合起来，原因是假如我们单独使⽤ 字典，虽然能以 O(1) 的时间复杂度查成员的分值，但是因为字典是以⽆序的⽅式来保存集合元素，所以每次进⾏范围操作的时候都要进⾏排序；假如我们单独使⽤跳跃表来实现，虽然能执⾏范围操作，但是查操作有 O(1)的复杂度变为了O(logN)。因此Redis使⽤了两种数据结构来共同实现有序集合。
参考资料：
1. Redis详解(五)------ redis的五⼤数据类型实现原理
2. Redis源码分析-压缩列表ziplist

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