你了解Redis中的跳跃表吗?

本文涉及的产品
云数据库 Tair(兼容Redis),内存型 2GB
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
简介: 你了解Redis中的跳跃表吗?

跳跃表的基本内容:

对于一个有序序列,链表相对于数组来说,删除和插入的效率要快很多,只需要改变指针的指向,但是在查找的时候,数组就要更占优势一些,可以随机访问,然而链表需要从头开始遍历,最坏的情况下可能达到了O(n),为了改变链表的这一弊端,人们就想出了利用空间换时间的策略,尝试给链表加个索引,假设我们当前有如下所示的普通链表:


我们要查找18需要比较8次

但如果如下所示我们给当前链表添加一层索引,那么只需要比较5次

如果我们给当前链表添加两层索引(如下所示),那么只需要比较4次

跳表的第一层存储的是所有的元素每个节点存在两个指针指向后继节点下一层的节点查找的时候从最高层开始逐层比较直到第一层

对于跳跃表来说,假设我们现在想要插入数据,我们不但要在链表中插入数据,还要去更新索引,如果直接插入数据而不更新索引,那么很有可能出现两个索引之间存在大量的数据,同时也失去了创建索引的意义,那么要如何更新索引呢?


上层节点个数应该是下层节点个数的二分之一,因此我们希望这个新节点添加到上一层的概率是二分之一,最简单的方式就是抛硬币,因为正反面的概率都是二分之一,所以我们只要让它在0和1之间随机,如果是0就停止,如果是1就继续,最后出现的次数k,就代表我们需要在第一层到第k层之间添加索引,当然我们也不能让它无限增长,所以我们还需要添加一个最大值的限制

public int getRandom(){
        int k=1;
        Random random=new Random();
        //random.nextBoolean()返回一个随机的 boolean 值,即 true 或 false
       while(random.nextBoolean()&&k<MAX_VALUE){
            k++;
       }
       return k;
}

跳跃表的增删改查:

比如我们添加一个节点为13,随机值为2

那么我们只需要在第一层和第二层加入13即可

删除操作就比较简单了,直接将我们节点和跨越的层数删除即可

时间复杂度:

第一层的索引节点数为n个,第二层为n/2个,那么第K层的索引节点数为

注意:当某层的索引节点只有两个时,我们就不增加索引了

下述中的2为当索引个数为2时,我们就不再添加索引了,h为跳跃表的高度

如果我们每一层要遍历X个节点,那么在跳表中查找的时间复杂度就为O(Xlogn),可认为O(logn)

由于插入和删除的时间复杂度都是O(1),时间主要花费在查找元素的位置,所以插入和删除的时间复杂度都为O(logn)

相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
6月前
|
存储 NoSQL Java
【Redis系列】那有序集合为什么要同时使用字典和跳跃表
面试官问:那有序集合为什么要同时使用字典和跳跃表来实现?我:这个设计主要是考虑了性能因素。1. 如果单纯使用字典,查询的效率很高是O(1),但执行类似ZRANGE、ZRNK时,排序性能低。每次排序需要在内存上对字典进行排序一次,同时消耗了额外的O(n)内存空间
【Redis系列】那有序集合为什么要同时使用字典和跳跃表
|
4月前
|
NoSQL Redis
Redis 中的跳跃表是什么?
Redis 中的跳跃表(Skiplist)是一种可以替代平衡树的数据结构,它主要用于实现有序集合(Sorted Set)功能。跳跃表通过在多个层级的链表上增加索引来提高查询效率,其效率可以与平衡树相媲美,但实现起来更简单。
41 1
|
4月前
|
消息中间件 存储 NoSQL
Redis数据结构—跳跃表 skiplist 实现源码分析
Redis 是一个内存中的数据结构服务器,使用跳跃表(skiplist)来实现有序集合。跳跃表是一种概率型数据结构,支持平均 O(logN) 查找复杂度,它通过多层链表加速查找,同时保持有序性。节点高度随机生成,最大为 32 层,以平衡查找速度和空间效率。跳跃表在 Redis 中用于插入、删除和按范围查询元素,其内部节点包含对象、分值、后退指针和多个前向指针。Redis 源码中的 `t_zset.c` 文件包含了跳跃表的具体实现细节。
|
4月前
|
存储 NoSQL Redis
Redis数据结构—跳跃表 skiplist
Redis数据结构—跳跃表 skiplist
|
存储 NoSQL 算法
Redis从入门到精通之答疑为什么ZSet使用跳跃表而不是平衡树、哈希表
有同学阅读了Redis从入门到精通章节中的《Redis从入门到精通之底层数据结构跳表 SkipList》向我提问Redis从入门到精通之答疑为什么ZSet使用跳跃表而不是平衡树、哈希表。今天就做一个解答
1040 7
Redis从入门到精通之答疑为什么ZSet使用跳跃表而不是平衡树、哈希表
|
存储 NoSQL Redis
今天终于知道 Redis 为什么要用跳跃表了
Redis 为什么会选择用跳表来实现有序集合呢? 为什么不用红黑树呢?学完今天的内容,你就知道答案了。
430 1
|
存储 机器学习/深度学习 NoSQL
|
存储 NoSQL 算法
Redis中ZSet的底层数据结构跳跃表skiplist,你真的了解吗?
Redis中ZSet的底层数据结构跳跃表skiplist,你真的了解吗?
203 0
|
NoSQL Redis
5分钟了解Redis的内部实现跳跃表(skiplist)
跳跃表(skiplist)是一个有序的数据结构,它通过在每个节点维护不同层次指向后续节点的指针,以达到快速访问指定节点的目的。跳跃表在查找指定节点时,平均时间复杂度为,最坏时间复杂度为O(N)。
259 0
5分钟了解Redis的内部实现跳跃表(skiplist)
|
机器学习/深度学习 NoSQL API
Redis的设计与实现(4)-跳跃表
跳跃表 (skiplist) 是一种有序数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。Redis 使用跳跃表作为有序集合键的底层实现之一。
76 2