快速了解 B Tree ,B+Tree以及B+Mysql 中的作用

Mysql 索引机制（B树,B+树篇）

Mysql 优化是一个大型应用过程中十分重要的一个环节，大部分开发者在使用的过程中，都会采用 添加索引的方式提高数据库查询性能和效率问题。今天我们简单聊聊 mysql 中的B+索引。
索引是什么？
数据库索引是一个能够提升数据库查询效率的数据结构。
我个人理解，索引类似于 新华字典的目录，能够让用户快速查到到对应项内容。

我们都知道，按照冯诺依曼模型 计算机主要有 如下几个部分：

所有的数据都是存储于硬盘或者内存中，MySQL数据 也是不例外的，Mysql 的数据是存储服务器到硬盘上的，如图：是两个常用引擎的数据格式（InnoDB、MyISAM）：

Mysql 是一个关系型数据库，在检索数据的过程中， 它主要流程先根据关键字去索引文件中检索对应关键硬件存储地址，然后根据地址查到到对应的行数据。

下面看一下Mysql 常用索引的数据结构是什么？

AVL树

再说B树之前 先拿之前提及到AVL树做一个简单比较说明。

简单来说 AVL树的概念 ：自带平衡条件的二叉查找树（父节点 大于左节点，小于右节点），采用二分法的思路。
它的平衡条件：
它的左右两个子树的高度差的绝对值不超过1 【或者是一个空树】
如图是一个AVL树插入过程。

假设 通过AVL树作为Mysql 数据库中的索引。我们看看会出现什么问题：
蓝色：文件系统存储磁盘数据块
黄色：真正的行记录数据

我们主要从两方面分析：

• 查询加载
• 存储过程

假设 我们要查找 关键字为 45的数据，根据二叉树的特性 ，我们比较流程大致70–>40–>45
此时我们需要查询3次，因此每次需要加载磁盘块以及对应数据 ，也需要加载3次。因此会出现两个问题：

• 磁盘IO加载效率问题。由于每次都需要对磁盘进行IO操作，随着数据不断增大，树形结构高度会不断增高，导致每次将数据页加载到内存中比对的次数就会频繁增加 。
• 数据页利用率问题。每个蓝色代码块只能存储一个关键字，存储数据量太小，我们拿Mysql InnoDb 引擎来说一个数据页默认16K ，如果存储一个1K 的数据 还有15K数据白白资源浪费掉。针对上面两个问题 ，B树就对以上的问题做了一些优化调整。

B-树

B树 又称 多路平衡二叉树 如图【简图】
最主要特点：
B-树允许每个节点有更多的子节点

它将数据划分成4个部分

可以看出
B树结构 有2个特点：

1. 岔路数 =存储的关键字+1
2. 相同高度的树形结构存储更多关键字节点

优势
每次插入数据时 都会优先加载磁盘数据 然后读取对应关键字进行二分比对插入，由于每个磁盘块能够存储更多【关键字、关键字的数据区等】，就能充分的利用磁盘I/O 率。
举一个例子：假设innodb 一个数据块 是10KB ，一个关键字（带数据和引用）是10byte，B数一个根节点数据块就能存储 100个关键字，树高为3的B树 最后一层就能存储大约 100^3关键字。

如图是B树结构的插入流程：

B树不足点：
我先拿 个人理解 先拿mysql 举例：
如上图，假设我要获取0007 的对应数据，此时系统需要加载磁盘需要加载4次，加载顺序
9–》4–》6–》7
每次加载磁盘数据块都会多加载一部分数据【这部分数据 9–》4–》6 的数据区】 ，其实这部分数据区 如果没有被需要 是没有必要加载到系统中去的。产生一些额外I/O开销。
PS：这个需要说一下，假设一开始 直接查找0009 那就直接可以获取到对应值。 也可以说是优点，但是 相比B+平均查找效率 还是存在不足的

B+树

B+树主要特点：

1. 根节点、枝叶节点 不保存数据区。
2. 叶子结点才保存数据区
3. B+TREE 关键字的搜索采用的是左闭合区间 X值 范围 【1,25) , 【25,50),【50,75)，【75，∝）
4. 叶子结点关键字采用双向链表结构

优势：

1. 由于根节点、枝叶节点 不保存数据区，因此IO效率是高于B树结构
2. 基于索引扫描秒性能高于B树，B+ 树只需要扫描 叶子结点。
3. 双向链表结构 排序能力更强。

B+索引在不同引擎中存储

Myisam引擎索引模型

Myisam 索引 存储在MYI 文件中，假设我们给Myisam 增加一个主键ID 同时先将主键设置为B+ 树索引。 Myisam 将主键 形成一个B+树 ，叶子结点为存储硬件地址。并将索引结构存储于MYD 文件中。需要注意是：每增加一个索引列（比如name）也会形成一个B+树，两个索引没有主次之分。与InnoDB 引擎不同。


