MyISAM中的索引方案

B树索引适用存储引擎如表所示：

索引/存储引擎	MyISAM	InnoDB	Memory
B-Tree索引	支持	支持	支持

tips MySQL官方只有B+树的概念，B树是国内的叫法，MySQL官方的B树即国内的B+树
即使多个存储引擎支持同一种类型的索引，但是他们的实现原理也是不同的。Innodb和MylISAM默认的索引是Btree索引;而Memory默认的索引是Hash索引。
MyISAM引擎使用B+Tree作为索引结构，叶子节点的data域存放的是数据记录的地址。

MyISAM索引的原理

下图是MyISAM索引的原理图。

我们知道InnoDB中索引即数据，也就是聚簇索引的那棵B+树的叶子节点中已经把所有完整的用户记录都包含了，而MyISAM的索引方案虽然也使用树形结构，但是却将索引和数据分开存储︰

​ ● 将表中的记录按照记录的插入顺序单独存储在一个文件中，称之为数据文件。这个文件并不划分为若干个数据页，有多少记录就往这个文件中塞多少记录就成了。由于在插入数据的时候并没有刻意按照主键大小排序，所以我们并不能在这些数据上使用二分法进行查找。

​ ● 使用MyISAM存储引擎的表会把索引信息另外存储到一个称为索引文件的另一个文件中。MyISAM会单独为表的主键创建一个索引，只不过在索引的叶子节点中存储的不是完整的用户记录，而是主键值＋数据记录地址的组合。

这里设表一共有三列，假设我们以col1为主键，上图是一个MyISAM表的主索引(Primary key)示意。可以看出MylSAM的索引文件仅仅保存数据记录的地址。在MylISAM中，主键索引和二级索引(Secondary key)在结构上没有任何区别，只是主键索引要求key是唯一的，而二级索引的key可以重复。如果我们在col2上建立一个二级索引，则此索引的结构如下图所示:

同样也是一棵B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为:首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

MyISAM与InnoDB对比

MyISAM的索引方式都是“非聚簇”的，与InnoDB包含一个聚簇索引是不同的。小结两种引擎中索引的区别：

①在InnoDB存储引擎中，我们只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录，而在MyISAM中却需要进行一次回表操作，意味着MylSAM中建立的索引相当于全部都是二级索引。
②InnoDB的数据文件本身就是索引文件，而MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。
③InnoDB的非聚簇索引data域存储相应记录主键的值，而MyISAM索引记录的是地址。换句话说，InnoDB的所有非聚簇索引都引用主键作为data域。
④ MyISAM的回表操作是十分快速的，因为是拿着地址偏移量直接到文件中取数据的，反观InnoDB是通过获取主键之后再去聚簇索引里找记录，虽然说也不慢，但还是比不上直接用地址去访问。
⑤InnoDB要求表必须有主键（MyISAM可以没有）。如果没有显式指定，则MysQL系统会自动选择一个可以非空且唯一标识数据记录的列作为主键。如果不存在这种列，则MysQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节，类型为长整型。

小结：

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助。比如：

举例1:知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有二级索引都引用主键索引，过长的主键索引会令二级索引变得过大。
举例2:用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一棵B+Tree，非单调的主键会造成在插入新记录时，数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。