概述
在整个计算机运行系统里，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结构保存的数据条数：
代码语言：txt复制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结构是严格按照索引顺序去执行。
代码语言：txt复制//使用到索引了
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结构是严格按照索引顺序去执行。
代码语言：txt复制//使用到索引了
Select * from user where name = ? AND age = ? AND address = ?
//使用到索引了
Select * from user where name = ?
//使用到了索引但是只用到name的索引了
Select * from user where name = ? AND address = ? 
