Redis从入门到精通之答疑为什么ZSet使用跳跃表而不是平衡树、哈希表

本文涉及的产品
Serverless 应用引擎免费试用套餐包,4320000 CU,有效期3个月
性能测试 PTS,5000VUM额度
云原生网关 MSE Higress,422元/月
简介: 有同学阅读了Redis从入门到精通章节中的《Redis从入门到精通之底层数据结构跳表 SkipList》向我提问Redis从入门到精通之答疑为什么ZSet使用跳跃表而不是平衡树、哈希表。今天就做一个解答

对比介绍

Redis使用跳跃表(Skip List)来实现有序集合(Sorted Set)的存储和操作,而不是使用平衡树(Balanced Tree)或者哈希表(Hash Table),这是因为跳跃表具有以下优点:

  1. 跳跃表的实现比较简单,容易理解和实现,而平衡树的实现比较复杂,需要考虑多种情况,容易出错。哈希表虽然实现简单,但是对于有序集合的操作比较困难。

  2. 跳跃表可以实现快速的插入、删除和查找操作,时间复杂度为O(log n),与平衡树相当,而哈希表在最好情况下可以实现O(1)的时间复杂度,但是在最坏情况下,时间复杂度为O(n),并且无法实现有序集合的排序和范围查找等操作。

  3. 跳跃表可以支持高并发的写入操作,因为每个节点都有多个指针,可以实现多个线程同时插入或删除节点,而平衡树和哈希表都需要进行加锁或者使用复杂的并发控制算法来保证并发的正确性。

虽然跳跃表与平衡树和哈希表相比有一些优点,但是也有一些缺点,比如:

  1. 跳跃表的空间复杂度比较高,因为每个节点都需要多个指针来连接不同的层级,而哈希表和平衡树只需要一个指针即可。

  2. 跳跃表的查找性能虽然比较好,但是不如哈希表那么快,因为跳跃表需要进行多次比较才能找到指定元素,而哈希表只需要一次哈希计算即可。

平衡树和哈希表特点

平衡树是一种二叉搜索树,它的特点是所有叶子节点深度相同,因此可以保证在最坏情况下的查找、插入和删除操作的时间复杂度都是 O(log n)。常见的平衡树有红黑树、AVL树、B树等。

哈希表是一种通过哈希函数将关键字映射到索引位置的数据结构,它的查询、插入和删除操作的时间复杂度通常是 O(1),但在最坏情况下会退化到 O(n)。哈希表的主要缺点是它不能直接支持范围查询,因此在一些场景下需要使用有序集合。

Redis的有序集合需要支持范围查询,同时还需要支持高效的插入和删除操作,因此采用了跳跃表(Skip List)作为底层数据结构,而不是使用平衡树或哈希表。跳跃表是一种可以高效支持范围查询的有序数据结构,它基于多层链表实现,每一层链表的节点数是前一层的 1/2 左右,而顶层链表的节点数为 2,因此可以在 O(log n) 的时间复杂度内进行范围查询、插入和删除操作。

下面是平衡树、哈希表和跳跃表的简单示意图:

平衡树示意图:

          10
         /  \
        5   15
       / \    \
      2   7   20

哈希表示意图:

   0 -> "value1"
   1 -> "value2"
   2 -> "value3"
   3 -> "value4"
   4 -> "value5"
   ...

跳跃表示意图:

         +------+    +------+              +------+    
Head --->|  0   |---->|  1   |--------------|  7   |----> NULL
         +------+    +------+    +------+   +------+    
                                  |  5   |---|  9   |----> NULL
                                  +------+   +------+

在上面的跳跃表示意图中,每个节点包含了一个值和多个指针,指向同一层的下一个节点和下一层的节点。顶层链表中的节点数最少,每往下一层增加一倍。例如,第一层链表的节点数为 4,第二层链表的节点数为 2,第三层链表的节点数为 1。

