一.吊打面试官系列-数据库优化-认识MySql索引

1.什么是索引

索引（Index）是帮助DBMS（数据库）高效获取数据的数据结构，索引是为了加速对表中数据行的检索而创建的一种分散的存储结构。如果数据库没有索引就会走表进行全表扫描，一旦数据量上来，简直就是灾难。下面我给了一个案例来简单理解一下，假如我们按照User的ID列来创建一个索引，效果如下：
在这里插入图片描述
如果我们没有索引，当我们查询一个 where id = 7 的数据的时候，Mysql会进行全表扫描，至少要扫描7次，如果我们使用了索引，如上图：是根据数据ID列创建的索引结构，MySql采用的是B+tree来构建索引，这种结构本身是有序的(左小右大的顺序)，那就可以采用二分查找快速定位到结果。比如对于：where id = 7 在索引中只需要对比3次即可找到，然后根据找到的元素对应的数据地址直接取完整数据，大大提高了检索效率。

2.索引的结构(tree)

Mysql的索引采用B+Tree和Hash数据结构来实现，如下图(Navicat工具-表设计-索引)：
在这里插入图片描述
在讲MySql索引原理之前我们先来做一点知识普及。对于"树"这种数据结构来说，他有很多变种，最简单的是二叉树，如下：

树有一些基本的概念

结点：使用树结构存储的每一个数据元素都被称为“结点”
1. 父结点（双亲结点）：4的父节点是2
2. 子结点：4 和 7 是 2 的子节点
3. 兄弟结点：4 和 7 他们是兄弟节点
4. 树根结点（简称“根结点”）：2 所在节点，没有父节点的节点
5. 叶子节点：3 ，6,11,15,17,22所在的节点就是叶子节点
子树：4 和 7 是 2 的只子树
空树：如果集合本身为空，那么构成的树就被称为空树。空树中没有结点。
度：对于一个结点，拥有的子树数（结点有多少分支）称为结点的度，一棵树的度是树内各结点的度的最大值，上面这个数的度是 2
层次：从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类推，一棵树的深度（高度）是树中结点所在的最大的层次，上面这个树的层次是 4
森林：由 m（m >= 0）个互不相交的树组成的集合被称为森林

二叉树它的特点是：是每个节点最多只能有两棵子树，且有左右之分，由二叉树衍生出来一种排过序的树叫：有序树或查找树。查找树就是按照 左小右大的顺序进行排序，如下：
在这里插入图片描述
有序只有就可以对半查找，比如要查找20，先从根节点开始查找，20 > 10 ,左边就直接不找了，然后再去对比 16 ，最多三次就能找到 20 所在的节点，性能很高。

查找二叉树有他的问题，就是当插入的元素始终偏大的时候，树就会朝着一边倾斜，从而退化成链表，降低性能，如下：
在这里插入图片描述
所以由此衍生出了平衡二叉树(AVL-tree) ，平衡二叉树也叫自平衡二叉搜索树（Self-Balancing Binary Search Tree），所以其本质也是一颗二叉搜索树，不过为了限制左右子树的高度差，避免出现倾斜树等偏向于线性结构演化的情况，所以对二叉搜索树中每个节点的左右子树作了限制，左右子树的高度差称之为平衡因子，树中每个节点的平衡因子绝对值不大于1 ，此时二叉搜索树称之为平衡二叉树。

自平衡是指，在对平衡二叉树执行插入或删除节点操作后，可能会导致树中某个节点的平衡因子绝对值超过 1，即平衡二叉树变得“不平衡”，为了恢复该节点左右子树的平衡，此时需要对节点执行旋转操作如下：
在这里插入图片描述
AVL树是平衡的，解决了查找树向一边偏斜甚至形成链表导致性能差的问题，所以AVL的查询是很快很稳当的，但是AVL树也有自己的问题:AVL树每次插入删除会进行大量的平衡度计算,插入删除比较耗时。因此出现了红黑树

