三高Mysql - Inndb存储引擎和索引介绍(上)

本文涉及的产品
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
云数据库 RDS PostgreSQL,高可用系列 2核4GB
云数据库 RDS MySQL,高可用系列 2核4GB
简介: 三高Mysql - Inndb存储引擎和索引介绍(上)

引言


内容为慕课网的《高并发 高性能 高可用 MySQL 实战》视频的学习笔记内容和个人整理扩展之后的笔记,这一节的内容是对于InnoDb的存储结构进阶了解,同时介绍为什么会使用B+索引作为最终数据结构,但是实际上InnoDb在具体实现中也并没有完全遵循B+的格式,而是在内部做了很多“手脚”,这也是所谓理论和实践之间的差异。

如果内容比较难,可以跟随《Mysql是怎么样运行》个人读书笔记专栏补补课,个人也在学习和同步更新中。

地址如下:juejin.cn/column/7024…


索引组织表



InnoDb 的所有表都是索引组织表,索引组织表有如下的定义:

不是一种“组织表”,而是由“索引”组织的表,索引即数据数据即索引,InnoDb中表默认都会主键顺序存放,同时按照一定的规则排序,默认的索引组织形式被称为聚簇索引。

什么是索引?

索引可以简单理解为目录,类似于我们书中的目录页,帮我们快速定位具体的内容,对于数据库某一列或者多列进行预排序的数据结构,注意这是一种数据结构目的是为了加快数组的搜索速度。

但是索引也有问题,那就是目录本身也需要占用存储空间并且随着数据的膨胀而膨胀,同时如果索引使用的不恰当也会出现问题,比如如果我们的目录索引的内容全都是一模一样的会出现“索引失效”问题,此时索引效果大打折扣,不如直接搜索数据。

主键定义和主键索引

在Mysql的Inndb存储引擎中,使用的主键索引也被称为聚簇索引:

InnoDb 的存储引擎表中每张表必须有一个主键,表中有一个非空唯一索引即为主键。如果存在多个非空唯一索引并且没有定义主键,选择第一个定义的索引,若所有条件不满足则InnoDb在数据行中自动创建一个6个字节的指针隐藏列作为主键,并且这个主键内部是自增的使得记录可以按照顺序进行存储。

下面用视频中的案例举例讨论的下面这个表主键是什么?


网络异常,图片无法展示
|


从上面的截图可以看到,字段a没有定义唯一索引,虽然它是非空的但是并不是唯一的所以不是主键,b虽然是最先定义的,但是他不是非空所以也不能作为索引,而d和 c虽然都是唯一索引并且都是非空列,根据多个非空索引取第一个定义索引为主键的规则,最终主键为字段d。


B+树索引


B+树的索引结构是InnoDb的基础结构,下面是传统的B+树的结构:

  • Btree 使用B+树作为索引的数据结构。
  • B+树的高度为2-4层,查找数据十分快。
  • B+树索引将非叶子节点所谓索引节点,叶子节点为数据节点,数据节点之间用链表串联实现优化范围查询。

Inndo的B+树和传统B+树的区别如下:

  1. InnoDb底层参考的是b+ 树,但是其实不完全相同,节点被称之为数据页和索引页,但是实际上索引页数据页除了数据类型不同基本一致,也就是索引即数据,数据即索引,索引它分为聚簇索引和辅助索引,聚簇索引最大特点是存放键是主键ID,而主键ID根据一定的规则生成或者在建表的时候指定,但是一定会有一个主键索引,也就说一个表一定存在主键。而辅助索引使用的是主键为索引字段的值,数值存放的是索引主键。
  2. 同层的数据页之间使用的是双向链表,索引页也是使用双向链表,这和B+树的数据结构是不一样的,传统B+ 树只在最底层的叶子节点为链表的设计。


聚簇索引



聚簇索引指的是根据表的主键构建一个B+ 树。叶子节点直接存放行数据而不是放指针,但是实际上叶子节点本身也是数据页只不过存放的是指针而已。

下面的案例图仅仅为最粗糙的角度观察mysql的数据页设计,实际内容要远比这张图复杂很多:


网络异常,图片无法展示
|


