文章目录
- 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)