红黑树也是一种自平衡二叉树，在平衡二叉树的基础上每个节点又增加了一个颜色的属性，节点的颜色只能是红色或黑色，例如，根节点必须是黑色的，每个叶子节点（NIL节点）都是黑色的，每个节点要么是红色的，要么是黑色的，每个红色节点的两个子节点都必须是黑色的等。
在这里插入图片描述
红黑树这样设计的目的在于第一：在任何一棵子树中，从根节点向下走到空节点的路径上所经过的黑节点的数目相同，从而保证了是一个平衡二叉树，
平衡二叉树（如AVL树）追求绝对平衡，其条件较为苛刻，在AVL树中，任何节点的左右子树的高度差最多为1，这种严格的平衡条件使得AVL树的实现相对复杂

红黑树的查询性能略微逊色于AVL树，因为其比AVL树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的AVL树最多多一次比较，但是，红黑树在插入和删除上优于AVL树，AVL树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于AVL树为了维持平衡的开销要小得多

对于Mysql而言并未选择二叉树，而是选择的多叉树，因为对于：数组，链表，包括二叉树而言都有一个问题，就是不适合存储大数据量，比如我有1千万数据，如果使用二叉树来存储那简直就是灾难，因为二叉树最多只能有2个分叉，这样的话树高就会变得非常高，那查询效果跟链表有什么区别？所以对于Mysql这种可能数据量非常大的数据库数据做索引它选择的是多叉树：B+tree。

多叉树可以分为：b-tree 和 b+tree,先说一下前者,下面是一个b-tree
在这里插入图片描述
B树（英语：B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如文件系统，数据库索引，如图所示就是一颗符合规范的B树。

B-Tree相比于二叉树而言，它每个节点允许存储2个以上的值，从而一个节点可以有多个子树，这样的话相同的数据量，B-tree比二叉树的节点会扫很多很多，树高也就会低很多，比较次数也就会少很多。另外：每次节点进行比较的时候都会从磁盘上加载数据(I/O),如果节点变少，树高变低，那么磁盘IO次数也大大减少，性能就会大大提高。

那么B+Tree和B-Tree又有什么区别呢？B+Tree是对B-tree的变种，Mysql索引使用的是B+tree，它和前者的区别在于：B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用，B+tree如下：
在这里插入图片描述
是InnoDB的B+树索引结构，它的优势体现在：

B+Tree属于多路树，每次查询都要走到叶子节点，查询效率稳定
非叶子节点不存储完整数据，而是存储键值 KEY ，和子树节点的应用，可以存储更多的KEY，充分利用每个节点的存储空间 16KB，减少了节点数，树高变矮，IO次数变少，性能更高。
举例说明：比如使用User的ID列创建索引，那么内部节点只需要存储ID列的值和子节点的地址指针，把一行数据放到叶子节点存储，这样内部节点就可以存储更多的ID值了。
叶子节点存储完整数据，叶子节点是有序的，每个叶子节点指向下一个节点的应用，形成一个双向链表结构，适合范围查询和排序。

所以：b+tree相比b-tree而言需要的节点是更少的，因为b+tree把数据存储到叶子节点，那么其他内部节点就可以存储更多的key值，需要的节点也会更少，从而树高变低，IO次数变少，性能变高。同时叶子节点的数据是形成有序链表结构，对排序和范围查找支持友好。

另外对于B+Tree而言，三层就可以存储千万级别的数据量，这里我们可以估算一下，在MySql中一个索引Node的大小为16KB，假设一行数据1k，那么一个节点在一个页/块中，能存储16行数据，由于B+Tree的内部节点只存储：索引列值和子节点指针，指针占6字节，key类型假设是bigint 占8字节(加起来14字节)，那么一个节点存储空间为16*1024字节，那么一个节点可以存放： (16 * 1024) / (6+8) = 1170 个key和1171个指针

