文章目录

      • 1. ZSet
      • 2. Skiplist(重点)

1. ZSet

Zset在redis6和redis 7的实现是不同的,redis 6的实现采用的是ziplist+skiplist,redis 7中采用的是listpack+skiplist

  • redis 6

我们看看相关配置:


当我们有序集合中包含的元素的数量超过了服务器属性server.zset_max_ziplist_entries的值,默认是128,或者有序集合中新添加的元素的member的长度大于服务器数学server.zset_max_ziplist_value的值(默认是64)时,redis会使用跳跃表来作为有序集合的底层实现,否则就使用ziplist。

  • redis 7

我们看看相关配置:

只是将底层的ziplist换成了listpack,其它没变

2. Skiplist(重点)

首先分析一下单链表,对于一个单链表来说,即便链表中存储的数据是有序的,如果我们要想在其中查找某个数据,也只能从头到尾遍历链表,这样查找效率会很低,时间复杂度为O(N)。


所以能不能加快链表查询?

解决方法:空间换时间,得到了下面的方案


从上面这个例子看出,加了一层索引之后,查找一个节点需要遍历的节点的个数减少了,也就是查找的效率提高了。现在,假设链表中有64个节点,按照上面两两取首的思路,我们建立了一个五级索引,如下:

可以发现数据量特别大时,查询次数得到了大大的减少,下面我们就得出了跳表的概念:

skiplist时一种空间换时间的结构,由于链表无法进行二分查找,因此借鉴数据库索引的思想,提取出链表中的关键节点(索引),先在关键节点上查找,再进入下层链表查找,提出多层关键节点,就形成了跳表。但是注意,跳表也需要占用一定的空间,所以索引添加的越多,空间占用就会越多。

跳表:链表+索引

  • 跳表时间复杂度分析:

跳表的时间复杂度:O(logN)

  • 跳表的空间复杂度

跳表的空间复杂度:O(n)

  • 跳表的优缺点:

优点:跳表时一个典型的空间换时间的解决方案,而且只有在数据量较大的情况下才能体现出优势,而且应该是读多写少的情况下使用,所以它的适用范围也是有限的

缺点:维护成本高,在单链表中,一旦定位好要插入的位置,插入节点的时间复杂度很低的就是O(1),但是新增或者删除时需要把索引都更新一遍,为了保证数据的有序性,我们需要先找到要操作的位置,这个超找操作就会比较耗时最后在新增和删除过程中的更新,时间复杂度也是O(logn)