写点什么

MySQL 索引原理 图文讲解

发布于: 2021 年 03 月 23 日
MySQL 索引原理 图文讲解

索引


在数据库中,索引可以理解为是一种单独的,物理的对数据库表中的一列或者多列的值进行排序的一种存储结构。它的作用是能让我们快速检索到想要的数据,好比字典的目录,通过目录的页码能快速找到我们想查找的内容。


在大数据量的数据库表中检索数据,如果没有建立索引,那就得全表扫描,将所有记录一一取出,与查询条件对比,然后返回满足条件的记录,大量的 IO 操作,这无疑是很耗费时间的。如果建立了索引,就能通过索引值快速定位到一个小范围的数据区间,避免全表扫描,大大提高了查询效率。


一个系统的性能好坏,系统架构和代码逻辑是一方面,还有一个点就是 SQL 语句和表索引的优化了,那首先得弄清楚索引的原理,才能进行写出更好的 SQL 以及优化,下面主要通过 MYSQL 的索引进行讲解。


树相关数据结构


其实在不同的数据库中,索引的具体实现是可能不同的,不能一口咬定索引的本质就是某某数据结构。比如 MongoDB 的索引使用的是 B-tree 数据结构;Mysql 的索引使用的是 B+tree 数据结构;再比如 ES 的倒排索引,HBase 的分布式索引等更复杂。不同的索引种类就是为了解决不同场景下的问题而设计的。


不过大部分的数据库的索引结构是树,二叉树,B 树,B+树等,下面我们简单了解下这些数据结构。


树(Tree)


