深入了解Mysql的B+Tree索引道理
索引是啥？
索引是为了加快对表中数据行的检索而创立的一种分离储备的数据构造。
索引的工作机制是怎样的？
如上图中，假如此刻有一条sql语句 select * from teacher where id = 101，假如没有索引的前提下，我们要寻到这笔记录，我们就需要就行全表扫描，匹配id = 101的数据。假如有了索引，我们就可以快速的通过索引寻到101所对应的行记载在磁盘中的地址，再按照给定的地址取出对应的行数据。
MYSQL数据库为什么要使用B+TREE作为索引的数据构造？
对数据的加快检索，第一想到的就是二叉树，二叉树的查寻时间复杂度可以到达O(log2(n))。下面看一下二叉树的储备构造：
二叉树搜索相当于一个二分查寻。二叉查寻能大大晋升查询的效力，但是它有一个问题：二叉树以第一个插入的数据作为根节点，如上图中，假如只看右侧，就会发明，就是一个线性链表构造。假如我们此刻的数据只包括1, 2, 3, 4，5, 6，就会显现一下状况：
假如我们要查询的数据为6则需要遍历所有的节点才能寻到6，即，相当于全表扫描，就是由于存在这种问题，所以二叉查寻树不适合用于作为索引的数据构造。
基于这样的推演，为理解决存在线性链表的问题，很容易就能够想到均衡二叉查寻树。下面看看均衡二叉树是怎样的：
均衡二叉查寻树定义为：节点的子节点高度差不克不及超越1,如上图中的节点20，左节点高度为1，右节点高度0，差为1，所以上图没有违反定义，他就是一个均衡二叉树。包管二叉树均衡的方式为左旋，右旋等操纵，至于假如左旋右旋，可以自行去搜索相关的知识。
假如上图中均衡二叉树留存的是id索引，此刻要从id = 8的数据，第一要把根节点加载进内存，用8和10停止比力，发明8比10小，连续加载10的左子树。把5加载进内存，用8和5比力，同理，加载5节点的右子树。此时发明命中，此刻要加载id为8的索引对应的数据。
如何寻到索引对应的数据呢？
索引留存数据的方式一样有两种，第一种为在节点的数据区留存id = 8的行数据的所有数据详细内容。别的一种方式，数据区留存的是真正留存数据的磁盘地址。
到这里，均衡二叉树解决了存在线性链表的问题，数据查询的效力仿佛也还可以，根本能到达O(log2(n))， 那为什么mysql不选中这样的数据构造呢，他又存在什么样的问题呢？
问题1： 搜索效力不足，一样来说，在树构造中，数据所处的深度，决议了搜索时的IO次数。如上图中搜索id = 8的数据，需要停止3次IO。当数据量抵达几百万的时候，树的高度就会很恐惧。
问题2： 查询不不不乱，假如查询的数据落在根节点，只需要一次IO，假如是叶子节点或者是支节点，会需要屡次IO才可以。
问题3： 节点储备的数据内容太少。没有很好利用操纵系统和磁盘数据交流特性，也没有益用好磁盘IO的预读能力。由于操纵系统和磁盘之间一次数据交流是已页为单位的，一页 = 4K，即每次IO操纵系统会将4K数据加载进内存。但是，在二叉树每个节点的构造只留存一个关键字，一个数据区，两个子节点的援用，并不克不及够填满4K的内容。幸幸苦苦做了一次的IO操纵，却只加载了一个关键字，在树的高度很高，刚好又搜索的关键字位于叶子节点或者支节点的时候，取一个关键字要做许多次的IO。
那有没有一种构造能够解决二叉树的这种问题呢？
有，多路均衡查寻树：（Balance Tree）：
B Tree 是一个绝对均衡树，所有的叶子节点在统一高度，如下图所示：
B Tree有什么优势，又是如何去解决一些问题的呢？
先看定义，上图为一个2-3树（每个节点储备2个关键字，有3路），多路均衡查寻树也就是多叉的意思，从上图中可以看出，每个节点留存的关键字的个数和路数关系为：
关键字个数 = 路数 – 1。
假设要从上图中去寻觅id = 28的数据，B TREE 搜索历程如下：
第一把根节点加载进内存，加载了17,35两个关键字，推断规则为：
按照以上规则命中28后，接下来加载28对应的数据， 就去寻28对应的数据区，数据区中储备的是详细的数据或者是指向数据的指针。
为什么说这种构造能够解决均衡二叉树存在的问题呢？
能够很好的利用操纵系统和磁盘的交互特性， MYSQL为了很好的利用磁盘的预读能力，将页大小为16K，马上一个节点（磁盘块）的大小设定为16K，一次IO将一个节点（16K）内容加载进内存。这里，假设关键字类型为 int，即4字节，若每个关键字对应的数据区也为4字节，不思考子节点援用的状况下，则上图中的每个节点大约能够储备（16 * 1000）/ 8 = 2000个关键字，则共2001个路数。关于二叉树，三层高度，最多可以留存7个关键字，而关于这种有2001路的B树，三层高度能够搜索的关键字个数远远的大于二叉树。
在B TREE包管树的均衡的历程中，每次关键字的转变，都会致使构造发生很大的转变，这个历程是特殊白费时间的，所以创立索引必然要创立适宜的索引，而不是把所有的字段都创立索引，创立冗余索引只会在对数据停止新增，删除，修改时增添机能耗损。
既然B树已经很好的解决了问题，为什么MYSQL还要用B+TREE？
先看看B+TREE是怎样的，B+TREE是B TREE的一个变种，在B+树种，B树种的路数和关键字的个数的关系不再成立了，B+TREE中，数据检索规则采纳的是左闭合区间，路数和关键个数关系为1比1，详细如下图所示：
假如上图中是用ID做的索引，假如是搜索id = 1的数据，搜索规则如下：
按照如上规则，终究在叶子节点中命中数据，按照叶子节点中节点1的数据区取得真正的数据。
B TREE和B+TREE不同是啥？
1、B+TREE 关键字的搜索采纳的是左闭合区间，之所以采纳左闭合区间是由于他要最好的去支撑自增id，这也是mysql的设计初衷。即，假如id = 1命中，会连续往下查寻，直到寻到叶子节点中的1。
2、B+TREE 根节点和支节点没有数据区，关键字对应的数据只留存在叶子节点中。即只要叶子节点中的关键字数据区才会留存真正的数据内容或者是内容的地址。而在B树种，假如根节点命中，则会直接返回数据。并且在B+TREE中，叶子节点不会去留存子节点的援用。
3、B+TREE叶子节点是次序摆列的，并且相邻的节点具有次序援用的关系，如上图中叶子节点之间有指针相连接。
MYSQL为什么终究要去选中B+TREE？
1、B+TREE是B TREE的变种，B TREE能解决的问题，B+TREE也能够解决（落低树的高度，增大节点储备数据量）
2、 B+TREE扫库和扫表能力更强，假如我们要按照索引去停止数据表的扫描，对B TREE停止扫描，需要把整棵树遍历一遍，而B+TREE只需要遍历他的所有叶子节点即可（叶子节点之间有援用）。
3、B+TREE磁盘读写能力更强，他的根节点和支节点不留存数据区，所有根节点和支节点一样大小的状况下，留存的关键字要比B TREE要多。而叶子节点不留存子节点援用。所以，B+TREE读写一次磁盘加载的关键字比B TREE更多。
4、B+TREE排序能力更强，如上面的图中可以看出，B+TREE自然具有排序功效。
5、B+TREE查询效力愈加不乱，每次查询数据，查询IO次数必然是不乱的。当然这个每个人的懂得都不一样，由于在B TREE假如根节点命中直接返回，确实效力更高。
MYSQL B+TREE详细落地势式
这里主要讲解的是MYSQL按照B+TREE索引构造不一样的两种储备引擎（MYISAM 和 INNODB）的实现，第一寻到MYSQL留存数据的文件夹，看看mysql是怎样留存数据的：
进入到这个名目下，这个名目下留存的是所有数据库，再进入到详细的一个数据库名目下。在这里，有多种数据的储备引擎，这里讲解MYISAM和innodb，如图中所示：
MYISAM储备引擎索引：
从图中可以看出，使用MYISAM储备引擎储备数据库数据，一共有三个文件：
Frm，表的定义文件。MYD：数据文件，所有的数据留存在这个文件中。MYI：索引文件。
在MYISAM储备引擎中，数据和索引的关系如下：
怎样查寻数据的呢？假如要查询id = 101的数据，先按照MYI索引文件（如上图左）去寻id = 101的节点，通过这个节点的数据区拿到真正留存数据的磁盘地址，再通过这个地址从MYD数据文件（如上图右）中加载对应的记载。
假如有多个索引，展现情势如下：
所以在MYISAM储备引擎中，主键索引和辅助索引是同级别的，没有主次之分。
Innodb储备引擎：
第一看一下汇集索引的概念，汇集索引定义为：数据库表行中数据的物理次序和键值的逻辑次序雷同。
Innodb以主键为索引来汇集组织数据的储备，下面看看Innodb是怎样组织数据的。
Innodb只要两个文件，Frm文件： 表的定义文件，和Ibd文件，没有专门留存数据的文件。数据以主键停止汇集储备，把真正的数据留存在叶子节点中。innodb设计初衷认为主键才是最主要的索引。详细如下图所示：
如上图中，叶子节点的数据区留存的就是真实的数据，在通过索引停止检索的时候，命中叶子节点，就可以直接从叶子节点中取出行数据。mysql5.5版本此前采纳的是MYISAM引擎，5.5之后采纳的是innodb引擎。
在innodb中，辅助索引的格局如下图所示？
如上图，主键索引的叶子节点留存的是真正的数据。而辅助索引叶子节点的数据区留存的是主键索引关键字的值。搜索历程为：假设要查询name = seven的数据，先在辅助索引中查询最后寻到主键id = 101，再在主键索引中搜索id为101的数据，终究在主键索引的叶子节点中猎取到真正的数据。所以通过辅助索引停止检索，需要检索两次索引。
把Innodb 和 MYISAM不同放在一张图中看，就如下所示：
创立索引的几大原则：
1、列的离散型：
离散型的运算公式：count(distinct col):count(col)，离散型越高，选中型越好。
如下表中各个字段，哪一列的离散型最好：
上图中，明显可以看出，name的离散型最好，假如用sex创立索引：
为什么说离散型越高，选中型越好？
如下图，假如对Sex创立索引，则索引构造将会如下：
假如此时检索 sex = 1的数据，根节点推断的时候，结果是查询左子树，但是当在左子树第二层再停止推断的时候，由于摆布分支都知足前提，所以很难选择选中哪一个分支连续搜索，或者是把两个分支同时停止搜索。
2、最左匹配原则
关于索引中的关键字停止对照的时候，必然是从左往右以此对照，且不成跳过。此前讲解的id都为int型数据，假如id为字符串的时候，如下图：
当停止匹配的时候，会把字符串转换成ascll码，如abc变成97 98 99，然后从左往右一个字符一个字符停止对照。所以在sql查询中使用like %a 时候索引会失效，由于%表示全匹配，假如已经全匹配就不需要索引，还不如直接全表扫描。
3、最少空间原则
前面已经说过，当关键字占用的空间越小，则每个节点留存的关键字个数就越多，每次加载进内存的关键字个数就越多，检索效力就越高。
结合索引：
单列索引：节点中的关键字[name]
结合索引：节点中的关键字[name, phoneNum]
可以把单列索引看成非凡的结合索引，结合索引的比力也是按照最左匹配原则。
结合索引列的选中原则：
（1） 经常用的列优先（最左匹配原则）
（2） 离散度高的列优先（离散度高原则）
（3） 宽度小的列优先，（最少空间原则）
下面简便举例平常经常会碰到的问题：
如，平常经常使用的查询sql如下：
Select * from users where name = ?
Select * from users where name = ? and pahoneNum = ?
为了加快检索速度，为上面的查询sql创立索引如下：
Create index idx_name on users(name)
Create index idx_name_phoneNum on users(name, phoneNum)
在上面解决方案中，按照最左匹配原则，idx_name为冗余索引， where name = ?一样可以利用索引idx_name_phoneNum停止检索。冗余索引会增减保护B+TREE均衡时的机能耗损，并且占用磁盘空间。
覆盖索引：
假如查询的列，通过索引项的信息可直接返回，则该索引称之为查询SQL的覆盖索引。覆盖索引可以提高查询的效力。
下面通过例子说明覆盖索引。
表：teacher
索引：PK（id）， key（name， phoneNum）， unique（teacherNo）
下面哪些sql使用到了覆盖索引？
Select teacherNo from teacher where teacherNo = ?：使用到了，检索到teacherNo 时候，可以直接将索引中的teacherNo 值返回，不需要进入数据区。
Select id，teacherNo from teacher where teacherNo = ?：使用到了，辅助索引的叶子节点留存了主索引的值，所以检索到辅助索引的叶子节点的时候就可以之间返回id。
Select name，phoneNum from teacher where teacherNo = ?：没有用到
Select phoneNum from teacher where name = ?, 使用到了。
知道了覆盖索引，就知道了为什么sql中要求尽量不要使用select *，要写明详细要查询的字段，一个缘由就是，这样在使用到覆盖索引的状况下，不需要进入到数据区，数据就能直接返回，晋升了查询效力。
通过前面的学习，我们可以很容易的清楚如下一下结论：
1、索引列的数据长度知足业务的状况下能少则少。
2、表中的索引并不是多多益善。
3、Where 前提中，like 9%， like %9%， like%9，三种方式都用不到索引。后两种方式关于索引是无效的。第一种9%是不肯定的，决议于列的离散型，结论上讲可以用到，假如发明离散状况特殊差的状况下，查询优化器觉得走索引查询机能更差，还不如全表扫描。
4、Where前提中 NOT IN 没法使用索引
5、多用指定查询，只返回本人想要的列，少用select *。
6、查询前提中使用函数，索引将会失效，这和列的离散型有关，一旦使用到函数，函数具有不肯定性。
7、结合索引中，假如不是依照索引最左列开端查寻，没法使用索引。
8、对结合索引准确匹配最左前列并范畴匹配另一列，可以使用到索引。
9、结合索引中，假如查询有某个列的范畴查询，其右侧所有的列都没法使用索引。
引荐Mysql教程《Mysql教程》
以上就是深入懂得Mysql的B+Tree索引道理的具体内容，更多请关注百分百源码网其它相关文章！
