B+树在 MyISAM 和 InnoDB 的不同实现方式（图）
文章目录
1、MyISAM索引实现：
1）主键索引：
MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。
下图是MyISAM主键索引的原理图：
这里假设表一共有三列，假设我们以Col1为主键，上图是一个MyISAM表的主索引（Primarykey）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。
2）辅助索引（Secondarykey）
在MyISAM中，主索引和辅助索引（Secondarykey）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。
如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：
同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。
2、InnoDB索引实现
然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。
1）主键索引：
MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点 data 域 保存了完整的数据记录。 这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
InnoDB主键索引的示意图：
上图所示，InnoDB主键索引的叶节点包含了完整的数据记录（数据文件），这种索引叫做 聚集索引。
因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），
如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，
如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。
2）InnoDB的辅助索引
InnoDB的所有辅助索引都引用主键作为data域。 例如，下图为定义在Col3上的一个辅助索引：
InnoDB表是基于聚簇索引建立的。 因此InnoDB的索引能提供一种非常快速的主键查找性能。不过，它的辅助索引（SecondaryIndex，也就是非主键索引）也会包含主键列，所以，如果主键定义的比较大，其他索引也将很大。如果想在表上定义、很多索引，则争取尽量把主键定义得小一些。InnoDB不会压缩索引。
文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索 两遍索引 ：首先 检索辅助索引获得主键，然后 用主键到主索引中检索获得记录。
不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助。
例如，知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。
再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
3、总结，InnoDB索引和MyISAM索引的区别：
一是主索引的区别，InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。
二是辅助索引的区别：InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。
4、扩展
普通二叉搜索树当索引的劣势：
（1）每个节点占用的空间太少，不能很好的利用磁盘的预读性。
（2）数据不规律的话，很可能形成链表。
（3）频繁 IO。
B树 当索引机制相比于二叉树的优势和劣势：
（1）每个节点有关键字、数据区、子节点指针。
（2）每个节点存储的数据多，可以充分的利用预读性（mysql一个磁盘页默认是16KB）。
B+树 相比于B树的优势：
（1）因为每个节点不存数据区（内存地址）了，所有每个节点的度可以更多，这样树的高度可以变矮很多，更利于查找。
（2）数据区都在叶子节点存着，一条链表，在排序时更有优势。
（3）b+树的节点变换时，是分裂形式而不是b树的左旋转(右旋转)形式，效率高。
（4）但是B+树有个缺点，就是不论查什么数据都必须要遍历到叶子节点才可以拿到真实的数据地址。
MyISAM 和 InnoDB 的索引机制的不同：
（1）MyISAM 的索引和数据区是分成两个文件来分别存储的，InnoDB 的数据区是和主键索引放在一起的。
（2）MyISAM 的每个索引都是单独的一棵树，每个索引都存储有真实的数据区地址，而 InnoDB 只有主键索引树才存储有真实地址，而辅助索引树的叶子节点存储的是主键的关键字。
（3）MyISAM 每个索引树都可以独当一面，而 InnoDB 的辅助索引树就算找到了对应的关键字，也还是要到叶子节点拿到主键的关键字，然后再去主键索引树遍历。
（4）MyISAM 没有默认的主键索引，而 InnoDB 有默认的主键索引（聚集索引）（不明确指定的情况下），InnoDB 除了主键索引是聚集索引，其他都是非聚集索引。