概述

在整个计算机运行系统里，Cpu，内存，和磁盘主要的性能瓶颈是卡在了读取数据中，Mysql索引的优化主要在减少磁盘I/O操作中，这篇博客中详细讲解了二叉树结构，以及BTree作为Mysql索引结构的根本原理，文章底部留下来几个常用的问题。

索引的本质

是帮助mysql高校获取数据的数据结构在mysql中，数据最终存储在硬盘中

访问磁盘相当于是I/O操作，Mysql中有一个页(page)的概念，一个page就是树中的一个节点，每次Mysql就会取出一个page也就是一个节点的数据，而mysql默认一个page保存16k的数据。

(资料图)

二叉树

二叉树定义：

左子树的所有值都小于根节点右子树的所有值都大于根节点每个根节点最多分裂出两个子节点

平衡二叉树定义：

相对平衡，左右两个子树的深度差 绝对值不能超过1左右两个子树也必须是平衡二叉树可以避免二叉树的极端情况

B-Tree结构

特点:多叉(多阶)

1个节点可以存储查过2个元素，可以拥有超过2个子节点拥有二叉树的一些性质平衡，每个节点的所有子树高度一致，比较矮

元素个数计算：

已知条件：m阶B树，最多拥有m个子节点,假设一个节点的存储元素个数为x。

根节点计算公式：1 <= x < m-1非根节点(向上取整) ，计算公式：m/2 <= x <= m-1子节点个数：y = x + 1,根节点计算公式：2 <= y <= m非根节点(向上取整) ，计算公式：m/2 <= y <= m每个节点最多有m个子节点除根节点外，每个节点至少有m/2个子节点，注意如果结果除不尽，就向上取整根节点要么为空，要么就独根，否则至少有2个子节点有K个子节点的节点必有k个关键词，就是有m个数据就有m个叉叶节点的高度一致

单个节点可以保存多个数据，一次page可以获取更多的有效数据，同时因为分叉增多，数据层级肯定会更小，查询次数就会减少。

一个3层的Btree可以保存多少条数据呢?假设一条数据占用1k的空间(它的标识先可以忽略不计)，3层的B-tree结构保存的数据条数：

16 * 16 * 16 = 4096

复制

假如一个表中有500w数据，层级还是会很深，这样查询数据的时候，磁盘I/O还是会很多，(2)数据从小到大依次分布在树的不同层级中，进行范围查找时，获取范围越大，获取的节点就越多，极端情况下所有的数据全部遍历一遍，相当于遍历了整颗树，节点越多，I/O操作就会越多，性能就会卡主。

B+Tree

B+Tree解决了B-Tree结构存在的问题。

叶子节点保存数据信息，非叶子节点不保存节点保存的元素树等于m，并且是左闭右开叶子节点通过指针链接，方便范围查找，只需遍历叶子节点

为什么Mysql使用B+Tree，而不使用B-Tree呢？叶子节点基于索引排序更优，非叶子节点不保存数据，保存索引数据更多，一次I/O获取更多的目标数据。最底层的数据结构属于双向链表，在做排序或者是范围查找的时候就会很方便，它不用遍历上面的节点。

Mysql具体如何使用

Myisam

*.frm 数据表的定义信息

*.myi 保存索引的信息

*.myd 保存数据文件

Innodb

*.frm 数据表的定义信息

*.ibd 保存了索引信息和数据信息

在Innodb引擎下，如果表没有创建主键索引，数据表会自动创建主键索引。

回表

回表，顾名思义就是回到表中，也就是先通过普通索引（我们自己建的索引不管是单列索引还是联合索引，都称为普通索引）扫描出数据所在的行，再通过行主键ID 取出索引中未包含的数据。所以回表的产生也是需要一定条件的，如果一次索引查询就能获得所有的select 记录就不需要回表，如果select 所需获得列中有其他的非索引列，就会发生回表动作。即基于非主键索引的查询需要多扫描一棵索引树。

Mysql回表指的是在InnoDB存储引擎下，二级索引查询到的索引列，如果需要查找所有列的数据，则需要到主键索引里面去取出数据。这个过程就称为回表。

有Id,Name,Age等等字段，Id和Name是索引，如果使用select Id,Name from Table在索引项就直接返回了，如果使用select * from Table当查询其他字段时就需要使用主键索引去获取数据，产生了多余的回表操作。

覆盖索引：可以考虑将查询的列创建组合索引，避免回表。

索引最左匹配原则

假如创建了name,age,address的索引，B+Tree结构是严格按照索引顺序去执行。

//使用到索引了Select * from user where name = ? AND age = ? AND address = ? //使用到索引了Select * from user where name = ?//使用到了索引但是只用到name的索引了Select * from user where name = ? AND address = ? 

复制

mysql索引面试题

1.mysql为什么不用二叉搜索树和平衡二叉树？

二叉搜索树相当于一个链表，极端情况，查询最后一条数据会遍历整个表，mysql每个节点的操作就是对磁盘的一个I/O操作，而平衡二叉树虽然避免了极端情况，但是一个节点只能保存一个元素，这样就会导致每一个节点保存的数据比较少，I/O操作增多，影响性能。

2.mysql为什么用B+tree,不用B-Tree?

1)叶子节点有指针关联，当进行排序和范围查找时，效率也会更高，它不会查询所有的节点，这样基于索引的扫表就会更优，基于索引的排序也会更优。

2)子节点中不保存数据信息，只保存标识信息和指针信息，这样在同一个page结构中保存的数据就会更多，减少磁盘I/O。

3.mysql为什么不选择使用B-Tree?

根据计算，3层的B-Tree树保存的数据还是很少，数据从小到大依次分布在数的不同层级中，进行范围查找时，获取范围越大，获取的节点就越多。

极端情况下，相当于遍历了整棵树，节点越多获取的次数就越多，I/O操作就会越多，这样性能就会遇到瓶颈。

4.mysql为什么不建议用uuid当主键?

5.为什么建议主键ID是递增的，和B+Tree有什么关系？

1) 因为B+Tree在创建索引是按照顺序从小到大创建的，并且把相临的节点放置在同一个page中，保证一个page的充分利用，减少分叉(也就是减少了检索次数)。

2) UUid是没有任何规律的，造成了Page的浪费，Btree会因为存储结构不合理，导致节点增多，所以不会用UUid当主键。

6.为什么不建议使用select * from Table语句查询数据？

有Id,Name,Age等等字段，Id和Name是索引，如果使用select Id,Name from Table在索引项就直接返回了，如果使用select * from Table当查询其他字段时就需要使用主键索引去获取数据，产生了多余的回表操作。

7.为什么Innodb引擎要求一定要建立主键索引？

这是由Innodb特殊引擎结构决定的，Innodb引擎数据存储在主键ID下面

8.索引最左匹配原则

假如创建了name,age,address的索引，B+Tree结构是严格按照索引顺序去执行。

//使用到索引了Select * from user where name = ? AND age = ? AND address = ? //使用到索引了Select * from user where name = ?//使用到了索引但是只用到name的索引了Select * from user where name = ? AND address = ? 

复制