redis有序集合数据结构
介绍：
ZSet数据结构类似于Set结构，只是ZSet结构中，每个元素都会有⼀个分值，然后所有元素按照分值的⼤⼩进⾏排列，相当于是⼀个进⾏了排序的链表。
如果ZSet是⼀个链表，⽽且内部元素是有序的，在进⾏元素插⼊和删除，以及查询的时候，就必须要遍历链表才⾏，时间复杂度就达到了O(n)，这个在以单线程处理的Redis中是不能接受的。所以ZSet采⽤了⼀种跳跃表的实现。这个实现有点类似于Kafka存储消息是使⽤的稀疏索引，kafka这个相对较简单，可以⽤来介绍类⽐学习。
如果熟悉Kafka，就知道Kafka在进⾏持久化的时候，⽣成了两个⽂件，⼀个是xxxxxxx.log，⼀个是xxxxxxx.index，这其中log⽂件中以链表的形式保存着消息的详细信息，⽽index⽂件中，则是保存着这些消息的索引，或者说偏移量，但⼜不是每⼀条消息的索引都在index⽂件中存在，⽽是稀疏的，⽐如log⽂件中的消息的索引从0-10000，那么index⽂件中存储的索引可能是100， 500， 700， 1000，5000， 6500，每⼀个索引中都保存着对应的log⽂件中的消息的具体位置，如图：
当要访问偏移量为899的这条消息时，先去index⽂件中查，到了700和1000这个区间，根据700这个索引中的信息，到log⽂件中700这条消息的具体位置，然后顺序往下查，直到到索引为899的这条消息为⽌。从这个实现中我们可以看到，Kafka并没有进⾏log ⽂件的整个遍历，⽽是通过index中的稀疏索引，到消息在log中的⼤概位置，然后顺序遍历到消息，这样就⼤⼤提⾼了查的效率，如图：
Redis的跳跃表和上⾯类似，只是更加复杂⼀些，Kafka的稀疏索引只有⼀层，⽽Redis的索引被提取为多层。如图：
所有的元素都会在L0层的链表中，根据分数进⾏排序，同时会有⼀部分节点有机会被抽取到L1层中，作为⼀个稀疏索引，同样L1层中的索引也有⼀定机会被抽取到L2层中，组成⼀个更稀疏的索引列表。
下⾯⽤图来演⽰⼀下在对快速链表进⾏插⼊、删除、查询时，是如何定位到L0层中的具体位置的。
⾸先，假定有这么⼀个链表，注意这⾥只展⽰分数，⽽不展⽰具体的值了：
如果要查分数为66的元素，⾸先在L2层的索引。很明显，66位于25和85中间，这时就缩⼩了查区间：
然后根据获得的区间，去L1对应的区间中查，得到⼀个更精确的区间：
最终，根据这个更精确的区间，去L0层顺序遍历，即可得到要查的元素：
上述即是对Redis的跳跃表的原理的⼀个简述。
这种跳跃表的实现，其实和⼆分查的思路有点接近，只是⼀⽅⾯因为⼆分查只能适⽤于数组，⽽⽆法适⽤于链表，所以为了让链表有⼆分查类似的效率，就以空间换时间来达到⽬的。
跳跃表因为是⼀个根据分数权重进⾏排序的列表，可以再很多场景中进⾏应⽤，⽐如排⾏榜，搜索排序等等。
命令操作：
添加元素，zadd zsetName score1 value1 score2 value2 score3 value3 .....
查看所有元素，zrange zsetName 0 -1
查看所有元素，按score逆序排列， zrevrange zsetName 0 -1
元素数量，zcard zsetName
获取指定value的分数， zscore zsetName value
获取指定value的排名，zrank zsetName value(从0开始)
redis八种数据结构
获取指定分值区间中的元素， zrangebyscore zsetName scoreStart scoreEnd(包含上下区间)（注意inf表⽰⽆穷⼤，-inf表⽰服务券⼤）
获取指定分值区间中的元素，并且返回分数， zrangebyscore zsetName scoreStart scoreEnd withscores
删除元素，zrem zsetName value

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