B+ 树是一种常用的经典数据结构。InnoDB 和 MyISAM的的数据结构就是基于B+树，因此这里对 B+ 树进行一次总结。
B+树是为磁盘或其他直接存取辅助设备而设计的一种平衡查找树，在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶节点中，各叶节点指针进行连接。
定义
B+ 树允许每个节点有M-1个子节点（M为树的阶层）。
- 根节点至少有两个子节点
- 每个节点有M-1个key，并且以升序排列
- 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
- 其它节点至少有M/2个子节点
下图为B+树的插入
B+ 树与 B 树的区别
B树的每个节点都存储了数据，并且叶子节点为null
B+树只有叶子节点存储数据，叶子节点包含了这棵树的所有键值，叶子节点不存储指针。
B+树增加了顺序访问的指针，每个叶子节点增加一个指向相邻叶子节点的指针。
B树是一个二叉结构的树，而B+树则是一个多叉树结构，使得这棵树相对来说更加“矮胖”。这样的优势是在查找时减少磁盘I/O的次数。相对于内存存取，磁盘I/O的消耗更高。
MyISAM 与B+树
MyISAM 引擎使用 B+树作为索引，叶节点的data域存放的是数据记录的地址。下图是MyISAM主键索引的原理图：
InnoDB 与 B+树
InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同
MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
InnoDB 表是基于聚簇索引建立的。因此InnoDB 的索引能提供一种非常快速的主键查找性能。不过，它的辅助索引（Secondary Index， 也就是非主键索引）也会包含主键列，所以，如果主键定义的比较大，其他索引也将很大。如果想在表上定义 、很多索引，则争取尽量把主键定义得小一些。InnoDB 不会压缩索引。
InnoDB索引和MyISAM索引的区别：
一是主索引的区别，InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。
二是辅助索引的区别：InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。
