您当前的位置:首页 > 电脑百科 > 数据库 > MYSQL

聊聊Mysql索引和redis跳表

时间:2021-02-05 10:48:31  来源:  作者:

聊聊MySQL索引和redis跳表 ---redis的有序集合zset数据结构底层采用了跳表原理 时间复杂度O(logn)(阿里)

redis使用跳表不用B+数的原因是:redis是内存数据库,而B+树纯粹是为了mysql这种IO数据库准备的。B+树的每个节点的数量都是一个mysql分区页的大小(阿里面试)

敲黑板:

每级遍历 3 个结点即可,而跳表的高度为 h ,所以每次查找一个结点时,需要遍历的结点数为 3*跳表高度 ,所以忽略低阶项和系数后的时间复杂度就是 ○(㏒n),空间复杂度是O(n)

聊聊Mysql索引和redis跳表

 

问题

如果对以下问题感到困惑或一知半解,请继续看下去,相信本文一定会对你有帮助

  • mysql 索引如何实现
  • mysql 索引结构B+树与hash有何区别。分别适用于什么场景
  • 数据库的索引还能有其他实现吗
  • redis跳表是如何实现的
  • 跳表和B+树,LSM树有何区别呢

解析

首先为什么要把mysql索引和redis跳表放在一起讨论呢,因为他们解决的都是同一种问题,用于解决数据集合的查找问题,即根据指定的key,快速查到它所在的位置(或者对应的value)

当你站在这个角度去思考问题时,还会不知道B+树索引和hash索引的区别吗

数据集合的查找问题

现在我们将问题领域边界划分清楚了,就是为了解决数据集合的查找问题。这一块需要考虑哪些问题呢

  1. 需要支持哪些查找方式,单key/多key/范围查找,
  2. 插入/删除效率
  3. 查找效率(即时间复杂度)
  4. 存储大小(空间复杂度)

我们看下几种常用的查找结构

hash

聊聊Mysql索引和redis跳表

 

hash是key,value形式,通过一个散列函数,能够根据key快速找到value

B+ 树:

注意 这是关于B+树的总结,如果你掌握到这个程度 是远远不够的,

B+树 的数据都在叶子节点,非叶子节点存放 索引

聊聊Mysql索引和redis跳表

 

B+树是在平衡二叉树基础上演变过来,为什么我们在算法课上没学到B+树和跳表这种结构呢。因为他们都是从工程实践中得到,在理论的基础上进行了妥协。

B+树首先是有序结构,为了不至于树的高度太高,影响查找效率,在叶子节点上存储的不是单个数据,而是一页数据,提高了查找效率,而为了更好的支持范围查询,B+树在叶子节点冗余了非叶子节点数据,为了支持翻页,叶子节点之间通过指针连接。

跳表

redis跳表视频讲解点击链接:「链接」

C/C++linux服务器开发精彩内容包括:C/C++,Linux,Nginx,ZeroMQ,MySQL,Redis,MongoDB,ZK,流媒体,P2P,Linux内核,Docker,TCP/IP,协程,DPDK多个高级知识点学习视频资料点击:C/C++Linux服务器开发/后台架构师【零声学院】-学习视频教程-腾讯课堂

C/C++Linux后台服务器开发技术交流qun:正在跳转

聊聊Mysql索引和redis跳表

 

跳表:为什么 Redis 一定要用跳表来实现有序集合?

上几篇主要是学习二分查找算法,但是二分查找底层依赖的是数组随机访问的特性,所以只能用数组来实现。如果数据存储在链表中,就没办法使用二分查找了吗?

此时跳表出现了,跳表(Skip list) 实际上就是在链表的基础上改造生成的。

跳表是一种各方面性能都比较优秀的 动态数据结构,可以支持快速的插入、删除、查找操作,写起来也不复杂,甚至可以替代 红黑树??。

Redis 一共有5种数据结构,包括:

1、字符串(String)
redis对于KV的操作效率很高,可以直接用作计数器。例如,统计在线人数等等,另外string类型是二进制存储安全的,所以也可以使用它来存储图片,甚至是视频等。

2、哈希(hash)
存放键值对,一般可以用来存某个对象的基本属性信息,例如,用户信息,商品信息等,另外,由于hash的大小在小于配置的大小的时候使用的是ziplist结构,比较节约内存,所以针对大量的数据存储可以考虑使用hash来分段存储来达到压缩数据量,节约内存的目的,例如,对于大批量的商品对应的图片地址名称。比如:商品编码固定是10位,可以选取前7位作为hash的key,后三位作为field,图片地址作为value。这样每个hash表都不超过999个,只要把redis.conf中的hash-max-ziplist-entries改为1024,即可。
3、列表(List)
列表类型,可以用于实现消息队列,也可以使用它提供的range命令,做分页查询功能。

