redis的zset数据结构:跳表

点赞再看,养成习惯,微信搜索「小大白日志」关注这个搬砖人。

文章不定期同步公众号,还有各种一线大厂面试原题、我的学习系列笔记。


广州这边封闭式管理好久了,今天终于周末可以出去溜溜了
redis的zset数据结构:跳表

什么是zset

zset是redis中一种有序、不重复的数据类型,每个元素都有一个分值,它可用于实现排行榜单,其底层采用压缩表ziplist或跳表skiplist的数据结构实现

zset的两种数据结构

  • 压缩表ziplist

当redis插入第一个元素时,同时满足以下条件,就会以ziplist创建跳表

  • 节点数量<128 (可通过server.zset_max_ziplist_entries设置)
  • 节点的长度<64(可通过server.zset-max-zip以上任一个,都会list-value设置)

当选择用ziplist实现zset后,以后插入的节点若不满足以上任一个条件,就会转为skiplist

  • 跳表skiplist

跳表的本质是一个多层链表,它能快速地查询、插入、删除【时间复杂度均为O(logn)】,所以它的查询速度媲美平衡二叉树,而且它的数据结构比平衡二叉树简单,结构示意图如下:

redis的zset数据结构:跳表
特点:

  • 跳表的最底层拥有所有的元素
  • 跳表每一层都是一个链表,除了最底层是原始链表,层次逐渐往上可分别划分为一级索引层、二级索引层...
  • 跳表插入元素时,会先随机生成出一个“层次数字”,然后元素会插入到这个层次的所有底层,直到原始链表层
  • 如果一个元素存在与某个索引层,那么这个元素也会存在于低于它的所有索引下层,如元素在第99索引层,那么由上到下从99索引层直到原始链表层都会存在该元素
  • 空间换时间,跳表查找变快了,但是要存储许多索引层,故空间开销变大了
 /**
 * 产生节点的高度。使用抛硬币
 *
 * @return
 */
 private int getRandomLevel() {
     //可知,元素的插入层次i从1开始自增,随机到哪一层的概率就像抛硬币一样,都是50%,故i越往后,其概率越小(每次都*0.5)
     //第一层概率:0.5,第二层0.5*0.5=0.25,...
        int lev = 1;
        while (random.nextInt() % 2 == 0) {
            lev++;
        }
        //MAX_LEVEL为跳表的最大层级
        return lev > MAX_LEVEL ? MAX_LEVEL : lev;
    }

跳表skiplist

  • 插入节点

    • 插入的时间复杂度为O(logn),每次插入都会先查找到要插入的位置(查找的时间复杂度就已经是【O(logn)】了,找到后直接插入【O(1)】,所以总的为【O(logn)】),删除也是同理为O(logn)
    • 每个节点的插入层次是通过getRandomLevel()随机出来的,插入层次互不影响

      以下模拟节点插入:
      redis的zset数据结构:跳表
  • 查找

查找节点时,从高索引层往低索引层查找:

一开始元素在高层从链表由前往后查找,直到要查找的目标元素在该层的某两个相邻元素之间,就会往下跳到下层的同一个位置,继续从同一位置向链表尾方向遍历查询->重复上面的过程,直到查找到目标元素

查找时每一层都跳过部分元素,进而加快了查找效率,以下模拟节点查找:
redis的zset数据结构:跳表

OK,如果文章哪里有错误或不足,欢迎各位留言。
创作不易,各位的「三连」是二少创作的最大动力!我们下期见!

上一篇:python3中 tkinter模块创建window窗体、添加按钮、事务处理、创建菜单等的使用


下一篇:propertychange input change