聚簇索引的特点


  • 非叶子节点存储的是索引,叶子节点则为数据,从左到右排序,在页分裂的时候,会把主键较大的值移动到对应的数据页。
  • 索引页之间使用链表进行连接,而叶子节点实际的数据存储区域,统一使用链条表进行串联。所以可以发现除开最顶层,所有的层级页和页之间是由链表之间链接的。
  • 每一个数据页包含infimum数据行代表当前数据页的第一个节点也就是最小值,supermum代表最后一个节点也就是最大值,这两个“行记录”是Mysql设计者的一个小把戏,目的是方便数据的查找和不同数据页之间的串联,也就是说每一个数据页默认至少有两个“虚拟”数据行。
  • 所有的数据页号会组成一个页目录,按照最大数据的数据页号进行排序,页目录里面从小到大存放了主键的id值,通过值找到对应的数据页内容,用于快速定位数据所在的数据页。
  • Innodb 默认为主键索引也就是聚簇索引。


为什么要使用从大到小的顺序进行排序?

其实主要是为了使用二分查找方法快速定位和查找数据页,提高查找的效率。注意由于早期Mysql版本中的索引设计只能按照升序的方式进行排列,导致聚簇索引多数为升序的索引,在8.0的版本中得到优化。


辅助索引


辅助索引的存在形式:

  1. 和主键索引的设计一样,但是key存放的是索引字段的值,值是主键值
  2. 辅助索引根据建立的索引除联合索引的情况外均为有几个索引建立几颗B+ 树。
  3. 辅助索引相当于一颗新的B+ 树。

主键索引:

  1. 主键索引也叫聚簇索引,由于底层使用了B+ 树的设计结构,所以Mysql必定有主键并且以主键作为索引的形式。
  2. 主键索引指的是键为主键,值为数据一种 索引形式。
  3. 一旦创建表则系统默认会存在一颗以主键索引的B+ 树。


回表是什么?


当辅助索引进行查询的时候由于查询的结果为主键的值,所以需要根据主键的值再去聚簇索引根据二分法查找一遍,这时候等于需要再查一遍聚簇索引,本质上是查了两次B+ 树,所以叫回表。

下面的示意图是一次回表操作:

假设我们需要搜索值为5的数据,首先会在二级索引通过二分遍历“槽”的形式找到具体所在的数据行,这个数据行保存索引值之外还存储了主键的值,所以这里需要拿到主键的值回到聚簇索引中找到实际存储的行记录。


但是如果查找条件和查找列都为索引值实际上会使用“覆盖索引”的查找方式,不需要回表操作。


网络异常,图片无法展示
|


索引算法



对于刚刚接触B+树的同学看到这些数据结构可能会懵圈,同时也不清楚为什么要设计这么个复杂的玩意,所以在课程中引入了各种数据结构来介绍为什么最终选择了B+树的结构,下面我们来简单对比各种常见的数据结构来了解为什么最后选择了B+ 树这种数据结构。


对于一些常见的算法可以阅读下面的网站了解:Data Structure Visualization (usfca.edu)


哈希表


www.cs.usfca.edu/~galles/vis…

哈希表的数据结构十分简单,只包含简单的键值对,用哈希函数给索引列计算一个哈希值存储,哈希表最典型的索引应用类型是哈希索引,通过对于索引列的总列计算一个哈希函数进行存储。

哈希表缺点:

哈希表最大的问题在于key冲突,因为如果存在key冲突,那么此时索引会退化为顺序的全表遍历,或者说拉出一个链表存储冲突哈希key进行遍历,并且哈希索引最为适用的等值查询实际在使用过程中并不是十分频繁,更多的时候会使用范围或者模糊搜索,这时候哈希表的数据结构是很难发挥作用的。

  • 哈希表不适用于范围查找和模糊搜索。
  • 哈希冲突会退化为顺序遍历查询。


网络异常,图片无法展示
|


线性结构


线性结构指的是经典数组,包括链表,数组和堆栈结构,比如数组的查询效率是O(n),并且查找的性能是O(1),看起来是对于设计数据库比较合适。

特点:

  1. 时间复杂度O(n)
  2. 需要从第一个开始做一次遍历线性查找,查找的效率是O(1)
  3. 数组的特点是查找快,更新慢,而链表的特点是更新快,查找稍慢。

不适合作为数据库的缺点:

对于任意的线性结构来说的查找,更新,删除的速度似乎很不错,但是顺序数组的插入速度不能接受,尤其是在数组中间插入的时候,需要拷贝数组向后挪位置,而链条的查找速度不能接受并且不利于磁盘存储,如果数据量很大的情况下开销庞大,显然都是不适合的。

