Redis zset 底层数据结构之跳表

本文涉及的产品
云数据库 Tair(兼容Redis),内存型 2GB
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
简介: 0、zset数据结构1、zset底层的数据结构2、跳表介绍3、跳表增删查的时间复杂度4、什么时候使用压缩链表,什么时候使用跳表5、跳表的内部实现及原理6、为什么用跳表而不用红黑树或二叉树呢.........

参考:

0、zset数据结构

  • 【有序集合】
  • 【本质上是集合,所有元素不能重复】
  • 【分数可以重复(相同时根据member字典排序),member不能重复】
  • 【支持根据score的范围查找】

1、zset底层的数据结构是什么?

 zset底层包含 跳表压缩列表

2、跳表是什么?

 跳表(skiplist)是在链表的基础上,增加了多级索引,通过多级索引位置的跳转,实现了快速查找元素。

 跳表这一有序集合,底层是一个名为zset的结构体。而一个zset结构同时包含一个字典和一个跳跃表。跳跃表按score从小到大保存所有集合元素。而字典则保存着从member到score的映射,这样就可以用O(1)的复杂度来查找member对应的score值。虽然同时使用两种结构,但它们会通过指针来共享相同元素的member和score,因此不会浪费额外的内存。

3、跳表的时间复杂度:

 利用空间换时间,查找、新增、删除的时间复杂度都为:O(logN),类似于二分查找。

4、什么时候使用压缩列表,什么时候使用跳表呢?

  • 元素数量小于128
  • 所有member的长度都小于64字节

5、跳表的内部实现及原理:

在这里插入图片描述

  1. 当链表足够长的时候,这种多层链表的查找方式能让我们跳过很多下层节点,大大加快查找的速度。
  2. 跳表为了避免链表在新增/删除时,时间复杂度较低为O(n)的问题,它不要求链表相邻节点的上下层数之间有严格的对应关系,而是为每个节点随机出一个层数(level)
  3. 从跳表的创建和插入过程可以看出,每一个节点的层数(level)是随机出来的,而且新插入一个节点不会影响其它节点的层数。因此,插入操作只需要修改插入节点前后的指针,而不需要对很多节点都进行调整,这就降低了插入操作的复杂度。实际上,这是跳表的一个很重要的特性
  4. 跳表其实除了最下面第1层链表之外,它会产生若干层稀疏的链表,这些链表里面的指针故意跳过了一些节点(而且越高层的链表跳过的节点越多)。这使得我们在查找数据时能先在高层链表中查找,然后逐层降低,最终降到第1层链表来精确查找数据位置。在这个过程中,我们跳过了一些节点,从而也就加快了查找速度
  5. 实际应用中的跳表每个节点应该包含member和value两部分。实际上列表中是按照member对应的score值从小到大进行排序的(score值相同时按member字典序排列),查找过程也是根据member来比较。
  6. MaxLevel = 32,默认最大层数
  7. 实际上,Redis中sorted set的实现是这样的:
  • 当数据较少时:zset是由一个压缩列表来实现的
  • 当数据较多时:zset是由一个 字典 + 跳表 来实现的。简单来讲,dict用来查询数据到分数的对应关系,而skiplist用来根据分数查询数据(可能是范围查找)
  1. 第1层链表不是一个单向链表,而是一个双向链表,这是为了方便以倒序方式获取一个范围内的元素

6、为什么用跳表而不用红黑树或二叉树呢?

  1. 范围查找时,跳表效率比红黑树高。跳表可以通过查找区间的起点,然后依次往后遍历即可~
  2. 跳表的实现比红黑树简单(红黑树在新增/删除时,可能会面临反转等操作),更易理解与实现,且可以通过控制跳表的索引层级来控制内存的消耗。
相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
目录
相关文章
|
2月前
|
存储 缓存 NoSQL
Redis核心数据结构与分布式锁实现详解
Redis 是高性能键值数据库,支持多种数据结构,如字符串、列表、集合、哈希、有序集合等,广泛用于缓存、消息队列和实时数据处理。本文详解其核心数据结构及分布式锁实现,帮助开发者提升系统性能与并发控制能力。
|
4月前
|
存储 NoSQL 算法
Redis设计与实现——数据结构与对象
Redis 是一个高性能的键值存储系统,其数据结构设计精妙且高效。主要包括以下几种核心数据结构:SDS、链表、字典、跳跃表、整数集合、压缩列表。此外,Redis 对象通过类型和编码方式动态转换,优化内存使用,并支持引用计数、共享对象和淘汰策略(如 LRU/LFU)。这些特性共同确保 Redis 在性能与灵活性之间的平衡。
|
7月前
|
NoSQL 算法 安全
Redis原理—1.Redis数据结构
本文介绍了Redis 的主要数据结构及应用。
Redis原理—1.Redis数据结构
|
6月前
|
存储 NoSQL Redis
投行系统的毫秒级榜单响应:如何用Redis ZSET破解同分排序难题?
通过Redis的ZSET数据结构和更新时间戳,解决投行交易系统实时排行榜中同分跳变的问题。具体方案为:将交易量作为整数部分,更新时间戳作为小数部分,确保同分时按最新更新排序,实现实时、高效、无需应用层干预的排行榜功能。一句话总结:通过Redis ZSET加更新时间戳,解决百万交易排行榜实时显示及同分难题。
|
11月前
|
存储 消息中间件 NoSQL
Redis 数据结构与对象
【10月更文挑战第15天】在实际应用中,需要根据具体的业务需求和数据特点来选择合适的数据结构,并合理地设计数据模型,以充分发挥 Redis 的优势。
224 64
|
存储 NoSQL 算法
「Redis」数据结构与对象
Redis数据结构与对象介绍
117 0
|
NoSQL 算法 Java
Redis进阶 - 数据结构:对象机制详解,一文深入底层分析
我们在前文已经阐述了Redis 5种基础数据类型详解,分别是字符串(string)、列表(list)、哈希(hash)、集合(set)、有序集合(zset),以及5.0版本中Redis Stream结构详解;那么这些基础类型的底层是如何实现的呢?Redis的每种对象其实都由对象结构(redisObject) 与 对应编码的数据结构组合而成, 本文主要介绍对象结构(redisObject) 部分。
Redis进阶 - 数据结构:对象机制详解,一文深入底层分析