北京通信管理局网站备案,西樵建网站,课程网站建设总体情况,英国做deal的网站#x1f3c6; 作者简介#xff1a;席万里 ⚡ 个人网站#xff1a;https://dahua.bloggo.chat/ ✍️ 一名后端开发小趴菜#xff0c;同时略懂Vue与React前端技术#xff0c;也了解一点微信小程序开发。 #x1f37b; 对计算机充满兴趣#xff0c;愿意并且希望学习更多的技… 作者简介席万里 ⚡ 个人网站https://dahua.bloggo.chat/ ✍️ 一名后端开发小趴菜同时略懂Vue与React前端技术也了解一点微信小程序开发。 对计算机充满兴趣愿意并且希望学习更多的技术接触更多的大神提高自己的编程思维和解决问题的能力。
Sorted SET 文章目录 跳表1.跳表是什么2.Redis的跳表实现总结重要 ZSET1.ZSET是什么2.适用场景3.常用操作4.底层实现5.总结重要 跳表
1.跳表是什么
跳表是Redis有序集合ZSet底层的数据结构跳表在ZSET中尤其重要。 跳表的本质还是链表只是在普通链表的基础上增加了多级的索引通过索引可以一次实现多个节点的跳跃提高性能。 跳表的结构
标准的跳表Redis不是使用标准的跳表有以下限制
score值不能重复只有向前指针没有回退指针。
2.Redis的跳表实现 Redis跳表单个节点有几层 层次的决定需要比较随机Redis是使用概率均衡的思路来确定新插入节点的层数。
Redis跳表决定每一个节点是否能增加一层的概率为25%而最大层数限制在Redis5.0是64层Redis7.0是32层。
Redis跳表优化了多少 O(N)降低到log(N)。
总结重要
1、跳表是什么和普通链表的区别
跳表也算链表不过相对普通链表增加了多级索引通过索引可以实现O(logN)的元素查找效率。
2、聊聊跳表的查找过程 从高级索引往后找如果下个节点比当前大就降级继续找。
3、跳表查询节点总数的平均时间复杂度 跳变编码模式下查询节点总数的平均时间复杂度是O(1)因为跳表头结构中定义了一个保存节点数量的字段Length源码中调用查询节点总数的api时会直接返回这个字段。
4、跳表中一个节点的层高是怎么决定的 跳表插入新节点会计算一个随机的层高跳表的每一个节点一开始默认都是1层然后每增加一层的概率都是25%在5.0版本最高为64层。
5、跳表插入一条数据的平均时间复杂度 跳表是一种支持多级索引的结构查询效率媲美二分查找插入一条数据的时间复杂度为OlogN。
6、跳表插入数据会影响其他节点吗 不会。节点层高在创建时就确认了不会被新插入节点影响。新插入节点只会影响每一层前一跳、后一跳的关联指针。
ZSET
1.ZSET是什么
ZSET就是有序集合也叫SORTED SET是一组按关联积分有序的字符串集合这里的分数是个抽象概念任何指标都可以抽象为分数以满足不同场景。积分相同的情况下按字典序排序。
2.适用场景
用于需要排序集合的场景最为典型的就是游戏排行榜。
3.常用操作
创建ZADD查询ZRANGE、ZCOUNT、ZRANK、ZCARD、ZSCORE更新ZADD、ZREN删除DEL、UNLINK 1.写操作 1、ZADD key scoremember [score member …] 向ZSET增加数据如果key已经存在则更新对应数据。 扩展参数XX仅更新存在的成员不添加新成员。NX不更新存在的成员只添加新成员。LT更新新的分值比当前分值小的成员不存在则新增。GT更新新的分值比当前分值大的成员不存在则新增。 2、ZREM key member[member …] 删除ZSET中的元素。 2.读操作 1、ZCARD key查看成员总数。 2、ZRANGE key start stop查看从start到stop范围的ZSET数据。 3、ZREVRANGE key start stop从大到小遍历。 4、ZCOUNT key min max计算min-max积分范围的成员个数。 5、ZRANK key member查看ZSET中的member的排名索引。 6、ZSCORE key member查询ZSET中成员的分数。 4.底层实现
ZSET编码有两种方式一种是ZIPLIST另一种是SKIPLISTHASHTABLE。 ZIPLIST编码的使用条件
列表对象保存的所有字符串对象长度都小于64字节。列表对象元素个数少于128个。 若有一条不满足编码就使用SKIPLISTHASHTABLE。 SKIPLIST是一种可以快速查找的多级链表结构。并且还使用HASHTABLE来配合查询O(1)。
5.总结重要
1、ZSET底层有哪些编码方式 ZSET底层有两种编码方式当ZSET元素大小小于64字节数量小于128时编码为ZIPLIST否则就为HASHTABLSKIPLIST。
2、跳表模式下查询节点总数的时间复杂度 通过字段获得O(1)。
3、跳表中一个节点的层高是怎么决定的 跳表的每一个节点每增加一层的概率都是25%最高为32层。
4、跳表插入一条数据的平均时间是多少 跳表通过创建多级索引的方式可以对比二分查找理论上插入一条数据的时间复杂度为Ologn。
5、为什么跳表和HASHTABLE配合使用呢 跳表适合范围查询HT适合单点查询执行ZSCORE的时候用HT执行ZRANK的时候用跳表。
6、为什么不用B树 B树的数据都存放在叶子节点使得查找时可能会占用更大的内存而且B树插入数据需要维护树的平衡开销比跳表更大。
