0.跳表基础知识
跳表(skiplist)是一种有序数据结构, 它通过在每个节点中维持多个指向其他节点的指针, 从而达到快速访问节点的目的。
跳跃表支持平均 O(log N) 最坏 O(N) 复杂度的节点查找, 还可以通过顺序性操作来批量处理节点。
在大部分情况下,跳跃表的效率可以和平衡树相媲美,并且因为跳跃表的实现比平衡树要来得更为简单,所以有不少程序都使用跳跃表来代替平衡树。
一个跳表的图示如下
可以看到如果要查找117这个元素,可以沿着红线的方向,“跳”着找,最终找到117,所以效率很高。
参考资料
SkipList 跳表
在JDK6中也加入了跳表的实现ConcurrentSkipListMap和ConcurrentSkipListSet,
他们的功能相当于JDK6以前的TreeMap和TreeSet(两者都采用红黑树来实现),只不过新的跳表更高级了,支持高并发。
1.高层视角解读
请先看这篇文章
跳跃表的实现
redis中的skiplist的数据结构如图所示
2.底层代码
API定义请看redis.h/zskiplistNode 和 redis.h/zskiplist
API实现请看t_zset.c,将近4000行代码。
span的作用?
跨度实际上是用来计算排位(rank)的: 在查找某个节点的过程中, 将沿途访问过的所有层的跨度累计起来, 得到的结果就是目标节点在跳跃表中的排位。
可以看zslGetRank函数的代码,正是有了这个span,使得计算一个元素的rank可以非常的高效!
- 大小: 32.3 KB
分享到:
相关推荐
NULL 博文链接:https://xpenxpen.iteye.com/blog/2090620
redis源码阅读中文分析注释
NULL 博文链接:https://xpenxpen.iteye.com/blog/2093786
NULL 博文链接:https://xpenxpen.iteye.com/blog/2091126
NULL 博文链接:https://xpenxpen.iteye.com/blog/2088678
scala连接redis哨兵模式 demo 使用scala的redis库(csdn)————程序
redis安装遇到的问题——linux centos7.5,包括未安装gcc,make不能编译等所有问题
Redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。 附件里面包括redis源码,phpredis源码,redis指令及文档
Redis,即远程字典服务,是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。...本文适合Redis初学者和进阶者阅读,是一份全面而实用的学习笔记。
redis源码级别的分析。需要具备c语言基础的开发学习,十分详细,带你全程深入了解redis。
1. 介绍经典的skiplist数据结构,并进简单的算法分析 2. 讨论Redis的skiplist的具体实现 3. 讨论sorted set是如何在skipl
redis的可视化工具,方便进行测试
Redis全套学习笔记 完整版pdf.rar set:添加键值对 get:获取值 apend:追价值 strlen:获取值的长度 setnx:key不存在时,设置key的值 incr:原子递增1 decr:原子递减1 incrby/decrby:递增或者递减指定的数字 ...
Redis全套学习笔记-带章节目录
springBoot集成Redis源码,springBoot集成Redis源码,springBoot集成Redis源码
redis的学习笔记
Redis源码阅读参考资料1
Redis学习笔记.pdf 含目录 #资源达人分享计划#
Redis的Windows版本源码
学习狂神说-Redis视频笔记,笔记完整并且加入了个人的理解和认知,笔记工整清晰,而且适合记忆学习。