Redis 跳表(一种高性能的动态数据结构)
一、前言
跳表(Skip List)这种数据结构在一般的数据结构书籍和算法书籍里都不怎么涉及----至少我大学数据结构课程没有讲这种结构。但是跳表确实是一种性能比较优秀的动态数据结构,并且Redis中的有序集合(Sorted Set)就是用跳表实现的。本文先大致了解一下跳表。
二、跳表
1、引出
对于一组有序数据,我们想要在其中查找某个数,如果数据使用数组存储,显然二分法是再适合不过了,但是如果数据是用链表存储的呢?难道我们用从头遍历吗?这样时间复杂度会达到O(n)级别,相比二分法O(logn)级别简直天壤地别。那么如何提高效率呢?
链表的查找时间复杂度算法为1/n(1+2+3+…+n)=O(n),数据出现的位置从第一个到最后一个的概率均为1/n,但是查询时间分别是1,2,,,n,所以平均时间复杂度为O(n)。
2、跳表
我用图片形式来理解跳表。
如下图,对初始链表做一层“索引”,每两个节点提取一个节点到上一层,然后用down指针连接到下一层。
现在我们查询16这个节点。从第一级索引开始,找到13,并且下一个为17,显然16在这两个节点之间,利用down指针下降一层,这次我们遍历2次即可。利用索引后,遍历了5+2=7次,而原始链表需要10次,这里加一层索引遍历次数减少了,效率提高了一点,但还不够,我们继续往上添加索引层。
这里我不再算了,结果是6次,效率又提高了!
那么这种链表加多级索引就是跳表的结构了。
3、链表查询的时间复杂度是多少?
①假设链表有N个节点,按图所示依次往上级添加索引,第一级有N/2个节点,第二级有N/4个节点。。。。
那么第k级索引有N/(2^k)个节点。
②假设索引有h级,最高级有2个节点。就有N/(2^h)=2--->h=log2N-1(以2为底N的对数)。加上原始链表,那么高度就是log2N了。
③查询时,如果每层都遍历m次(最高级最多遍历2次,其他级最多遍历m次)那么复杂度就是O(mlgN)(在大O表示法里,logaN级别的复杂度等于lnN复杂度,去掉m就是O(logn)级别了),我们求一下m的值。
在第k级时,我们遍历到了y和z,查询值介于两者之间,通过down指针,到达第k-1级,而这一级y和z之间最多有3个节点,那么m就等于3了。
综上跳表的查询时间复杂度就是O(logn)了。
4、跳表的耗费空间吗?
这个问题就很简单了,空间复杂度就是每层节点和,即n/2+n/4+...+4+2=n-2,空间复杂度就是O(n)了。
当然了这里也可以扩大索引间隔,减少一点索引空间,但是我们还是按照上面的求时间复杂度方法,得到的结果仍是O(logn)。实际应用中,向来是比较乐意用空间换时间的,所以这种做法的意义并不大,因为时间复杂度还是没变!
并且这里我们使用整数作为例子来讲得,软件开发中,链表存的可能是一个很大的对象,索引只需要记录关键字和一些指针,那么额外的空间和原数据相比完全可以忽略!
5、高效的动态插入和删除
我想汉字没有图片表达的清楚,所以还是用图片来表述!
时间复杂度仍是O(logn)。我们说单链表插入复杂度为O(1),但是这是指插入动作,并不包含查找插入点所耗的时间,加上查找时间O(n),跳表效率还是高一点!
删除要麻烦一点,因为删除的节点要是在索引中,我们还得更新索引,更新索引就得找到前驱节点,当然双链表可以不用考虑了!
6、索引动态更新
考虑这样一种情况
更极端的可以退化成单链表,所以索引的动态更新是必要的!
AVL树是通过左右旋转保持平衡性,而跳表是通过随机函数生成一个值K,然后将节点添加到第一级到第K级索引中。
关于这个随机函数,我没有做深入研究(水平有限,然后有兴趣可以参考redis中关于有序集合的跳表实现)
三、Redis为什么选择跳表?
严格讲Redis还用到了散列表,但是本文讲的是跳表,所以暂时忽略!
在Redis开发手册中,有序集合支持的操作有
- 插入一个数据
- 删除一个数据
- 查找一个数据
- 迭代输出有序序列
- 按照区间查找数据
前面可以用其他数据结构完成----比如红黑树,但是最后一个显然用跳表去定位起点(然后逐条输出)更好实现!再者跳表的代码虽然很难但是比起红黑树相对起来要好实现。
但是。。。。。。。红黑树有现成的实现,直接拿来用,而跳表却需要自己实现。。。。。。。
四、简单的跳表实现代码
代码由王争老师完成
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 | package skiplist; import java.util.Random; /** * 跳表的一种实现方法。 * 跳表中存储的是正整数,并且存储的是不重复的。 * * Author:ZHENG */ public class SkipList { private static final int MAX_LEVEL = 16; private int levelCount = 1; private Node head = new Node(); // 带头链表 private Random r = new Random(); public Node find(int value) { Node p = head; for (int i = levelCount - 1; i >= 0; --i) { while (p.forwards[i] != null && p.forwards[i].data < value) { p = p.forwards[i]; } } if (p.forwards[0] != null && p.forwards[0].data == value) { return p.forwards[0]; } else { return null; } } public void insert(int value) { int level = randomLevel(); Node newNode = new Node(); newNode.data = value; newNode.maxLevel = level; Node update[] = new Node[level]; for (int i = 0; i < level; ++i) { update[i] = head; } // record every level largest value which smaller than insert value in update[] Node p = head; for (int i = level - 1; i >= 0; --i) { while (p.forwards[i] != null && p.forwards[i].data < value) { p = p.forwards[i]; } update[i] = p;// use update save node in search path } // in search path node next node become new node forwords(next)for (int i = 0; i < level; ++i) { newNode.forwards[i] = update[i].forwards[i]; update[i].forwards[i] = newNode; } // update node hightif (levelCount < level) levelCount = level; } public void delete(int value) { Node[] update = new Node[levelCount]; Node p = head; for (int i = levelCount - 1; i >= 0; --i) { while (p.forwards[i] != null && p.forwards[i].data < value) { p = p.forwards[i]; } update[i] = p; } if (p.forwards[0] != null && p.forwards[0].data == value) { for (int i = levelCount - 1; i >= 0; --i) { if (update[i].forwards[i] != null && update[i].forwards[i].data == value) { update[i].forwards[i] = update[i].forwards[i].forwards[i]; } } } } // 随机 level 次,如果是奇数层数 +1,防止伪随机private int randomLevel() { int level = 1; for (int i = 1; i < MAX_LEVEL; ++i) { if (r.nextInt() % 2 == 1) { level++; } } return level; } public void printAll() { Node p = head; while (p.forwards[0] != null) { System.out.print(p.forwards[0] + " "); p = p.forwards[0]; } System.out.println(); } public class Node { private int data = -1; private Node forwards[] = new Node[MAX_LEVEL]; private int maxLevel = 0; @Override public String toString() { StringBuilder builder = new StringBuilder(); builder.append("{ data: "); builder.append(data); builder.append("; levels: "); builder.append(maxLevel); builder.append(" }"); return builder.toString(); } } } |
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
团队管理
一、项目流程 流程 时间点 需求池优先级 无 产品评审 时间点 用例评审 时间点 UI评审 时间点 数据库、架构评审 时间点 排期 时间点 开发 时间点 整包提测 时间点 产品、UI确认功能 时间点 性能压测 时间点 第一轮测试 时间点 第二轮测试 时间点 产品发布 时间点 上线 时间点 复盘 时间点 二、中间穿插每周一次团队分享 人员 分享内容 时间点 产品 分享内容 时间点 前端 分享内容 时间点 后端 分享内容 时间点 安卓/IOS 分享内容 时间点 运营 分享内容 时间点 UE 分享内容 时间点 三、git分支管理 分支 来源 上线合并 说明 master 无 无 主分支 develop master master 平时开发后合并的分支 release master master 和本版本的功能bug无关的功能开发,有可能需要稍后时间在上线,但是这中间可能会有hotfix feature develop develop 平时本地开发分支 hotfix master developmasterrelease 紧急修复线上问题 feature release developmast...
- 下一篇
RocketMQ 学习之路 | 第一章 :RocketMQ 的安装与配置
一:RocketMQ 简介 RocketMQ 是一款分布式、队列模型的消息中间件,具有以下特点: 能够保证严格的消息顺序。 提供丰富的消息拉取模式。 高效的订阅者水平扩展能力。 实时的消息订阅机制。 亿级消息堆积能力。 二:RocketMQ的安装1.下载RocketMQ源码 下载地址 rocketmq-4.4.0 2.解压 , 进入解压目录 unzip rocketmq-all-4.2.0-source-release.zip cd rocketmq-all-4.4.0 3.执行安装命令 mvn -Prelease-all -DskipTests clean install -U 4.安装完成后进入启动文件所在目录 cd distribution/target/apache-rocketmq 5.启动服务器, 查看启动日志 nohup sh bin/mqnamesrv & tail -f ~/logs/rocketmqlogs/namesrv.log 6.启动broker , 查看broker启动日志 nohup sh bin/mqbroker -n localhost:987...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- 设置Eclipse缩进为4个空格,增强代码规范
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- Red5直播服务器,属于Java语言的直播服务器
- Eclipse初始化配置,告别卡顿、闪退、编译时间过长
- CentOS7,8上快速安装Gitea,搭建Git服务器
- CentOS8安装Docker,最新的服务器搭配容器使用
- MySQL8.0.19开启GTID主从同步CentOS8
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- Hadoop3单机部署,实现最简伪集群