概述

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

(资料图)

索引的本质

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

二叉树

二叉树定义：

平衡二叉树定义：

B-Tree结构

特点:多叉(多阶)

元素个数计算：

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

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

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

16 * 16 * 16 = 4096

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

B+Tree

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

为什么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 = ? 

关键词：