4、集合(Set)
集合,整数的有序列表可以直接使用set。可以用作某些去重功能,例如用户名不能重复等,另外,还可以对集合进行交集,并集操作,来查找某些元素的共同点

5、有序集合(zset)
有序集合,可以使用范围查找,排行榜功能或者topN功能。

其中第五个zset 有序集合 就是用跳表来实现的。那 Redis 为什么会选择用跳表来实现有序集合呢?

一、如何理解跳表?

对于单链表来说,我们查找某个数据,只能从头到尾遍历链表,此时时间复杂度是 ○(n)。

聊聊Mysql索引和redis跳表

 

那么怎么提高单链表的查找效率呢?看下图,对链表建立一级 索引,每两个节点提取一个结点到上一级,被抽出来的这级叫做 索引 或 索引层。

聊聊Mysql索引和redis跳表

 

开发中经常会用到一种处理方式,hashmap 中存储的值类型是一个 list,这里就可以把索引当做 hashmap 中的键,将每 2 个结点看成每个键对应的值 list。

所以要找到13,就不需要将16前的结点全遍历一遍,只需要遍历索引,找到13,然后发现下一个结点是17,那么16一定是在 [13,17] 之间的,此时在13位置下降到原始链表层,找到16,加上一层索引后,查找一个结点需要遍历的结点个数减少了,也就是说查找效率提高了

那么我们再加一级索引呢?
跟前面建立一级索引的方式相似,我们在第一级索引的基础上,每两个结点就抽出一个结点到第二级索引。此时再查找16,只需要遍历 6 个结点了,需要遍历的结点数量又减少了。

聊聊Mysql索引和redis跳表

 

当结点数量多的时候,这种添加索引的方式,会使查询效率提高的非常明显

聊聊Mysql索引和redis跳表

 

二、用跳表查询到底有多快

在一个单链表中,查询某个数据的时间复杂度是 ○(n),那在一个具有多级索引的跳表中,查询某个数据的时间复杂度是多少呢?

按照上面的示例,每两个节点就抽出一个一级索引,每两个一级索引又抽出一个二级索引,所以第一级索引的结点个数大约就是 n/2,第二级索引的结点个数就是 n/4,第 k 级索引的结点个数就是 n/2^k。

假设一共建立了 h 级索引,最高级的索引有两个节点(如果最高级索引只有一个结点,那么这一级索引起不到判断区间的作用,那么是没什么意义的),所以有:

聊聊Mysql索引和redis跳表

时间复杂度的分析


聊聊Mysql索引和redis跳表

 

根据上图得知,每级遍历 3 个结点即可,而跳表的高度为 h ,所以每次查找一个结点时,需要遍历的结点数为 3*跳表高度 ,所以忽略低阶项和系数后的时间复杂度就是 ○(㏒n)

其实此时就相当于基于单链表实现了二分查找。但是这种查询效率的提升,由于建立了很多级索引,会不会很浪费内存呢?

三、跳表是不是很浪费内存?

来分析一下跳表的空间复杂度。 为O(n)

聊聊Mysql索引和redis跳表

 


聊聊Mysql索引和redis跳表

空间复杂度

所以如果将包含 n 个结点的单链表构造成跳表,我们需要额外再用接近 n 个结点的存储空间,那怎么才能降低索引占用的内存空间呢?

前面是每两个结点抽一个结点到上级索引,如果我们每三个,或每五个结点,抽一个结点到上级索引,是不是就不用那么多索引结点了呢?

聊聊Mysql索引和redis跳表

 

计算空间复杂度的过程与前面的一致,尽管最后空间复杂度依然是 ○(n),但我们知道,使用大○表示法忽略的低阶项或系数,实际上同样会产生影响,只不过我们为了关注高阶项而将它们忽略。

聊聊Mysql索引和redis跳表

空间复杂度

实际上,在实际开发中,我们不需要太在意索引占据的额外空间,在学习数据结构与算法时,我们习惯的将待处理数据看成整数,但是实际开发中,原始链表中存储的很可能是很大的对象,而索引结点只需要存储关键值(用来比较的值)和几个指针(找到下级索引的指针),并不需要存储原始链表中完整的对象,所以当对象比索引结点大很多时,那索引占用的额外空间就可以忽略了。

四、高效的动态插入和删除

跳表这个动态数据结构,不仅支持查找操作,还支持动态的插入、删除操作,而且插入、删除操作的时间复杂度也是 ○(㏒n)。

对于单纯的单链表,需要遍历每个结点来找到插入的位置。但是对于跳表来说,因为其查找某个结点的时间复杂度是 ○(㏒n),所以这里查找某个数据应该插入的位置,时间复杂度也是 ○(㏒n)。