也就是说一个节点可以放1170个key和指针，也就是说它至少有1171个子节点，因为一个节点可以放16行数据，那么二层可以放 16 * 1171 = 18736 行数据，那么第三层就可以放 16 * 1171 * 1171 = 21939856 2千万左右的数据。这个数据也是业界默认的Mysql的瓶颈量，单表不要超过2千万的数据量。

3.索引的物理结构

[以Mysql5.x为例]MySQL常用的存储引擎有InnoDB,和MyIsam，如果使用InnoDB存储引擎，数据库文件类型就包括.frm、ibdata1，默认存储到“C:\ProgramData\MySQL\MySQL Server 5.x\data”目录下，比如有一个t_user表采用的是InnoDB引擎，那么就会参数2二个文件：
在这里插入图片描述

frm : 表结构文件
idb : 表数据和索引文件，记住：InnoDB的数据和索引是在同一个文件中

而对于MyISam存储引擎而言不是这样的，一个表它分为了三个文件
在这里插入图片描述

db.frm ：表结构文件
db.MYD : 表数据文件
db.MYI : 索引存储文件

记住：MyISam的表结构，数据，索引文件的是单独的一个文件。在InnoDB中索引和数据在同一个ibd文件中，有了这个概念之后我们就可以很好的理解这2种存储引擎的B+Tree的区别了。

4.索引的分类

在这里插入图片描述

索引的分类可以分为：主键索引，唯一索引(unique ) ，普通索引(normal)，全文索引(fulltext)如下：
在这里插入图片描述
按功能分类：

唯一索引：唯一索引是一种限制数据库表中列值唯一性的索引，用于保证在指定列上没有重复的数据。与普通索引不同，唯一索引在索引列中的每个值都是唯一的，且不允许插入重复值，包括 NULL 值。适用于：手机号，身份证，用户名等字段，
普通索引：它只包含一个列的值和指向该行的指针，用于加速对该列的单列查询。可以对表的任意列创建普通索引，但通常建议对经常进行查询和排序的列创建索引，列值可以重复，适用于：姓名，生日等字段。
全文索引：用来对表中的文本域(char，varchar，text)进行索引，全文索引是一种基于文本内容的索引技术，可以快速地检索出包含指定关键词或短语的文档或记录。相比于传统的索引技术，全文索引更加适用于文本数据的搜索和查询。用于需要对大量文本数据进行搜索和查询的情况，如新闻、博客、社交媒体等应用，或者模糊搜索场景

按物理实现方式分类：

聚集索引：通常，聚集索引与主键同义，聚簇索引（Clustered Index）是一种索引方式，它将数据存储在磁盘上，并且按照索引的顺序进行排序。它可以将相邻的行存储在相邻的磁盘页上，从而提高查询的性能。聚簇索引只能为表创建一个索引，因为每个表只能以一种方式进行排序。聚簇索引对于经常需要根据特定列进行查询的表非常有用，因为它们可以快速定位数据。
非聚集索引：非聚簇索引（Non-Clustered Index）是一种索引方式，它将索引数据存储在单独的数据结构中，而不是存储在表的磁盘上。它包含了指向表中每行的指针，并按照索引列的顺序进行排序。这种索引方式可以为表创建多个索引，并且可以根据多个列进行排序。非聚簇索引对于经常需要根据不同的列进行查询的表非常有用，因为它们可以快速定位数据。

按作优化角度分类：

组合索引：多个列一起构建的索引，用于提高多列查询的效率
前缀索引：是一种基于字符串前缀的数据库索引结构。在前缀索引中，对于字符串类型的列，可以只对其前几个字符建立索引，而不是对整个字符串进行索引。这样可以大大减小索引的存储空间，同时也可以提高查询效率。
覆盖索引：是一种特殊的索引，它包含了所有需要查询的列的数据，而不需要进一步的查找操作就可以直接返回查询结果。这种索引也被称为索引覆盖或索引包含查询。

按关系分类：

主键索引：是随着设定主键而创建的，也就是把某个列设为主键的时候，数据库就会給改列创建索引。这就是主键索引.唯一且没有null值,
在表上定义主键 PRIMARY KEY，InnoDB 将主键索引用作聚簇索引。

