MySQL索引的本质,MySQL索引的实现,MySQL索引的数据结构

本文涉及的产品
云数据库 RDS SQL Server,独享型 2核4GB
云数据库 RDS MySQL Serverless,0.5-2RCU 50GB
简介: MySQL索引的本质,MySQL索引的实现,MySQL索引的数据结构

一、索引的本质

索引是帮助MySQL高效获取数据的排好序数据结构

如上图所示这个表,如果没有索引的话,当我们执行查询的时候:

select * from table1 where Col2 = 23;

就会从头比较到尾,然后找到对应的,一共需要查找7次,索引很慢。

索引的作用就在这了,可以快速的帮你找到某列上要找的元素。

假设,我们为Col2建立上索引:

并假设我们的索引是一颗二叉排序树(真实的数据库底层并不是使用二叉排序树的,这里只是做一个简单的演示例子)。

可以看到这是一颗二叉排序树,时间复杂度是和二分查找差不多的。每次都可以舍掉一半的数据。

当我们再次执行:

select * from table1 where Col2 = 23;
  • 1、先跟34对比,比34小,查找34的左⬅️子树;
  • 2、跟22对比,比22大,查找22的右➡️子树;
  • 3、跟23对比,与23相等,返回这行结果。

可以看到一共查找了3次。

如果数据量很大的话,其实优势就体现出来了。

(一)为什么数据库的索引不能用二叉搜索树?

根据上面的演示,看着二叉搜索树也是可以的呀,也挺快嘛。

但是为什么用在数据库底层不合适呢?这也是面试时常问的。

我们可以演示一下:

https://www.cs.usfca.edu/~galles/visualization/BST.html

我们假设我们给Col1加上索引,那么依次对二叉搜索树插入:1、2、3、4、5、6、7;

可以看到退化成了一个链表的形式。

当我们查询7的话,时间复杂度就变成了单链表一样了。

从大到小也是:

总结如下:

  • 如果数据库底层使用二叉搜索树的话,遇到数据为极端的情况下会退化成单链表,所以不太合适;

可以想象一下,如果我们给自增的一列使用二叉搜索树的索引数据结构的话,是不是就很倒霉了。这就是极端的情况,都在一边。

(二)为什么红黑树不适合数据库索引?

红黑树又叫:二叉平衡树

红黑树作为Java开发人员应该很耳熟吧,JDK8中的HashMap中的底层数据结构就用到了红黑树。

这么牛逼的JDK中都用到了红黑树,为什么数据库中的索引数据结构不太适合呢?

还是上面那个假设,假设我们给Col1加上红黑树的索引。

过程如下动态演示:

如果我们执行:

select * from table1 where Col1 = 7;

动态演示如下:

可以看到,我们一共查询了4次就查到了。与没加这个索引之前还是有比较大的效果的,至少没有全部扫描。

总结:

通过观察可以看到,每次插入几乎都会去调整这颗二叉树,保持高度是平衡的。

如果数据量非常大的话,也是非常耗时的,所以红黑树也是不太合适。

(三)聚集索引和非聚集索引

回答这个问题之前先来看一下Mysql底层数据文件的存储方式,这里拿MyISAM和InnoDB两种引擎来做比较。

1、MyISAM引擎

如上图所示,MyISAM引擎的表,在硬盘上存储着3种文件格式,分别是“.frm”、“.MYD”、“.MYI”;

  • “.frm”:整个数据表的框架,也就表的结构。
  • “.MYD”:D是data的意思,这个文件是存储的数据。
  • “.MYI”:I是Index的意思,这个文件是存储的索引。

可以看到表的结构、数据、索引三种都分开来。这个就是非聚集的。

2、InnoDB引擎

与MyISAM引擎不同的是,InnoDB引擎在硬盘上只存储来2种文件,分别为:“.frm”、“.ibd”;

  • “.frm”:表的结构/框架;
  • “.ibd”:此文件存储着表的索引和数据;

可以看出InnoDB引擎把数据和索引同时存储在来一个文件里,这就是聚集索引。

二、MySQL中索引的实现(摘)

在MySQL中,索引是在存储引擎层实现的,不同存储引擎对索引的实现方式是不同的,下面我们探讨一下MyISAM和InnoDB两个存储引擎的索引实现方式。

(一)MyISAM索引实现:

MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址,MyISAM索引的原理图如下。

这里假设表一共有三列,假设我们以Col1为主键,则上图是一个MyISAM表的主索引(Primary key)示意。

可以看出MyISAM的索引文件仅仅保存数据记录的地址。

在MyISAM中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。

如果我们在Col2上建立一个辅助索引,则此索引的结构如下图所示。同样也是一颗B+Tree,data域保存数据记录的地址。因此,MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。

(二)InnoDB索引实现:

虽然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同。

第一个重大区别是InnoDB的数据文件本身就是索引文件。

从上文知道,MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。

而在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。

下图是InnoDB主索引(同时也是数据文件)的示意图,可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有),如果没有显式指定,则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整形。

第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说,InnoDB的所有辅助索引都引用主键作为data域。下图为定义在Col3上的一个辅助索引。这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助,例如知道了InnoDB的索引实现后,就很容易明白为什么不建议使用过长的字段作为主键,因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。再例如,用非单调的字段作为主键在InnoDB中不是个好主意,因为InnoDB数据文件本身是一颗B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择。

相关实践学习
基于CentOS快速搭建LAMP环境
本教程介绍如何搭建LAMP环境,其中LAMP分别代表Linux、Apache、MySQL和PHP。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助     相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
目录
相关文章
|
4天前
|
存储 NoSQL 关系型数据库
索引的三种常见底层数据结构以及优缺点
索引的三种常见底层数据结构以及优缺点
|
12天前
|
SQL 存储 关系型数据库
MySQL索引(二)索引优化方案有哪些
MySQL索引(二)索引优化方案有哪些
30 0
|
27天前
|
存储 关系型数据库 MySQL
MySQL - 聚簇索引和非聚簇索引
MySQL - 聚簇索引和非聚簇索引
|
27天前
|
存储 SQL 关系型数据库
MySQL - 深入解析MySQL索引数据结构
MySQL - 深入解析MySQL索引数据结构
|
1天前
|
SQL 关系型数据库 MySQL
MySQL索引与事务
MySQL索引与事务
|
2天前
|
存储 SQL 关系型数据库
【MySQL 数据库】6、一篇文章学习【索引知识】,提高大数据量的查询效率【文末送书】
【MySQL 数据库】6、一篇文章学习【索引知识】,提高大数据量的查询效率【文末送书】
42 0
|
2天前
|
监控 关系型数据库 MySQL
MySQL创建索引的注意事项
在索引的世界中,权衡是关键。权衡读写性能,权衡索引的数量和类型,权衡查询的频率和数据分布。通过谨慎的设计、定期的维护和持续的监控,我们能够确保索引在数据库中的角色得到最大的发挥,为应用提供更加高效和可靠的数据访问服务。在数据库优化的旅途中,索引是我们的得力助手,正确使用它将使数据库系统更具竞争力和可维护性。
10 0
|
3天前
|
SQL 关系型数据库 MySQL
京东三面:什么情况会导致 MySQL 索引失效?
为了验证 MySQL 中哪些情况下会导致索引失效,我们可以借助 explain 执行计划来分析索引失效的具体场景。
19 0
|
5天前
|
存储 监控 关系型数据库
Mysql内部在索引层面的优化
Mysql内部在索引层面的优化
|
5天前
|
SQL 算法 关系型数据库
MySQL索引优化实战二
MySQL索引优化实战二