InnoDB 的索引模型
我们看一下mysql 5.7 官方文档解释：


InnoDB 引擎 中的索引采用两类：

• clustered index 主要存储 叶子节点存的是整行数据
• secondary index 每个记录都包含该行的主键列以及为secondary index指定的列

如图：

InnoDB 引擎 采用这两种索引机制 会导致一个小问题：
我们用一个学生表

同时创建两个B+索引，一个主键（ID、一个学生stuNo编号( ABC 标识)， 因此引擎会创建两个B+索引树，
假设我们根据 ”select * from Student where suNo= A “进行搜索 的时候 大致流程：

1. 先去secondary index 索引搜索出来 【有图】 对应关键字值 【假设9】
2. 由于 secondary index 特性 它只 每个记录都包含该行的主键列以及为secondary index指定的列的值 ，没有获取全部信息 ，因此mysql 需要再次从clustered index B+结构中获取查询一遍，直到找到对应数据的全部行记录值。

2 这个过程我们称之为 回表 回表是一个耗性能的操作。因此 ：

Mysql 不建议 select 语句 用 * 查询

如何避免回表呢？

采用覆盖索引：
定义 一个索引包含了（或覆盖了）满足查询结果的数据就叫做覆盖索引
还是上面的例子

select id from Student where stuNo= A     √
select id,stuNofrom Student where stuNo= A    √
select id,name from Student where stuNo= A   X
select stuNo from Student where stuNo= A     √
select * from Student where stuNo= A    X

最左前缀原则
B+ 树的索引结构采用的是最左前缀原则。
常用的情况主要体现三点：

1. where 模糊搜索过程 建议用 % 在最右边 ，最左边不要加%

   select id from Student where name like 'A%';  √
   select id from Student where name like '%A%';  X

2. 联合索引时候 最左原则 （常用字段、离散度高、存储小 依次排序）
3. 联合索引不是越多越好，建议根据业务模型选择

   select id,stuNo,name from Student where id=9 and stuNo= A √
   select id,stuNo,name from Student where sex='男' and id= 9  不建议 性别离散度比较小

第二个特点单独说说一下 存储小 原则：
学生表：创建两个索引 ，要求既要 联合查找 name,age 又要单个查找name或age，此时如何创建索引呢？
首先我们可以先创建一个 联合 index（name,age）索引，单个索引 我们可以比较name 和age 数据字节大小 age比较小 因此创建 index（age）
结论：
如果表里已经有联合索引 index（A,B） ，在创建单个索引index ©时，如果联合索引包含单个索引，优先考虑空间大小。

ICP原则（Index Condition Pushdown）
Mysql 5.6 以后引用 一个Mysql 优化，其目的减少 回表次数。提升性能

select * from Student where name like 'A%' and  age=10 and  sex='男';

联合索引 index（name,age）
没有启用ICP
1、获取下一行，首先读取索引元组，然后使用索引元组查找并读取整个表行。

2、测试WHERE适用于此表的部分条件一条条取出来回表，直到查询到结果集。
启用ICP

1. 获取下一行的索引元组（而不是整个表行）
2. 测试WHERE适用于该表的部分条件，并且只能使用索引列进行检查。如果不满足条件，请转到下一行的索引元组。
3. 如果满足条件，请使用索引元组来定位和读取整个表行。
4. 测试WHERE 适用于此表的条件的其余部分。

Mysql 配置可以采用如下命令结果集关闭：

SET optimizer_switch = 'index_condition_pushdown=off';
SET optimizer_switch = 'index_condition_pushdown=on';

我们再看一下 B+插入过程：

上图 我们可以发现一个事情，如果当前插入的数据 是自增序列的话，只有右边的树形结构进行旋转变化，左侧并没有，
因此 Msql 主键建议 用自增序列，不建议UUID
自增主键的插入数据模式，正符合了我们前面提到的递增插入的场景。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。而有业务逻辑的字段做主键，则往往不容易保证有序插入，这样写数据成本相对较高。

这样就会有一个新的问题：那是不是只要任意长度递增纯数字就可以做主键呢？

答案：建议自增序列，假设 我们11位 手机号和自增序列多对比 ，14位手机号大致每个叶子节点11个字节左右，而如果用整型做主键，则只要 4 个字节，如果是长整型（bigint）则是 8 个字节。

主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小

总结

如果采用B+ 树做索引需要注意优化点如下：

1. Msql 主键建议用自增序列，不建议UUID ，不建议利用自增序列连续性 业务模型设计
2. Sql 语句 采用 最左前缀原则
3. where 模糊搜索过程 建议用 % 在最右边 ，最左边不要加%
4. 避免隐式转换，SQL语句中尽可能不要用Mysql 提供函数或者运算
5. 重建索引不建议 通过Add、drop 命令，建议用alter table T engine=InnoDB 减少空间大小