从B-tree与B+tree到MySQL
B-tree
我们可以将一个b树简单的理解成一个自平衡的m叉树，并将它称作m阶b树；同样的，如果你看了聊聊红黑树和跳表，也可以将一个二三树理解为是一个3阶B树。
对于一个m阶的红黑树来说：
- B树中所有节点的孩子节点数中的最大值称为B树的阶，记为m
- 树中的每个节点最多有m个子树
- 根节点如果不是终端节点，至少有两棵子树
- 除根节点外所有非叶节点都拥有m/2棵子树（m/2向上取整）
- 所有叶子都在同一层
形象的我们用一个4阶的b树与平衡二叉树来表示同一组数据：
从结构上来看，我们可以看到，b树较之于二叉树更加的扁平，而这意味着跨节点操作更加的少，当数据结构以节点粒度对数据进行落盘后，使用二叉树结构的查询对于磁盘的io次数有显著的优化（当数据节点读入后认为已拉入内存，后续读取磁盘io压力小）。
什么意思呢？ 当我们将这棵树以节点为单位存储到磁盘中，读取最远端的叶子数据需要的磁盘操作如下：
明显的，二叉树的读盘操作更加的频繁，在这样的场景下二叉树的性能必然是劣于b树的，这也是为什么数据库的索引结构更加多的采用b树及其变种而不使用二叉树的原因。
B+tree
而b+tree与b-tree有什么不同呢？看图说话：
明显的，所有的叶子节点可以组成一个完整的数据索引链表，我们可以便利的获取一段区间值的内容出来，这样的好处不仅仅是批量区间读取使得高效。根据局部性原理，通过这样的方式加载到内存中的数据有很大可能被后续的访问命中，从而减少后续的I/O操作。
对于MySQL
对于索引而言，B+并不是万能妙药。简单的思考就会发现问题:
- 对于B+树如何定阶，而定阶后树的深度如何把握？
- 对于频繁的操作，维护树的稳定而做的分裂与合并同样造成大量的I/O影响性能。
定阶
对于操作系统来说，将数据分页（又成block）可以加速磁盘读写，一般而言，我们每个节点占用的大小应小于等于一个页。通常的，linux下一个block大小约为4KB，那么可以推断出：
- 一个4B（Int）大小的索引，加上4B大小的子树节点指针，阶数关系有
m * (4 + 4) = 4 KB
易得阶数m=512，而此时对于亿级别的数据，最大深度约为log(512/2)(10^8) = 3.32 ~= 4
只有当数据激增至百亿时，深度才会至5。 - 一个32*8B(Varchar(32))大小的索引，加上4B大小的子树节点指针，阶数关系有
m * (32 * 8 + 4) = 4 KB
得阶数m~=16，而此时对于亿级别的数据，最大深度约为log(16/2)(10^8) ~= 9 ~= 9
以上，我们可以认为主键或索引不宜过长，或过长的索引数据级应该要小，不然主键过大导致树深度激增过快将大幅度的拉低性能。
维护稳定性
对于一个标准的B+树，在插入叶子节点而叶子节点无法容纳时，会触发平衡策略进行该叶子节点的分裂，而对于MySQL而言，为了减少I/O，策略上会选择新开一个独立叶子来存储新入的数据而不是对旧有数据进行分裂。
这就造成了索引不可以过分离散的问题，当索引值不连续，将开出非常多的独立叶子，而每个block内数据少的可怜，从而隐式的使B+树阶数退化进而深度激增影响性能。
这也是为什么使用这种策略的数据引擎(innodb)会推荐使用连续的自增id。