关于MySQL索引,之前已经有过相关介绍《》本篇将对索引相关进行补充。

MySQL官方对索引的定义为:索引(Index)是帮助 MySQL 高效获取数据的数据结构。

白话文:索引就像书的目录一样可以非常快速的定位到书的页码。

如果向MySQL发出一条SQL语句请求,查询的字段没有创建索引的话,可能会导致全表扫描,这样的话查询效率非常低。

实现索引一般有一下几种算法:哈希算法、平衡二叉树算法、B树、B+树

I.哈希算法

哈希表(Hash table,也叫散列表),是根据关键码值直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表(HashMap快速随机查询的实现原理)。

优点:查找可以直接根据key访问;

缺点:因为底层数据结构是散列的,无法进行比较大小,所以不能进行范围查询;

在InnoDB中有一个特殊的“自适应哈希索引”:当InnoDB注意到某些索引值被使用的非常频繁时,它会在内存中基于B-Tree索引之上再创建一个哈希索引。这是引擎内部的行为,我们无法控制,但可以通过设置关闭该功能。

II.平衡二叉树算法:

平衡二叉树(AVL)它是一棵空树或它的左子树和右子树的深度之差(平衡因子BF=左子树的高度HL-右子树的高度HR)的绝对值不超过1(|BF|<=1),且它的左子树和右子树都是一颗平衡二叉树。平衡二叉树大部分操作和二叉查找树类似,主要不同在于插入删除的时候平衡二叉树的平衡可能被改变,并且只有从那些插入点到根结点的路径上的结点的平衡性可能被改变,因为只有这些结点的子树可能变化。

优点:平衡二叉树算法基本与二叉树查询相同,效率比较高;

缺点:插入操作需要旋转,支持范围查询;

关联阅读:《》

III.B树与B+树:

B树(B-tree)是一种树状数据结构,它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。概括来说就是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同,B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程,从而加快存取速度。普遍运用在数据库和文件系统。

因为B树节点元素比平衡二叉树要多,所以B树数据结构相比平衡二叉树数据结构实现减少磁盘IO的操作。

B+树相比B树,新增叶子节点与非叶子节点关系,叶子节点中包含了key和value,非叶子节点中只是包含了key,不包含value。

所有相邻的叶子节点包含非叶子节点,使用链表进行结合,有一定顺序排序,从而范围查询效率非常高。

但因为有冗余节点数据,所以会比较占用磁盘资源。

关联阅读:《》

在MySQL中默认数据与索引文件位置是/var/lib/mysql,不同引擎的索引文件的后缀也有所不同

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

对于MyISAM引擎的文件:

.myd即my data,是表数据文件

.myi 即my index,是索引文件

.log是日志文件。

而InnoDB引擎的文件,因为采用表空间(tablespace)来管理数据,存储表数据和索引,InnoDB数据库文件(即InnoDB文件集,ib-file set):所以数据与索引文件默认会存储在ibdata1文件中。

ibdata1、ibdata2等是系统表空间文件,存储InnoDB系统信息和用户数据库表数据和索引,所有表共用。

还有一种.ibd文件,是单表表空间文件,每个表使用一个表空间文件(file per table),存放用户数据库表数据和索引。

MySQL的InnoDB引擎和MyISAM引擎使用的都是B-Tree而底层实现又是用B+Tree来实现的,但实现方式有所不同,分别被称为聚簇索引和非聚簇索引。

MyISAM底层使用B+树,叶子节点的value对应存放行地址,并通过定位得到数据;而InnoDB底层使用B+树,叶子节点的value对应存放的是行的data数据,相比于MyISAM效率要高,但是比较占磁盘内存大小。

最后针对索引相关内容做出如下总结:

Q1:为什么要使用索引

索引(Index)是帮助MySQL高效获取数据的数据结构

如果向MySQL发送一条SQL请求,相关条件查询字段没有创建索引的话,就会导致全表扫描,这样的话查询效率就会非常低

Q2:索引底层使用那些数据结构

数据结构哈希算法:HashMap中应用的根据key-value的形式直接进行访问的数据结构;优点是查找客户直接根据key访问,能快速定位,随机查询效率高,缺点是不能进行范围查找

平衡二叉树算法:具备了二叉查找树的基本特征,并且子树高度差严格控制在一定范围内,保证节点的充分利用,查询效率高,但是缺点是插入时需要进行旋转(左单旋、右单旋、左右双旋、右左双旋),虽然支持范围查询但是效率不是很高

B树(B-Tree):B树是系统最优化大块数据的读和写操作,减少定位记录时所经历的中间过程,从而加快存取速度,普遍应用在数据库和文件系统;他的节点比平衡二叉树要多,所以可以实现减少磁盘I/O次数的操作

B+树:相比于B树新增叶子节点和非叶子节点的关系,非叶子节点只包含key,叶子结点包含key和value,所有相邻的叶子节点包含非叶子节点,使用链表进行连接,并且有一定的排序顺序,所以范围查询效率非常高

Q3:数据结构平衡二叉树原理

平衡二叉树算法:具备了二叉查找树的基本特征,并且左子树和右子树都是平衡二叉树,且深度差的绝对值不超过1,保证节点的充分利用,查询效率高,但是缺点是插入时需要进行旋转(左单旋、右单旋、左右双旋、右左双旋),虽然支持范围查询但是效率不是很高

Q4:平衡二叉树磁盘 IO 性质

使用平衡二叉树进行磁盘I/O的过程是每经过一个节点就需要进行一次磁盘I/O

首先第一次I/O从根节点开始,如果小于该节点则取左指针进行第二次I/O,反之取右指针进行第二次I/O;之后依次执行直到命中数据

Q5:数据结构 B 树的实现原理

B树(B-Tree):B树是系统最优化大块数据的读和写操作,减少定位记录时所经历的中间过程,从而加快存取速度,普遍应用在数据库和文件系统;他的节点比平衡二叉树要多,所以可以实现减少磁盘I/O次数的操作

Q6:数据结构B树与B+树的区别

相比于B树新增叶子节点和非叶子节点的关系,非叶子节点只包含key,叶子结点包含key和value,所有相邻的叶子节点包含非叶子节点,使用链表进行连接,并且有一定的排序顺序,所以范围查询效率非常高

但是因为有冗余节点数据,所以会比较占硬盘资源

Q7:MyISAM与InnoDB引擎中B+树的区别

MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址,而在InnoDB中,表数据文件本身就是B+Tree的一个索引结构,它的叶子节点保存了完整的数据记录,这个索引的key是数据表的一个主键,因此InnoDB表数据本身就是一个主键索引;

MyISAM底层使用B+树,叶子节点的value对应存放行数的地址,并通过定位得到数据

InnoDB底层使用B+树,叶子节点的value对应存放的是行的data数据,相比于MyISAM效率要高,但是比较占用硬盘的内存大小。

随笔,是记忆的一种延伸