扫码订阅《 》或入驻星球,即可阅读文章!

GOLANG ROADMAP

阅读模式

  • 沉浸
  • 自动
  • 日常
首页
Go学习
  • Go学院

    • Go小课
    • Go视界
    • Go小考
    • Go实战
  • Go资源

    • 优质课程
    • 在线宝典
    • 资源下载
    • 帮找资源
训练营 🔥
  • Go体系课&实战训练营
  • 升值加薪陪跑训练营
Go求职
  • 求职刷题

    • 企业题库
    • 面试宝典
    • 求职面经
  • 求职服务

    • 内推互助
    • 求职助力
    • 内推公司
Go友会
  • 城市
  • 校园
推广返佣
  • 返佣排行
  • 返佣规则
  • 推广学院
实验区
  • Go周边
  • Go宝典

    • 推荐图书
    • 精品博文
  • Go开源

    • Go仓库
    • Go月刊
更多
  • 用户中心

    • 我的信息
    • 我的返佣
    • 我的消息
  • 玩转星球

    • 星球介绍
    • 星主权益
    • 吐槽专区
    • 成长记录
  • 合作交流

    • 商务合作
    • 讲师招募
    • 生态伙伴
author-avatar

GOLANG ROADMAP


首页
Go学习
  • Go学院

    • Go小课
    • Go视界
    • Go小考
    • Go实战
  • Go资源

    • 优质课程
    • 在线宝典
    • 资源下载
    • 帮找资源
训练营 🔥
  • Go体系课&实战训练营
  • 升值加薪陪跑训练营
Go求职
  • 求职刷题

    • 企业题库
    • 面试宝典
    • 求职面经
  • 求职服务

    • 内推互助
    • 求职助力
    • 内推公司
Go友会
  • 城市
  • 校园
推广返佣
  • 返佣排行
  • 返佣规则
  • 推广学院
实验区
  • Go周边
  • Go宝典

    • 推荐图书
    • 精品博文
  • Go开源

    • Go仓库
    • Go月刊
更多
  • 用户中心

    • 我的信息
    • 我的返佣
    • 我的消息
  • 玩转星球

    • 星球介绍
    • 星主权益
    • 吐槽专区
    • 成长记录
  • 合作交流

    • 商务合作
    • 讲师招募
    • 生态伙伴
  • 面试宝典系列

    • Redis面试题汇总
  • 宝典内容

    • 1.Redis的数据结构及使用场景?
    • 2.Redis持久化的几种方式?
    • 3.Redis的LRU具体实现?
    • 4.单线程的Redis为什么快?
    • 5.Redis的数据过期策略
    • 6.如何解决Redis缓存雪崩问题?
    • 7.如何解决Redis缓存穿透问题?
    • 8.Redis并发竞争key如何解决?
    • 9.Redis的主从模式和哨兵模式和集群模式区别?
    • 10.Redis事物的了解CheckAndSet操作实现乐观锁
    • 11.Redis有序集合zset底层怎么实现的?
    • 12.跳表的查询过程是怎么样的,查询和插入的时间复杂度

扫码订阅《 》或入驻星球,即可阅读文章!

11.Redis有序集合zset底层怎么实现的?


GOLANG ROADMAP
Redis有序集合zset底层怎么实现的?

Redis中的set数据结构底层用的是跳表实现的.

跳表是一个随机化的数据结构,实质就是一种可以进行二分查找的有序链表。

跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。

跳表不仅能提高搜索性能,同时也可以提高插入和删除操作的性能。

  • (1)跳表是可以实现二分查找的有序链表;
  • (2)每个元素插入时随机生成它的level;
  • (3)最低层包含所有的元素;
  • (4)如果一个元素出现在level(x),那么它肯定出现在x以下的level中;
  • (5)每个索引节点包含两个指针,一个向下,一个向右;
  • (6)跳表查询、插入、删除的时间复杂度为O(log n),与平衡二叉树接近;

为什么Redis选择使用跳表而不是红黑树来实现有序集合?(O(logN))

首先,我们来分析下Redis的有序集合支持的操作:

  • 插入元素
  • 删除元素
  • 查找元素
  • 有序输出所有元素
  • 查找区间内所有元素

其中,前4项红黑树都可以完成,且时间复杂度与跳表一致。但是,最后一项,红黑树的效率就没有跳表高了。 在跳表中,要查找区间的元素,我们只要定位到两个区间端点在最低层级的位置,然后按顺序遍历元素就可以了,非常高效。

而红黑树只能定位到端点后,再从首位置开始每次都要查找后继节点,相对来说是比较耗时的。 此外,跳表实现起来很容易且易读,红黑树实现起来相对困难,所以Redis选择使用跳表来实现有序集合。