在MySQL中，主要有四种类型的索引，分别是：B-Tree索引，Hash索引，Fulltext索引和R-Tree索引。我们主要分析B-Tree索引。
B-Tree索引是mysql数据库中使用最为频繁的索引类型，除了Archive存储引擎之外的其他所有的存储引擎都支持B-Tree索引。Archive引擎直到MySQL5.1才支持索引，而且只支持索引单个AUTO_INCREMENT列。
不仅仅在MySQL中是如此，实际上在其它的许多数据库管理系统中B-Tree索引也同样是作为最主要的索引类型，这主要是因为B-Tree索引的存储结构在数据库的数据检索中有非常出色的表现。
一般来说，MySQL中的B-Tree索引的物理文档大多都是以BalanceTree的构造来存储的，也就是全部实际需求的数据都存放于Tree的LeafNode(叶子节点)，并且到任何一个LeafNode的最短路径的长度都是完全相同的，因此我们大家都称作B-Tree索引。当然，可能各种数据库（或MySQL的各类存储引擎）在存放自己的B-Tree索引的时候会对存储结构稍加改造。如InnoDB存储引擎的B-Tree索引实际使用的存储结构实际上是B+Tree，也就是在B-Tree数据构造的基础上做了很小的改造，在每一个LeafNode上边出存放索引键的相关信息以外，还存储了指向与该LeafNode邻近的后一个LeafNode的指针信息（增强了顺序浏览指针），这主要目的是加速检索多个邻近LeafNode的效率考虑。
下面主要探讨MyISAM和InnoDB2个存储引擎的索引实现方式，MySQL索引在MyISAM和InnoDB存储引擎中的实现区别：
1.MyISAM索引实现：
1）主键索引：
MyISAM引擎使用B+Tree作为索引构造，叶节点的data域储存的是数据记录地址。下图是MyISAM主键索引的原理图：
这里设表一共有三列，假设我们以Col1为主键，图myisam1是一个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要求表必须有主键（MyISAM可以没有），要是没有显式指定，则MySQL系统将自动选择一个可以唯一标识数据记录的列作为主键，假如不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。
2）InnoDB的辅助索引
InnoDB的所有辅助索引都引用主键作为data域。比如，下图为定义在Col3上的一个辅助索引：
InnoDB表是基于聚簇索引建立的。因此InnoDB的索引能提供一种非常快速的主键查找性能。不过，它辅助索引（SecondaryIndex，也就是非主键索引）也会包括主键列，因此，如果主键定义的比较大，其他索引也将很大。如果要在表上定义、许多索引，则争取尽量将主键定义得小一些。InnoDB不会压缩索引。
文字符的ASCII码作为比较准则。汇聚索引这种实现方式促使按主键的搜索十分高效，可是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
不同存储引擎的索引实现方式对于规范使用和优化索引都非常有帮助，比如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，由于全部辅助索引都引用主索引，过长的主索引会令辅助索引变得太大。再比如，用非单调的字段作为主键在InnoDB中不是个好主意，由于InnoDB数据文件本身是一颗B+Tree，非单调的主键会导致在插进新记录时数据文件为了维持B+Tree的特点而频繁的分裂调节，十分低效，而采用自增字段作为主键则是一个很好的挑选。
MySQL索引在MyISAM和InnoDB存储引擎中的实现区别：
一是主键索引的区别，InnoDB的数据文件本来就是索引文档。而MyISAM的索引和数据是分开的。
二是辅助索引的区别：InnoDB的辅助索引data域存储相应记录主键的值而非地址。而MyISAM的辅助索引和主键索引没有多大区别。
