学习笔记-Redis设计与实现-跳跃表

本文涉及的产品
云数据库 Tair(兼容Redis),内存型 2GB
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
简介:
  • 跳跃表(skiplist)是一种有序数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。

  • 跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点。

  • Redis使用跳跃表作为有序结合键的底层实现之一,如果一个有序集合包含的元素数量比较多,又或者有序集合中元素的成员(member)是比较长的字符串时,Redis就会使用跳跃表来作为有序集合见的底层实现。


5.1 跳跃表的实现

wKioL1idXK6gtn1KAAQNSmuPXHY976.png


  • zskiplist结构,包含以下属性:

  1. header:指向跳跃表的表头节点

  2. tail:指向跳跃表的表尾节点。

  3. level:记录目前跳跃表内,层数最大的哪个节点的层数(表头节点的层数不计算在内)

  4. length:记录跳跃表的长度,即,跳跃表目前包含节点的数量(表头节点不计算在内)

  • zskiplistNode结构,包含以下属性:

  1. (level):每个层都带有两个属性:前进指针和跨度。前进指针用于访问位于表尾的其他方向的其他节点,而跨度则记录了前进指针所指向节点和当前节点的距离。

  2. 后退(backward)指针:节点中用BW字样标记节点的后退指针,它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。

  3. 分值(score):在跳跃表中,节点按各自所保存的分值从小到大排列。

  4. 成员对象(obj)

  5. 表头节点和其他节点的构造时一样的。


5.2 跳跃表API


wKioL1idXQDR1WbPAAdUXFuJ4AE117.pngwKioL1idXSbgchbXAAhTC-x5HRY801.png


5.3 重点回顾

  • 跳跃表是有序集合的底层实现之一。

  • Redis的跳跃表实现zskiplist和zskiplistNode两个结构组成,其中zskiplist用于保存跳跃表信息,而zskiplistNode则用于表示跳跃表节点。

  • 每个跳跃表节点的层高都是1至32之间的随机数。

  • 在同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的成员对象必须是唯一的。

  • 跳跃表中的节点按照分值大小进行排序,当分值相同时,节点按照成员对象的大小进行排序。



本文转自 许大树 51CTO博客,原文链接:http://blog.51cto.com/abelxu/1896679,如需转载请自行联系原作者
相关实践学习
基于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
相关文章
|
12月前
|
存储 NoSQL Redis
Redis系列学习文章分享---第十六篇(Redis原理1篇--Redis数据结构-动态字符串,insert,Dict,ZipList,QuickList,SkipList,RedisObject)
Redis系列学习文章分享---第十六篇(Redis原理1篇--Redis数据结构-动态字符串,insert,Dict,ZipList,QuickList,SkipList,RedisObject)
137 1
|
12月前
|
NoSQL Java Redis
Redis系列学习文章分享---第十八篇(Redis原理篇--网络模型,通讯协议,内存回收)
Redis系列学习文章分享---第十八篇(Redis原理篇--网络模型,通讯协议,内存回收)
152 0
|
12月前
|
存储 消息中间件 缓存
Redis系列学习文章分享---第十七篇(Redis原理篇--数据结构,网络模型)
Redis系列学习文章分享---第十七篇(Redis原理篇--数据结构,网络模型)
162 0
|
12月前
|
存储 NoSQL 算法
Redis系列学习文章分享---第十篇(Redis快速入门之附近商铺+用户签到+UV统计)
Redis系列学习文章分享---第十篇(Redis快速入门之附近商铺+用户签到+UV统计)
102 0
|
12月前
|
存储 NoSQL Redis
Redis系列学习文章分享---第九篇(Redis快速入门之好友关注--关注和取关 -共同关注 -Feed流实现方案分析 -推送到粉丝收件箱 -滚动分页查询)
Redis系列学习文章分享---第九篇(Redis快速入门之好友关注--关注和取关 -共同关注 -Feed流实现方案分析 -推送到粉丝收件箱 -滚动分页查询)
123 0
|
8月前
|
NoSQL 数据可视化 Linux
redis学习四、可视化操作工具链接 centos redis,付费Redis Desktop Manager和免费Another Redis DeskTop Manager下载、安装
本文介绍了Redis的两个可视化管理工具:付费的Redis Desktop Manager和免费的Another Redis DeskTop Manager,包括它们的下载、安装和使用方法,以及在使用Another Redis DeskTop Manager连接Redis时可能遇到的问题和解决方案。
473 1
redis学习四、可视化操作工具链接 centos redis,付费Redis Desktop Manager和免费Another Redis DeskTop Manager下载、安装
|
8月前
|
NoSQL Linux Redis
Docker学习二(Centos):Docker安装并运行redis(成功运行)
这篇文章介绍了在CentOS系统上使用Docker安装并运行Redis数据库的详细步骤,包括拉取Redis镜像、创建挂载目录、下载配置文件、修改配置以及使用Docker命令运行Redis容器,并检查运行状态和使用Navicat连接Redis。
959 3
|
8月前
|
NoSQL Java Redis
shiro学习四:使用springboot整合shiro,正常的企业级后端开发shiro认证鉴权流程。使用redis做token的过滤。md5做密码的加密。
这篇文章介绍了如何使用Spring Boot整合Apache Shiro框架进行后端开发,包括认证和授权流程,并使用Redis存储Token以及MD5加密用户密码。
152 0
shiro学习四:使用springboot整合shiro,正常的企业级后端开发shiro认证鉴权流程。使用redis做token的过滤。md5做密码的加密。
|
8月前
|
存储 Prometheus NoSQL
大数据-44 Redis 慢查询日志 监视器 慢查询测试学习
大数据-44 Redis 慢查询日志 监视器 慢查询测试学习
113 3
|
8月前
|
NoSQL 关系型数据库 MySQL
Redis 事务特性、原理、具体命令操作全方位诠释 —— 零基础可学习
本文全面阐述了Redis事务的特性、原理、具体命令操作,指出Redis事务具有原子性但不保证一致性、持久性和隔离性,并解释了Redis事务的适用场景和WATCH命令的乐观锁机制。
1021 0
Redis 事务特性、原理、具体命令操作全方位诠释 —— 零基础可学习