二分查找:二分查找对于线性数组结构来说是非常常用的方式,有序数组在等值查询和范围查询场景中的性能就都非常优秀。

二分查找演示图:www.cs.usfca.edu/~galles/vis…


网络异常,图片无法展示
|


  1. 时间复杂度(O(logn)),每一次查找都是上一次的一半。
  2. 使用数组的中点作为比较对象。
  3. 根据中点数据大小,选择一半数据作为新数列查找。
  4. 每次可以查找的数据量为一半。

不足点:二分查找虽然在查询上提升一个量级,但是依然没有避免插入的问题。


二叉树


既然线性结构有限制,那么逻辑结构是否可行?所以我们可以思考如果用二叉树如何处理。

  1. 时间复杂度是O(logN)。
  2. 搜索效率的速度取决于树的高度。
  3. 遍历方式,分为前序遍历,中序遍历,后序遍历。
  4. 如果所有的节点往一侧添加,可能退化为线性查找。

不适合作为数据库的缺点:

插入和删除需要耗费一定的性能,并且为了节点的稳定,需要使用左旋或者右旋的操作,维持二叉树的平衡,所以后续拓展出平衡二叉树和红黑树。


网络异常,图片无法展示
|


平衡二叉树和红黑树


平衡二叉树针对二叉树引入左旋和右旋的操作维持平衡,平衡二叉树的定义是:左右两个子树的高度差不能超过 1,左右两边相对平衡,因此称之为平衡二叉树。而红黑树s

  1. AVL 树,通过左旋和右旋的操作将节点进行上浮或者下沉。
  2. AVL树保证不会退化为线性查找。

不适合作为数据库的缺点:

1. 虽然可以保证查询的性能不会退化,但是对于树的左旋和右旋的操作十分耗费性能,在存储数据的时候会出现长时间等待的情况,同时还是会发现这样存储的效率是十分低的,同时磁盘的利用率十分低。

2. 另外从数据结构图发现还有一个十分明显的缺点,那就是一个节点只能有两个子节点,如果插入大量节点会导致树的高度不断膨胀,即使可以平衡操作,对于插入的操作而言还是十分耗费性能的。


B 树


数据结构演示图:www.cs.usfca.edu/~galles/vis…

既然二叉树只有两个节点,那么我们调整结构,让每一层的节点内容增多,并让树控制在2-4层。同时可以包含多个子节点,这样即可极大提高存储效率,同时这种紧凑的结构也方便磁盘的顺序扫描。

  1. 线性数据结构和树结构的结合。
  2. 通过多数据节点大大降低树的高度。
  3. 不需要旋转就可以保证树的平衡

缺点:

但是很可惜B树有一个十分致命的缺陷,那就是不适合作为范围查找,如果我们想跨越多个范围进行查询,那么需要从根节点遍历一整颗树多次,我们知道范围查询的常见是非常常见的,这样的性能开销对于数据库来说显然不实际。


网络异常,图片无法展示
|


B+树


数据结构演示图:www.cs.usfca.edu/~galles/vis…

B+树是对于B 树的一种优化和变种,其实可以发现就是在线性结构和逻辑结构的兼容,最终在B树的基础上,所有的数据存在叶子节点,而索引节点放在非叶子节点,最终这样的接口。

特点:

  1. B+树是B树发展过来的一种数据结构
  2. B+树所有数据都在叶子节点。
  3. B+树所有数据最终形成了一个线性表。


网络异常,图片无法展示
|

