摘录： http://blog.coding labs.org/articles/theory-of-MySQL-index.html
在MySQL中，索引是存储引擎级别的概念，索引的实现方式因存储引擎而异。 本文主要介绍如何为两个存储引擎实现索引： MyISAM和InnoDB。
MyISAM索引的实现
MyISAM引擎使用B Tree作为索引结构，叶节点的data域中存储有数据记录的地址。 下图是MyISAM索引的原理图。
图8
这里假设表共有3列，以Col1为主键，图8是MyISAM表的主索引(Primary key )的图像。 可以看到，MyISAM索引文件只存储数据记录的地址。 在MyISAM中，“主索引”和“次索引”在结构上没有差异。 但是，key在主索引中必须是唯一的，并且次索引中的key可以重复。 如果在Col2中创建了辅助索引，则该索引的结构如下图所示。
图9
同样，B Tree，data域是保存数据记录的地址。 因此，MyISAM中的索引检索算法首先按照B Tree检索算法来检索索引，如果存在指定的Key，则取出该data域的值，将data域的值作为地址，相应地
MyISAM的索引方法也称为“非聚合”，但这样做是为了区别于InnoDB的聚合索引。
InnoDB索引的实现
InnoDB也使用b树作为索引结构，但具体实现方式与MyISAM完全不同。
第一个最大的区别是InnoDB数据文件本身就是索引文件。 如您所知，MyISAM索引文件和数据文件是分离的，索引文件只存储数据记录的地址。 在InnoDB中，表数据文件本身是按b树组织的索引结构，该树的叶节点data域包含完整的数据记录。 因为此索引的key是数据表的主键，所以InnoDB表数据文件本身就是主索引。
图10
图10是InnoDB主索引(也是数据文件)的图像，显示叶节点包含完整的数据记录。 这样的索引称为聚合索引。 由于InnoDB数据文件本身是用主键汇总的，因此InnoDB要求表具有主键。 没有MyISAM也没关系。 如果未明确指定，MySQL系统将自动选择能够唯一标识数据记录的列作为主键。 如果不存在这样的列，MySQL将自动生成InnoDB表中的隐式字段作为主键。 此字段的长度为6字节，类型为长整形
与第二个MyISAM索引的区别在于，InnoDB的次索引data域包含相应记录的主键值，而不是地址。 也就是说，InnoDB中的所有次索引都将主键作为data域引用。 例如，图11是在Col3中定义的辅助索引。
图11
这里以英语字符的ASCII码为比较标准。 虽然聚合索引可以非常高效地使用主键进行搜索，但子索引搜索需要两次索引搜索：首先搜索子索引以获取主键，然后使用主键将记录检索到主键。
了解各种存储引擎的索引实现方法有助于正确使用和优化索引。 例如，如果知道InnoDB的索引实现，则很容易理解为什么主索引太长会导致次索引太大，因为所有次索引都引用主索引。 例如，使用非单调字段作为主键在InnoDB中不是一个好主意。 由于InnoDB数据文件本身是B Tree，因此使用非单调主键时，插入新记录时数据文件会频繁分裂和调整，以保持B Tree的特性，从而导致效率低下。 此外，建议使用自增加字段作为主键。