美文网首页
redis中zset原理

redis中zset原理

作者: shark没有辣椒 | 来源:发表于2021-12-05 20:38 被阅读0次

    redis中有一个非常重要的数据结构,那就是Zset。它是一个有序集合,也就是说存储的数据是有序的。

    说到有序集合,很容易就能想到二叉搜索树,比如AVL树、红黑树、B树、B+树这些数据结构。而Zset底层使用的是什么数据结构呢,其实zset使用的是跳跃表(skipList)的数据结构。

    什么是跳跃表?
    它其实是一种随机化的数据结构,一个多层的有序链表,一种基于概率统计的插入算法。

    那么redis中为什么不使用红黑树而使用跳跃表?

    • 首先,在做范围查询的时候,平衡树的操作要比跳跃表复杂。因为平衡树,在查询到最小值的时候,还需要采用中序遍历去查询最大值。 而skipList只需要在找到最小值后,对第一层的链表(也就是最底层的链表)进行若干次遍历即可。
    • 平衡树的删除和插入,需要对子树进行相应的调整,操作复杂。而skiplist只需要修改相邻的节点即可。
    • 在做查询操作的时候,skiplist和平衡树都是O(logN)的时间复杂度。
    • 从整体上来看,skiplist算法实现的难度要低于平衡树。
    图1

    跳跃表就像是上图一样的一个多层的链表,如果查询46的话。其步骤是:
    (1)查询L4层,查询->55,需要查询1次
    (2)查询L3层,查询->21–>55,需要查询2次
    (3)查询L2层,查询->37–>55,需要查询2次
    (4)查询L1层,查询->46,查询1次,找到结果

    跳跃表就好像每两个元素抽取一个元素放到上一层,这样一次叠加,就形成了多层的链表。上一层的元素个数是下一层元素个数的1/2,所以查询的时候就类似二分查找。

    这种方法类似于二分查找的方法,所以跳跃表的查找的时间复杂度为O(logN)。

    跳跃表每个节点包含两个指针,一个指向同一链表中的下一个元素(next),一个指向下面一层的元素(down)。

    我们来看一下插入,往跳表中插入数据的时候,可以选择同时将这个数据插入到第几层中,比如随机函数生成了值 K,那我们就将这个结点添加到第一层到第 K 层这 K 级索引中。

    随机的K是如何产生的:
    通过随机数来产生,第一层肯定需要添加元素,所以K的初始值为1。后面的,如果随机数为1,就是K加一,随机数为0,就退出。这样每一层插入该元素的概率为1/2的n次方。这样就很大程度上保证了后一层元素的总数量是前一层元素的2倍。

    int random_level()  
    {  
        K = 1;  
    
        while (random(0,1))  
            K++;  
    
        return K;  
    } 
    

    再看删除,在各个层中找到包含 x 的节点,使用标准的 delete from list 方法删除该节点。直接删除元素,然后调整一下删除元素后的指针即可。跟普通的链表删除操作完全一样。

    跳跃表插入和删除的时间复杂度都是O(logN)。


    本文转载自:
    https://blog.csdn.net/zy450271923/article/details/106970148/

    相关文章

      网友评论

          本文标题:redis中zset原理

          本文链接:https://www.haomeiwen.com/subject/zwrnxrtx.html