Redis使用经验总结02-为什么使用跳表


1、跳表更省内存,not very memory intensive

2、sorted set经常使用zrange zrevrange操作,会把跳表等价于链表,性能上不比红黑树等平衡树差

3、跳表更简单,容易debug ,可以在O(long(N))的复杂度实现ZRANK

  • 每个跳跃表节点的层高都是 1 至 64 之间的随机数。
  • 层高越高出现的概率越低,层高为i的概率为

image-20210315112521349

在redis实现中 p=1/4, 层高期望为E约等于1.33,所以节点的平均层高约等于1.33是个常数,从而得出跳跃表的空间复杂度为O(n)。

sorted set命令:

ZRANK key member

返回有序集key中成员member的排名。其中有序集成员按score值递增(从小到大)顺序排列。排名以0为底,也就是说,score值最小的成员排名为0。

使用ZREVRANK命令可以获得成员按score值递减(从大到小)排列的排名。

ZRANGE myzset 0 -1

返回制定区间得分的数据 如果得分相同,将按字典排序

当你需要元素从最高分到最低分排列时,请参阅ZREVRANGE(相同的得分将使用字典倒序排序)

ZREVRANGE key start stop [WITHSCORES]

和 zrange相反,得分从高到低

image-20210315112429349

image-20210315112440419