B+Tree简介
基本概念
B+Tree是相比BTree的一种衍生体，最大的特点是叶子节点的数是通过链表进行关联起来
MySQL使用B+Tree的原因
Mysql是持久化的，数据和索引是存储在磁盘上的，每次的检索数据，需要从磁盘进行加载数据。磁盘的最小单位是扇区，扇区的大小只有512B的大小，操作系统通常一次会加载多个扇区的数据到内存中，操作系统最小的单位是块block，在Linux系统中block的大小通常为4KB，也就是说加载一个块的数据，默认是8个扇区的数据
每次的索引加载，都涉及到IO的操作，因为磁盘的IO越多，就会导致消耗的时间就会越长
满足MySQL的索引条件：
1、在尽可能少的IO中完成操作
2、要能高效的查找一个数据，也能高效的执行范围查找
B+Tree使用了二分查找，同时叶子节点为顺序排列，能够支持高效的范围查找
B+Tree的节点中只存储了索引数据，对于原data则存储在叶子节点中，更适合大量索引数据的检索；另一个重点是由于索引 文件都是存放在一个节点里面，对应相同的扇区，磁盘在进行预加载的时候，会把相邻的扇区的数据一起进行加载到内存中，这样在进行数据查找的时候更容易找到相邻扇区的索引数据，提升检索速度，减少了IO的操作
B+Tree特点
- 一棵M阶的树，每个分支节点，最多有M棵子树，比如一棵3三阶的树，每个分支节点最多只有三个子女
- 根节点最少两课子树
- 每个节点都包含n个元素，其中 m/2 <= n <= m
- 每个节点的元素大小都是从小到大依次排序
- 所有叶子节点都处于相同一层
- 每个叶子节点的元素大小都是从小到大依次排列，通过指针链接，形成有序链表
B+Tree的查找
B+Tree查找的时候，先去根节点找，然后会自上而下的进行查找，最终找到匹配的叶子节点，
比如查找51，在根节点中发现小于59，则继续在左边子树查找，依次发现比44大，比59小，则在59的子树中进行查找，定位到51（这里由于每一层的节点都是有序排列的，所以很容易定位到51具体在哪个子树上面）
B+树中间节点没有Data数据，所以同样大小的磁盘页可以容纳更多的节点元素。所以数据量相同的情况下，B+树比B树更加“矮胖“，因此使用的IO查询次数更少。
B+Tree的插入
- 所有的插入都是最终体现在叶子节点上面，且叶子节点的顺序是不能够被打乱的
- 如果插入的元素之后，当前节点的元素个数大于M，则需要对当前节点进行拆分处理，具体情况分为一下几类
- 如果当前节点插入了新元素之后，节点内的元素个数小于等于M，则不需要进行拆分处理
- 如果当前接插入新元素之后，节点内的元素个数大于M，则需要将当前节点拆分为左右两个节点，同时需要将原始节点里面的中间的元素，上升放置到父节点里面去，如下图，插入元素37：
将37上升到父节点中，父节点中元素由[59，97]变为[37，59，97]
- 如果在第二步过程中，如果上移元素之后，父节点的元素个数大于M，则仍然需要进行元素拆分，方法跟第二步一样