（一）mysql中普遍使用B+Tree做索引，但在实现上又根据聚簇索引和非聚簇索引而不同。

①聚簇索引：指主索引文件和数据文件为同一份文件，聚簇索引主要用在Innodb存储引擎中。在该索引实现方式中B+Tree的叶子节点上的data就是数据本身，key为主键，如果是一般索引的话，data便会指向对应的主索引。

    在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

②非聚簇索引：指B+Tree的叶子节点上的data，并不是数据本身，而是数据存放的地址。

并不是数据本身，而是数据存放的地址。主索引和辅助索引没啥区别，只是主索引中的key一定得是唯一的。主要用在MyISAM存储引擎中，如下图：

非聚簇索引比聚簇索引多了一次读取数据的IO操作，所以查找性能上会差。

（二）MyisAM索引和InnoDB索相比较

①MyisAM支持全文索引（FullTEXT）、压缩索引，InnoDB不支持。

②InnoDB支持事务，MyisAM不支持。

③MyisAM顺序存储数据，索引叶子结点保存对应的数据行地址，辅助索引 和 主键索引相差无几；

    InnoDB主键节点同时保存数据行，其他辅助索引保存的是主键索引的值；

④MyisAM键值分离，索引载入内存（key_buffer_size），数据缓存依赖操作系统；

    InnoDB键值一起保存，索引与数据一起载入InnoDB缓冲池；

 ⑤MyisAM主键（唯一）索引按升序来存储存储，InnoDB则不一定；

 ⑥MyisAM索引的基数值（Cardinality，show index 命令可以看见）是精确的，InnoDB则是估计值。

      这里涉及到信息统计的知识，MyisAM统计信息是保存磁盘中，在alter表或Analyze table操作更新此信息，而InnoDB则是在表第一次打开的时候估计值保存在缓存区内。

 ⑦MyisAM处理字符串索引时用增量保存的方式，如第一个索引是‘preform’，第二个是‘preformence’，则第二个保存是‘7，ance’，这个明显的好处是缩短索引，但是缺陷就是不支持倒序提取索引，必须顺序遍历获取索引。