Mysql高可用高性能存储应用系列1 - 索引篇

概述

在整个计算机运行系统里，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 = ?