聊聊Mysql索引和redis跳表

 

那么删除操作呢?

聊聊Mysql索引和redis跳表

 

五、跳表索引动态更新

当我们不停的往跳表中插入数据时,如果我们不更新索引,就可能出现某 2 个索引结点之间数据非常多的情况。极端情况下,跳表会退化成单链表。

聊聊Mysql索引和redis跳表

 

作为一种动态数据结构,我们需要某种手段来维护索引与原始链表大小之间的平滑,也就是说如果链表中结点多了,索引结点就相应地增加一些,避免复杂度退化,以及查找、插入、删除操作性能下降。

跳表是通过随机函数来维护前面提到的 平衡性。

我们往跳表中插入数据的时候,可以选择同时将这个数据插入到第几级索引中,比如随机函数生成了值 K,那我们就将这个结点添加到第一级到第 K 级这 K 级索引中。

聊聊Mysql索引和redis跳表

 

随机函数可以保证跳表的索引大小和数据大小的平衡性,不至于性能过度退化。

跳表的实现有点复杂,并且跳表的实现并不是这篇的重点。主要是学习思路。

六、解答开篇

Redis 中的有序集合是通过跳表来实现的,严格点讲,还用到了散列表,如果查看 Redis 开发手册,会发现 Redis 中的有序集合支持的核心操作主要有下面这几个:

  • 插入一个数据
  • 删除一个数据
  • 查找一个数据
  • 按照区间查找数据(比如查找在[100,356]之间的数据)
  • 迭代输出有序序列

其中,插入、查找、删除以及迭代输出有序序列这几个操作,红黑树也能完成,时间复杂度和跳表是一样的,但是,按照区间来查找数据这个操作,红黑树的效率没有跳表高。

对于按照区间查找数据这个操作,跳表可以做到 ○(㏒n) 的时间复杂度定位区间的起点,然后在原始链表中顺序往后遍历就可以了。这样做非常高效。

当然,还有其他原因,比如,跳表代码更容易实现,可读性好不易出错。跳表更加灵活,可以通过改变索引构建策略,有效平衡执行效率和内存消耗。

不过跳表也不能完全替代红黑树。因为红黑树出现的更早一些。很多编程语言中的 Map 类型都是用红黑树来实现的。写业务的时候直接用就行,但是跳表没有现成的实现,开发中想用跳表,得自己实现。