如果表没有定义主键，InnoDB 会选择第一个不为 NULL 的唯一索引列用作聚簇索引。如果以上两个都没有，InnoDB 会使用一个 6 字节长整型的隐式字段 ROWID 字段构建聚簇索引。该 ROWID 字段会在插入新行时自动递增
辅助索引：出主键以外的其他列创建的索引就是辅助索引，辅助索引叶子节点存储的是主键索引的值。

不同类型的存储引擎可能支持不同的索引类型。例如，InnoDB存储引擎支持B-tree和Full-text索引，但不支持Hash索引；而Memory存储引擎支持B-tree和Hash索引，但不支持Full-text索引

5.索引的算法Hash

索引的算法有B+Tree 和Hash 两种方式
在这里插入图片描述

Hash方式底层使用的是Hash表算法，时间复杂度是n(1) ,一次IO就能查询到结果，但是Hash是无序的，有如下缺点：

Hash结构的索引不支持排序，InnoDB,MyIsam都不支持Hash
只能进行等值查询( = , in)，不能使用范围查询（ > ，< ，Between ）等
列的重复值过多会出现大量Hash冲突问题

哈希索引就是一种以键值对存储数据的结构，类似于HashMap。每个索引项包含两部分，一个是关键字的哈希值，另一个是指向存储该关键字的数据块的指针，Hash索引的查询速度非常快，因为它通过哈希函数将关键字转换为固定长度的哈希值，然后根据哈希值直接访问索引项。由于哈希值是唯一的，因此可以直接找到存储数据的位置，不需要进行比较操作
在这里插入图片描述

Mysql常用引擎允许的索引类型

储存引擎	允许的索引类型
Myisam	BTREE
InoDB	BTREE
Memory	Hash,BTREE

Mysql InnoDB引擎不支持hash索引，但是在内存结构中有一个自适应hash索引，来提高查询性能，当设置hash索引时会自动转换成btree索引。
innodb_adaptive_hash_index 是 MySQL InnoDB 存储引擎中的一个参数，它控制着 InnoDB 自适应哈希索引的功能。

innodb_adaptive_hash_index 的默认值为 ON，也就是说，默认情况下 InnoDB 自适应哈希索引是开启的。如果您希望关闭这个功能，可以将该参数设置为 OFF。

6.辅助索引和回表

对于主键默认会创建主键索引，其他列创建的索引就叫辅助索引，也叫二级索引，辅助索引的叶子节点存储的是主键索引的键值，这就意味着辅助索引需要查询两个B+Tree，比如：下面给ID列和Name列都建立了索引，ID列的索引是主键索引，而Name列的索引是辅助索引
在这里插入图片描述
主键索引的叶子节点存储的是数据，辅助索引的叶子节点存储的是主键索引的健值，所以当我们带着 where name = “A” 去查询的时候，会从辅助索引的根节点进行查找，当找到叶子节点后，又会拿着ID值去主键索引进行查找，这个过程叫 回表 ，所以：能按照 where id = 值来查找性能是最高的。

覆盖索引：如果我们select 的列正好出现在辅助索引的索引列中，那么就不需要回表。比如：辅助索引列中包含name的值，而查询列的正好是 select name ，那就可以直接取辅助索引列的值了，就不需要回表。所以：推荐使用组合索引，以及不要使用select *,它会导致覆盖索引失效。

对于MyISam而言它的B+Tree和InnoDB是有区别的，MyISAM索引文件和数据文件是分离的

在这里插入图片描述
MyIsam的B+Tree叶子节点存储的是数据的地址，索引和数据是分开存储的，InnoDB和MyIsam的索引结构的区别正好对应了物理结构的区别，InnoDB的B+tree数据在叶子节点，也就是索引和数据是在一起的存储在ibd文件中，那么他们的逻辑和物理存储顺序都是一致的(聚集索引)，而MyIsam的索引和数据是分开的，存储在MYD(数据)和MYI(索引)文件中。