相关实践学习
每个IT人都想学的“Web应用上云经典架构”实战
本实验从Web应用上云这个最基本的、最普遍的需求出发,帮助IT从业者们通过“阿里云Web应用上云解决方案”,了解一个企业级Web应用上云的常见架构,了解如何构建一个高可用、可扩展的企业级应用架构。
MySQL数据库入门学习
本课程通过最流行的开源数据库MySQL带你了解数据库的世界。   相关的阿里云产品:云数据库RDS MySQL 版 阿里云关系型数据库RDS(Relational Database Service)是一种稳定可靠、可弹性伸缩的在线数据库服务,提供容灾、备份、恢复、迁移等方面的全套解决方案,彻底解决数据库运维的烦恼。 了解产品详情: https://www.aliyun.com/product/rds/mysql 
相关文章
|
2月前
|
存储 SQL 关系型数据库
mysql底层原理:索引、慢查询、 sql优化、事务、隔离级别、MVCC、redolog、undolog(图解+秒懂+史上最全)
mysql底层原理:索引、慢查询、 sql优化、事务、隔离级别、MVCC、redolog、undolog(图解+秒懂+史上最全)
mysql底层原理:索引、慢查询、 sql优化、事务、隔离级别、MVCC、redolog、undolog(图解+秒懂+史上最全)
|
2月前
|
存储 关系型数据库 MySQL
MySQL数据库索引的数据结构?
MySQL中默认使用B+tree索引,它是一种多路平衡搜索树,具有树高较低、检索速度快的特点。所有数据存储在叶子节点,非叶子节点仅作索引,且叶子节点形成双向链表,便于区间查询。
92 4
|
4月前
|
存储 关系型数据库 MySQL
阿里面试:MySQL 一个表最多 加几个索引? 6个?64个?还是多少?
阿里面试:MySQL 一个表最多 加几个索引? 6个?64个?还是多少?
阿里面试:MySQL 一个表最多 加几个索引? 6个?64个?还是多少?
|
2月前
|
存储 SQL 关系型数据库
MySQL 核心知识与索引优化全解析
本文系统梳理了 MySQL 的核心知识与索引优化策略。在基础概念部分,阐述了 char 与 varchar 在存储方式和性能上的差异,以及事务的 ACID 特性、并发事务问题及对应的隔离级别(MySQL 默认 REPEATABLE READ)。 索引基础部分,详解了 InnoDB 默认的 B+tree 索引结构(多路平衡树、叶子节点存数据、双向链表支持区间查询),区分了聚簇索引(数据与索引共存,唯一)和二级索引(数据与索引分离,多个),解释了回表查询的概念及优化方法,并分析了 B+tree 作为索引结构的优势(树高低、效率稳、支持区间查询)。 索引优化部分,列出了索引创建的六大原则
|
3月前
|
存储 关系型数据库 MySQL
MySQL覆盖索引解释
总之,覆盖索引就像是图书馆中那些使得搜索变得极为迅速和简单的工具,一旦正确使用,就会让你的数据库查询飞快而轻便。让数据检索就像是读者在图书目录中以最快速度找到所需信息一样简便。这样的效率和速度,让覆盖索引成为数据库优化师傅们手中的尚方宝剑,既能够提升性能,又能够保持系统的整洁高效。
112 9
|
4月前
|
机器学习/深度学习 关系型数据库 MySQL
对比MySQL全文索引与常规索引的互异性
现在,你或许明白了这两种索引的差异,但任何技术决策都不应仅仅基于理论之上。你可以创建你的数据库实验环境,尝试不同类型的索引,看看它们如何影响性能,感受它们真实的力量。只有这样,你才能熟悉它们,掌握什么时候使用全文索引,什么时候使用常规索引,以适应复杂多变的业务需求。
103 12
|
4月前
|
存储 SQL 关系型数据库
MySQL存储引擎简介
在选择相应的存储引擎时,需要充分考虑实际业务场景、性能需求和数据一致性要求,从而为数据管理提供最佳支持。
292 17
|
21天前
|
安全 关系型数据库 MySQL
MySQL安全最佳实践:保护你的数据库
本文深入探讨了MySQL数据库的安全防护体系,涵盖认证安全、访问控制、网络安全、数据加密、审计监控、备份恢复、操作系统安全、应急响应等多个方面。通过具体配置示例,为企业提供了一套全面的安全实践方案,帮助强化数据库安全,防止数据泄露和未授权访问,保障企业数据资产安全。
|
6天前
|
缓存 关系型数据库 BI
使用MYSQL Report分析数据库性能(下)
使用MYSQL Report分析数据库性能
39 3
|
12天前
|
关系型数据库 MySQL 数据库
自建数据库如何迁移至RDS MySQL实例
数据库迁移是一项复杂且耗时的工程,需考虑数据安全、完整性及业务中断影响。使用阿里云数据传输服务DTS,可快速、平滑完成迁移任务,将应用停机时间降至分钟级。您还可通过全量备份自建数据库并恢复至RDS MySQL实例,实现间接迁移上云。

推荐镜像

更多