Tags:Mysql   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
作者:雷文霆 爱可生华东交付服务部 DBA 成员,主要负责Mysql故障处理及相关技术支持。爱好看书,电影。座右铭,每一个不曾起舞的日子,都是对生命的辜负。 本文来源:原创投稿 *爱可生...【详细内容】
2021-12-24  Tags: Mysql  点击:(6)  评论:(0)  加入收藏
一、为什么要搭建主从架构呢1.数据安全,可以进行数据的备份。2.读写分离,大部分的业务系统来说都是读数据多,写数据少,当访问压力过大时,可以把读请求给到从服务器。从而缓解数据...【详细内容】
2021-12-15  Tags: Mysql  点击:(10)  评论:(0)  加入收藏
生成间隙(gap)锁、临键(next-key)锁的前提条件 是在 RR 隔离级别下。有关Mysql记录锁、间隙(gap)锁、临键锁(next-key)锁的一些理论知识之前有写过,详细内容可以看这篇文章...【详细内容】
2021-12-14  Tags: Mysql  点击:(17)  评论:(0)  加入收藏
binlog 基本认识 MySQL的二进制日志可以说是MySQL最重要的日志了,它记录了所有的DDL和DML(除了数据查询语句)语句,以事件形式记录,还包含语句所执行的消耗的时间,MySQL的二...【详细内容】
2021-12-14  Tags: Mysql  点击:(13)  评论:(0)  加入收藏
为查询优化你的查询 大多数的MySQL服务器都开启了查询缓存。这是提高性最有效的方法之一,而且这是被MySQL的数据库引擎处理的。当有很多相同的查询被执行了多次的时候,这些查...【详细内容】
2021-12-09  Tags: Mysql  点击:(15)  评论:(0)  加入收藏
测试的目的和原因,公司有很多程序员,每个程序员对数据库和表结构都有自己的理解。而且每个程序员的理解往往是以效率考虑。既然都是为了效率考虑,那么我就来测试一下究竟哪种使...【详细内容】
2021-12-08  Tags: Mysql  点击:(14)  评论:(0)  加入收藏
当你们考虑项目并发的时候,我在部署环境,当你们在纠结使用ArrayList还是LinkedArrayList的时候,我还是在部署环境。所以啊,技术不止境,我在部环境。今天这篇文章缕一下在同一台服...【详细内容】
2021-12-08  Tags: Mysql  点击:(16)  评论:(0)  加入收藏
对于数据分析来说,MySQL使用最多的是查询,比如对数据进行排序、分组、去重、汇总及字符串匹配等,如果查询的数据涉及多个表,还需要要对表进行连接,本文就来说说MySQL中常用的查询...【详细内容】
2021-12-06  Tags: Mysql  点击:(19)  评论:(0)  加入收藏
在学习SQL语句之前,首先需要区分几个概念,我们常说的数据库是指数据库软件,例如MySQL、Oracle、SQL Server等,而本文提到的数据库是指数据库软件中的一个个用于存储数据的容器。...【详细内容】
2021-11-24  Tags: Mysql  点击:(23)  评论:(0)  加入收藏
概述以前参加过一个库存系统,由于其业务复杂性,搞了很多个应用来支撑。这样的话一份库存数据就有可能同时有多个应用来修改库存数据。比如说,有定时任务域xx.cron,和SystemA域...【详细内容】
2021-11-05  Tags: Mysql  点击:(31)  评论:(0)  加入收藏
▌简易百科推荐
作者:雷文霆 爱可生华东交付服务部 DBA 成员,主要负责Mysql故障处理及相关技术支持。爱好看书,电影。座右铭,每一个不曾起舞的日子,都是对生命的辜负。 本文来源:原创投稿 *爱可生...【详细内容】
2021-12-24  爱可生    Tags:MySQL   点击:(6)  评论:(0)  加入收藏
生成间隙(gap)锁、临键(next-key)锁的前提条件 是在 RR 隔离级别下。有关Mysql记录锁、间隙(gap)锁、临键锁(next-key)锁的一些理论知识之前有写过,详细内容可以看这篇文章...【详细内容】
2021-12-14  python数据分析    Tags:MySQL记录锁   点击:(17)  评论:(0)  加入收藏
binlog 基本认识 MySQL的二进制日志可以说是MySQL最重要的日志了,它记录了所有的DDL和DML(除了数据查询语句)语句,以事件形式记录,还包含语句所执行的消耗的时间,MySQL的二...【详细内容】
2021-12-14  linux上的码农    Tags:mysql   点击:(13)  评论:(0)  加入收藏
为查询优化你的查询 大多数的MySQL服务器都开启了查询缓存。这是提高性最有效的方法之一,而且这是被MySQL的数据库引擎处理的。当有很多相同的查询被执行了多次的时候,这些查...【详细内容】
2021-12-09  元宇宙iwemeta    Tags:mysql   点击:(15)  评论:(0)  加入收藏
测试的目的和原因,公司有很多程序员,每个程序员对数据库和表结构都有自己的理解。而且每个程序员的理解往往是以效率考虑。既然都是为了效率考虑,那么我就来测试一下究竟哪种使...【详细内容】
2021-12-08  吴彬的分享    Tags:Mysql数据库   点击:(14)  评论:(0)  加入收藏
当你们考虑项目并发的时候,我在部署环境,当你们在纠结使用ArrayList还是LinkedArrayList的时候,我还是在部署环境。所以啊,技术不止境,我在部环境。今天这篇文章缕一下在同一台服...【详细内容】
2021-12-08  秃头码哥    Tags:MySQL数据库   点击:(16)  评论:(0)  加入收藏
对于数据分析来说,MySQL使用最多的是查询,比如对数据进行排序、分组、去重、汇总及字符串匹配等,如果查询的数据涉及多个表,还需要要对表进行连接,本文就来说说MySQL中常用的查询...【详细内容】
2021-12-06  笨鸟学数据分析    Tags:MySQL   点击:(19)  评论:(0)  加入收藏
在学习SQL语句之前,首先需要区分几个概念,我们常说的数据库是指数据库软件,例如MySQL、Oracle、SQL Server等,而本文提到的数据库是指数据库软件中的一个个用于存储数据的容器。...【详细内容】
2021-11-24  笨鸟学数据分析    Tags:SQL语句   点击:(23)  评论:(0)  加入收藏
概述以前参加过一个库存系统,由于其业务复杂性,搞了很多个应用来支撑。这样的话一份库存数据就有可能同时有多个应用来修改库存数据。比如说,有定时任务域xx.cron,和SystemA域...【详细内容】
2021-11-05  Java云海    Tags:分布式锁   点击:(31)  评论:(0)  加入收藏
MySQL的进阶查询 一、 按关键字排序 使用ORDERBY语句来实现排序排序可针对一个或多个字段ASC:升序,默认排序方式 【升序是从小到大】DESC:降序 【降序是从大到小】ORDER BY的...【详细内容】
2021-11-05  Java热点    Tags:SQL语句   点击:(27)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条