Redis底层数据结构之 zset

zset是Redis提供的一个非常特别的数据结构，常用作排行榜等功能，以用户id为value，关注时间或者分数作为score进行排序。与其他数据结构相似，zset也有两种不同的实现，分别是zipList和skipList。zipList前面我们已经介绍过了，这里就不再介绍了。那什么是跳表呢？

Redis的zset是一个复合结构，一方面类似于Java的数据结构HashMap，可以给每一个元素value赋予一个权重score，使用hash结构来存储value和score的对应关系，即Map<Object,Double>。另一方面它又类似于TreeSet，内部的元素会按照权重score进行排序，可以得到每个元素的名次，还可以通过score的范围来获取元素的列表。

• zipList：满足以下两个条件
  • [score,value]键值对数量少于128个；
  • 每个元素的长度小于64字节；
• skipList：不满足以上两个条件时使用跳表、组合了map和skipList
  • map用来存储member到score的映射，这样就可以在O(1)时间内找到member对应的分数；
  • skipList按照从小到大的顺序存储分数
  • skipList每个元素的值都是[socre,value]对

使用zipList的示意图如下所示：

跳表 skipList

跳表skipList在Redis中的运用场景只有一个，那就是作为有序列表zset的底层实现。跳表可以保证增、删、查等操作时的时间复杂度为O(logN)，这个性能可以与平衡树相媲美，但实现方式上却更加简单，唯一美中不足的就是跳表占用的空间比较大，其实就是一种空间换时间的思想。跳表的结构如下所示：

在跳跃表中

Redis底层数据结构之 zset

原文：https://www.cnblogs.com/reecelin/p/13368374.html