一. 存储引擎的数据结构

1. B树（B-树）

B树是2-3树的一种扩展，对于M阶(M就是树的高度，比如下图为一个四阶的树)的B树来说：

（1）根节点至少有两个子节点

（2）每个节点至多有M-1个key，以升序排列，以及Nk+1个指针，其中Nk代表key的数量。

（3）对于一个key1来说，它左侧的指针指向的子节点的key值<=key1,右侧子指针指向的子节点的key值>key1（详见下图）

（4）其他节点至少有M/2个子节点

关于B树中插入节点的过程，在下面这个博客中有一个动图解释的很详细：

http://www.cnblogs.com/yangecnu/p/Introduce-B-Tree-and-B-Plus-Tree.html

他的插入过程和红黑树很相似，总结一下就是：

（1）当要插入一个新值时，首先根据第三条原则找到他在叶子节点的位置并插入

（2）如果当前叶子节点的key数目等于M，那么就要拆分，拆分的过程就是把所有key通过一个中间值（如M=4取第二个数，M=5取第三个数），分成相同的两份（如果M是偶数会相差一），然后中间数为父节点，两边的树作为左右子节点，但要注意中间数是插入到他们的父节点中的，而不是新生成一棵树，这也就意味着如果这时候父节点的key树等于M，那么就要通过相同的变换把key值接着向上传递，直到key数<M。

2. B+树

存储引擎常用的一种数据结构，一种多叉平衡查找树，特点（对于M阶的B+树）：

（1）除叶子结点外所有节点都有M个键以及M个指向子节点的指针。

（2）所有叶子节点都在同一层 

（3）非叶子结点的子树指针与关键字（Key）个数相同； 

（4）非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）； 

（5）为所有叶子结点增加一个链指针； 

（6）所有关键字（key）都在叶子结点出现；，因此所有查找只会在叶子结点命中

结构如下图所示：

相比B树的优点：

（1）支持范围查找

（2）遍历更方便

（3）节省空间：因为B+树只有叶子节点才存数据，因此内部节点不需要只想关键字具体信息的指针。

（4）所有查询操作都需要命中子节点，所以是相同的。

PS: B*树就是在B+树基础上，为非叶子结点也增加链表指针

二. MyISAM引擎

不支持事务

支持表级锁（MySql支持两种表级锁，表共享读锁和表独占写锁），但不支持行级锁

存储表的总行数

一个MyISAM表有三个文件：索引文件（.MYI），表结构文件(.frm)，数据文件(.MYD)

采用非聚集索引：即索引文件和数据文件是分开的，索引文件的数据域存储指向数据文件的指针

跨平台应用更方便（表保存为文件形式）

支持三种不同的存储格式：

（1）静态表：存储迅速，容易缓存，出现故障容易恢复；但是占用内存多，因为会按列宽度补足空格

（2）动态表：占用空间少，但是频繁更新和删除容易产生碎片，需要定期整理（OPTIMIZE TABLE），并且出现故障难以恢复。

（3）压缩表：占据的磁盘空间非常小（每个记录被单独压缩，所以访问开支很小）。

三. InnoDb引擎

支持事务

支持行级锁（仅在条件语句中包括主键索引时）

内存使用率低

查询效率和写的效率更低

采用聚集索引，索引和数据存在一起，叶子结点直接存的是数据。

支持外键

注：MyISAM在查询时的性能比InnoDB高，因为它采用的辅索引和主键索引类似，所以通过辅索引查找数据时只需要通过辅索引树就可以查找到，而InnoDB需要先通过辅索引查找到主索引，再通过主索引树查找到数据。

四. MEMORY

只对应一个磁盘文件.frm，用来存储表结构

访问速度非常快，因为他的数据存在内存中，但是一旦服务关闭，数据就会丢失

可以指定Hash索引或BTREE索引

默认存储数据大小不超过16MB，但可以调整

应用场景：比如作为统计操作的的中间结果表，便于高效地对中间结果分析并得到最终结果。

五. MERGE

一组MyISAM表的组合，这些MyISAM表结构必须完全相同

对MERGE表的操作实际上是对其子表进行的

可以通过指定INSERT_METHOD=LAST来制定插入数据的表（这里指定为最后一个表）

参考：

[1] 《深入浅出MySQL》

[2] 平衡查找树之B树：http://www.cnblogs.com/yangecnu/p/Introduce-B-Tree-and-B-Plus-Tree.html

[3] B树，B+树，B*树：https://www.jianshu.com/p/db226e0196b4