树是一种数据结构,它是由 n(n>0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:


1. 每个结点有零个或多个子结点;

2. 没有父结点的节点称为根结点;

3. 每一个非根结点有且只有一个父结点;

4. 除了根结点外,每个子结点可以分为多个不相交的子树;



二叉树(Binary tree)


二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。


二叉树是指树中节点的度不大于 2 的有序树,它是一种最简单且最重要的树。二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不相交的,分别称作根的左子树和右子树组成的非空树;左子树和右子树又同样都是二叉树 。它的时间复杂度是 O(n)。



当然,二叉树根据一些特性,又可以分为平衡二叉树,二叉查找树,满二叉树,完全二叉树等,此就不细讲了,大家可自行百度了解。


这里需要讲下平衡树(Balance Tree,BT) ,它指的是任意节点的子树的高度差都小于等于 1。常见的符合平衡树的有,B 树(多路平衡搜索树)、AVL 树(二叉平衡搜索树)等


B 树(B-tree)


B 树属于多叉树,又名平衡多路查找树(查找路径不只两个)。它能够保证数据有序,还保证了在查找、插入、删除等操作时性能都能保持在 O(logn),为大块数据的读写操作做了优化。它有以下特点:

  1. 任意非叶子结点最多只有 M 个子树,且 M>2

  2. 根结点至少有 2 个子树

  3. 除根结点以外的非叶子结点的儿子数为[M/2, M]

  4. 每个非根节点所包含的关键字个数 j 满足:┌m/2┐ - 1 <= j <= m - 1;

  5. 非叶子结点的关键字个数=指向子树的指针个数-1

  6. 非叶子结点的关键字:K[1], K[2], …, K[M-1];且 K[i] < K[i+1]

  7. 非叶子结点的指针:P[1], P[2], …, P[M],其中 P[1]指向关键字小于 K[1]的子树,P[M]指向关键字大于 K[M-1]的子树,其它 P[i]指向关键字属于(K[i-1], K[i])的子树

  8. 所有叶子结点位于同一层


在 B 树中查找给定关键字的方法是,首先把根结点取来,在根结点所包含的关键字 K1,…,Kn 查找给定的关键字(可用顺序查找或二分查找法),若找到等于给定值的关键字,则查找成功;否则,一定可以确定要查找的关键字在 Ki 与 Ki+1 之间,Pi 为指向子树根节点的指针,此时取指针 Pi 所指的结点继续查找,直至找到,或指针 Pi 为空时查找失败。树高一层意味着多一次的磁盘 I/O。


下图是 M=3 时,一种 B 树展现形式:



B+树(B+Tree)


B+树是 B 树的一个升级版,相对于 B 树来说 B+树更充分的利用了节点的空间,B+树的特点是能够保持数据稳定有序,让查询速度更加稳定,其速度完全接近于二分法查找,其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入,这与二叉树恰好相反。


B+树的特点如下:

  1. 非叶子节点不保存关键字记录的指针,只进行数据索引。所有数据记录节点按照键值的大小存放在同一层的叶子节点上,非叶子结点只存储 key 的信息,这样使得 B+树每个非叶子节点所能保存的关键字大大增加,树的层级更少查询数据更快。

  2. 叶子节点的关键字有序排列,左边结尾数据都会保存右边节点开始数据的指针。在查询大小区间的数据时候很方便,数据紧密性很高。

  3. 能够保持数据稳定有序,让查询速度更加稳定,其速度完全接近于二分法查找,其插入与修改拥有较稳定的对数时间复杂度。

  4. 叶子节点保存了父节点的所有关键字记录的指针,所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样。

  5. 非叶子节点的子节点数=关键字数。

  6. 遍历全节点数据只需要遍历所有叶子节点即可,这有利于数据库做全表扫描。

  7. 所有关键字都出现在叶子结点的链表中(稠密索引),非叶子结点相当于是叶子结点的索引(稀疏索引)。


虽然 B+树相对于 B 树有许多优势,但如果经常访问的数据离根节点很近,而 B 树的非叶子节点本身存有关键字记录数据的指针,所以 B 树对于这种数据检索的速度会要比 B+树快。


B+树的结构如下图所示:



Mysql 聚簇索引


我们知道,Mysql 的 InnoDB 使用的是 B+树存储数据,除了主键索引为聚簇索引,其它索引均为非聚簇索引。一个表中只能存在一个聚簇索引(主键索引),但可以存在多个非聚簇索引(非主键索引)。B+树中叶子节点包含数据表中的行记录,即包含主键索引和数据,这就是聚簇索引。


Mysql 存储的数据是以数据页为最小单位的,数据在数据页中是连续存储的,InnoDB 的数据文件(.idb)按主键聚集,所以 InnoDB 必须有主键,如果没有显示指定主键,则选取首个为唯一且非空的列作为主键索引,如果也没有,则 Mysql 自动为 InnoDB 表生成一个隐含字段 ROW_ID 作为主键,这个字段长度为 6 个字节,类型为长整形。数据页和数据页之间是通过双向链表来关联的,数据与数据之间通过单向链表来关联。



注意,上图数据页的行记录数据中,为简便才列出出 3 个字段 id,name 和 age,实际根据你一条数据有多少字段,就会存多少个字段的值。


你是否发现上图中有个特点,就是叶子节点的父节点,存储的数据其实是主键和数据页,到了这一层,我们通过主键比较,就能定位到具体的数据页了。但如果数据表数据量非常大了,从而数据页的数量也变得非常多,也就导致了索引页会变得很大,那我们在一个很大的索引页中再进行查找,那效率也会变得很低了。


所以针对此弊端,产生了一种新的存储结构,即索引页,如上图的第一层,它是对索引页的索引,也叫辅助索引(稀疏索引)。


假设现在需要查找 id=12 的数据,首先在最上层的索引页 1 中,通过二分查找主键,发现应该在索引页 2 中查找,然后定位到索引页 2 中,此时索引页 2 中是有记录具体的数据页了,最后通过比较主键定位到数据页 2 中,然后遍历数据页 2 中的数据即可。


可能有人会问那上一层索引页(例如索引页 1)数据量又太大了呢?毫无疑问,可以再将索引页 1 继续分裂,然后往上再构建一层,以此类推。学习过跳表的同学可能对这种数据结构理解起来很容易,它们很相似。Mysql 的 InnoDB 底层使用的就是这种数据页加索引页的结构来存储数据的。


根据以上分析,Mysql 选择 InnoDB 引擎的时候,主键尽量定义简单,不要太大,因为在主键索引中会在 B+树各层中存储主键值,会占用空间。其二尽量选择有单调性的字段作为主键,不然为了维护一个有序 B+树,非单调性的字段计算起来比较麻烦复杂,所以使用自增字段作为主键则是一个很好的选择。


Mysql 非聚簇索引


我们已经了解到主键索引(聚簇索引)的底层原理了。那我们平常建立的索引除了主键索引,肯定会还有其他非聚簇索引,例如基于 name+age 建立的索引。它又是怎么构建索引结构的呢?


其实原理同主键索引差不多,主键索引是根据主键来维护一个 B+树,非主键索引就是根据索引列来维护一个 B+树。不同的索引对应一个 B+树,索引也占用存储空间,这也就是不能建太多索引的原因。


非主键索引,会根据索引列维护一个 B+树,和主键索引不同的是,索引页中用非主键索引列(例如 name+age)代替主键,并且叶子节点的数据页存放的数据不再是整个行记录数据,而是主键加非索引列的值,例如 id+name+age。


那对于非主键索引,又是如何维护一个 B+树的呢?其实在插入数据的时候,首先会根据 name 进行排序,如果 name 值一样,再根据 age 排序,如果 age 值也一样,最后根据主键来排序,最终插入到合适的数据页中。


为什么非聚簇索引的 B+树的数据页不存放整个行记录呢?因为聚簇索引的 B+树中的数据页已经存放了整个行记录了,如果还在其他非聚簇索引中存放整个行记录,特别是一行记录的字段非常多的时候,会导致数据重复存储,严重浪费存储空间。


假如有以下查询语句(已建立 name+age 索引),需要返回行记录的全部字段信息,但是非聚簇索引中数据页只存储了 id+name+age,那其他字段的信息去哪里取呢?


SELECT * FROM person WHERE name='Mr.nobody' AND age=18
复制代码


那就涉及到回表查询了。通过非聚簇索引查询到了记录主键值,然后再根据主键值再到聚簇索引中查找,就能查询到所有字段信息了,这就是回表。


那 SQL 查询条件字段是非聚簇索引的,是否就一定要进行回表查询呢?请看如下 SQL 查询语句:


SELECT id,name,age FROM person WHERE name='Mr.nobody' AND age=18
复制代码


你会发现返回的字段其实都在非聚簇索引的数据页中,所以这种情况是不需要回表的。所以当在非聚簇索引中查询到的结果满足不了返回的字段时,才需要根据主键值到聚簇索引当中回表查询需要的字段。


所以我们在写 SQL 查询的时候,如果能根据主键查询到我们想要的数据,就优先使用主键查询;还有,在使用非聚簇索引查询数据的时候,需要返回的字段信息包括在非聚簇索引字段中,就直接写返回的字段,而不是写*号返回全部的字段信息,因为可能会进行回表查询增加查询时间,而且返回的数据量太大还会浪费带宽。


MyISAM 索引


上面我们是基于 InnoDB 存储引擎讲解的索引,那对于 Mysql 的另外一种存储引擎 MyISAM,索引结构又是什么样的呢?


MyISAM 存储引擎也是使用 B+树作为索引结构,和 InnoDB 的一样,但是 MyISAM 中,叶子节点的 data 域存放的是数据记录的地址,表数据存储在独立的地方。即主键索引和非主键索引叶子节点中,都不存储真正的表数据,而是存储指向表数据的地址。所以也不存在回表查询的情况。


在 MyISAM 中,主键索引和非主键索引在结构上没有任何区别,只是主键索引要求 key 是唯一的,而非主键索引的 key 可以重复。MyISAM 的索引方式也叫做非聚簇索引,这样叫是为了与 InnoDB 的聚簇索引区分。



索引存储文件


索引是存储在文件系统中的,是实际占据物理空间的,在不同的存储引擎中,索引存储的文件也不同。存储引擎是基于表的。如下创建 2 张表,一张基于 InnoDB 存储引擎,一张基于 MyISAM 存储引擎。


CREATE TABLE innodb_table (	id INT PRIMARY KEY,	name VARCHAR(20)) ENGINE=INNODB;
CREATE TABLE myisam_table ( id INT PRIMARY KEY, name VARCHAR(20)) ENGINE=MYISAM;
复制代码



注意,以上是基于 Mysql8.020 版本,不同的 Mysql 版本可能生成的文件不一样。创建完表后,会自动生成以上文件,在 InnoDB 中,每一个表的索引(B+树)的非叶子节点存储索引,叶子节点存储索引和索引对应的数据,.ibd 文件存储着表数据和索引。而在 MyISAM 中,索引和数据是分开存储的,.MYD 文件用于存储表数据,*.MYI 文件存储索引相关的数据。



发布于: 2021 年 03 月 23 日阅读数: 41
用户头像

CSDN博客专家,微信搜一搜 - 陈皮的JavaLib 2020.02.22 加入

CSDN博客专家,专注各项技术领域的Java开发工程师,微信搜一搜【陈皮的JavaLib】,关注后学习更多技术文章和一线大厂面试资料和技术电子书籍。

评论

发布
暂无评论
MySQL 索引原理 图文讲解