对于于一个单链表来讲,即便链表中存储的数据是有序的,如果我们要想在其中查找某个数据,也只能从头到尾遍历链表。这样查找效率就会很低,时间复杂度会很高,是 O(n)。比如查找12,需要7次查找
image.png

如果我们增加如下两级索引,那么它搜索次数就变成了3次

image.png

总结

从上面可以看出来,Redis使用跳跃表作为有序集合的底层数据结构,主要是因为跳跃表具有实现简单、操作高效、并发性能好等优点,可以满足Redis对有序集合的高效操作需求。同时,Redis也提供了其他数据结构,比如哈希表、列表、集合等,可以根据实际需求来选择合适的数据结构。

相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore     ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库 ECS 实例和一台目标数据库 RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
目录
相关文章
|
2月前
|
缓存 NoSQL Java
springboot的缓存和redis缓存,入门级别教程
本文介绍了Spring Boot中的缓存机制,包括使用默认的JVM缓存和集成Redis缓存,以及如何配置和使用缓存来提高应用程序性能。
127 1
springboot的缓存和redis缓存,入门级别教程
|
2月前
|
存储 消息中间件 NoSQL
Redis 入门 - C#.NET Core客户端库六种选择
Redis 入门 - C#.NET Core客户端库六种选择
69 8
|
1月前
|
存储 NoSQL 关系型数据库
Redis的ZSet底层数据结构,ZSet类型全面解析
Redis的ZSet底层数据结构,ZSet类型全面解析;应用场景、底层结构、常用命令;压缩列表ZipList、跳表SkipList;B+树与跳表对比,MySQL为什么使用B+树;ZSet为什么用跳表,而不是B+树、红黑树、二叉树
|
1月前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet
|
4月前
|
NoSQL 安全 Java
Redis6入门到实战------ 三、常用五大数据类型(字符串 String)
这篇文章深入探讨了Redis中的String数据类型,包括键操作的命令、String类型的命令使用,以及String在Redis中的内部数据结构实现。
Redis6入门到实战------ 三、常用五大数据类型(字符串 String)
|
4月前
|
NoSQL 关系型数据库 Redis
Redis6入门到实战------ 九、10. Redis_事务_锁机制_秒杀
这篇文章深入探讨了Redis事务的概念、命令使用、错误处理机制以及乐观锁和悲观锁的应用,并通过WATCH/UNWATCH命令展示了事务中的锁机制。
Redis6入门到实战------ 九、10. Redis_事务_锁机制_秒杀
|
4月前
|
NoSQL Java Redis
Redis6入门到实战------ 八、Redis与Spring Boot整合
这篇文章详细介绍了如何在Spring Boot项目中整合Redis,包括在`pom.xml`中添加依赖、配置`application.properties`文件、创建配置类以及编写测试类来验证Redis的连接和基本操作。
Redis6入门到实战------ 八、Redis与Spring Boot整合
|
3月前
|
存储 NoSQL API
7)深度解密 Redis 的有序集合(ZSet)
7)深度解密 Redis 的有序集合(ZSet)
54 0
|
1天前
|
存储 缓存 NoSQL
解决Redis缓存数据类型丢失问题
解决Redis缓存数据类型丢失问题
109 85
|
2月前
|
消息中间件 缓存 NoSQL
Redis 是一个高性能的键值对存储系统,常用于缓存、消息队列和会话管理等场景。
【10月更文挑战第4天】Redis 是一个高性能的键值对存储系统,常用于缓存、消息队列和会话管理等场景。随着数据增长,有时需要将 Redis 数据导出以进行分析、备份或迁移。本文详细介绍几种导出方法:1)使用 Redis 命令与重定向;2)利用 Redis 的 RDB 和 AOF 持久化功能;3)借助第三方工具如 `redis-dump`。每种方法均附有示例代码,帮助你轻松完成数据导出任务。无论数据量大小,总有一款适合你。
78 6
下一篇
DataWorks