本文共 2712 字，大约阅读时间需要 9 分钟。
客户端-》【缓存-》语法解析器-》查询优化器-》查询执行引擎】-》索引和数据
索引是辅助存储引擎高效获取数据的一种数据结构，索引是数据的目录，便于搜索引擎快速定位数据
数据结构: B+ tree、Hash、Full-text索引
物理存储：聚簇索引和二级索引（辅助索引）
字段特性：主键索引、唯一索引、普通索引、前缀索引
字段个数： 单列索引和联合索引（复合索引）
| InnoDB | MyISAM | Memory | |
|---|---|---|---|
| B+tree 索引 | Yes | Yes | Yes |
| Hash索引 | No | No | Yes |
| Full-text索引 | Yes | Yes | No |
相对于B-tree，B+tree只在叶子节点存储数据，而B-tree的非叶子节点也存储数据，索引B+tree单个节点的数据量更小，在相同的磁盘I/O次数下，能查询更多的节点，另外我们注意到B+tree叶子节点采用单链表连接，适合MySQL中常见的基于范围的顺序检索场景，而B-tree无法做到这一点。
对于有N个叶子节点的B+tree，其搜索复杂度为O(logdN)，其中d(degree)为B+tree的度，表示节点允许的最大子节点个数为d个，在实际的运用过程中d值是大于100的，即时数据达到千万级别时B+tree的高度依然维持在3-4左右，保证了3-4次磁盘I/O操作就能查询到目标数据，而从红黑树的示意图中，可以看到红黑树是二叉树，节点的子节点个数为两个，意味着其搜索复杂度为O(logN)，比B+tree树高出不少，因此红黑树检索到目标数据所需的磁盘I/O次数更多。
范围查询是MySQL中常见的场景，Hash表不适合做范围查询，它更适合做等值查询，另外Hash表还存在Hash函数选择和Hash值冲突等问题（因为这些原因，B+树索引要比Hash表索引有更广的适用场景）
InnoDB表的索引按叶子节点存储，是否为完整表数据分为聚餐索引和二级索引，全表数据就是存储在聚簇索引中的，聚簇索引以外的索引叫做二级索引，我们结合实际的例子来介绍下这两类索引，在测试数据库中创建一个包含销售员信息的测试表workers。
CREATE TABLE `workers` ( `id` int(11) NOT NULL AUTO_INCREMENT COMMENT '员工工号', `name` varchar(36) NOT NULL COMMENT '员工名字', `sales` int(11) DEFAULT NULL COMMENT '员工销售业绩', PRIMARY KEY(`id`)) ENGINE = INNODB AUTO_INCREMENT=10 DEFAULT CHARSET=utf8;
插入数据：
insert into workers(id, name, sales) values (1, 'Georgi', 12744);...
在这个例子中workers表的聚簇索引建立在字段id上的，它的B+tree的示意图是这样的。聚簇索引的每个叶子节点存储了一行完整的表数据，叶子节点间采用单向链表按id列递增连接，可以方便的进行顺序检索。（InnoDB表必须要有聚簇索引，默认在主键字段上建立聚簇索引，在没有主键字段情况下，表的第一个NOT NULL的唯一索引被建立为聚簇索引，在前两者都没有的情况下，InnoDB将自动生成一个隐式递增id并在此列上建立聚簇索引）。
在name字段上添加二级索引：
ALTER TABLE `workers` ADD INDEX index_name(`name`);
二级索引的示意图可以看出，二级索引的叶子节点并不存储一行完整的表数据，而是存储了聚簇索引所在的列的值，业务就是workders表中的id列的值。
由于二级索引的叶子节点不存储完整的表数据，索引当通过二级索引查询到聚簇索引列值后，还需要回到聚簇索引也就是进一步获取数据。
select * from workers where name='Parto'
这条语句中，在二级索引index_name中查询到主键id=3，接着需要带着id=3这个条件，进一步回到聚簇索引查询后获取到完整的数据，很显然回表需要额外的B+tree搜索过程，必然增大查询耗时。需要注意的是，通过二级索引查询时，回表不是必须的过程，当query的所有字段在二级索引中能够查找到时，就不需要回表。MySQL称此时的二级索引为覆盖索引或者触发了索引覆盖。
select id, name from workers where name='Parto';
通过explain命令查看这条SQL的执行计划，可以看到Extra中使用了Using index，表名查询触发了二级索引index_name的索引覆盖。
对比如下语句：
explain select id, name, sales from workers where name='Parto';
可以看到Extra中显示的是NULL，并没有Using index，表明没有触发索引覆盖，需要回表查询。
对字符类型字段的前几个字符或对二进制类型字段的前几个bytes字段建立的索引而不是在整个字段上建立索引。
create index index_name on persons (name(5)) comment '前缀索引';
例如可以对persons表中的name(varchar(16))字段，name字段的前5个字段建立索引，通过命令show index from persons，可以看到索引信息中的索引key的Sub_part中的长度为5。前缀索引可以建立的类型有：char、varchar、binary、varbinary的列上，可以大大减少索引占用的存储空间，也能提升索引的查询效率。
MyISAM中不存在聚簇索引的表，MyISAM中的主键索引和非主键索引的结构是一样的，从图中可以看出他们的叶子节点是不存储数据的，存放的是表数据的地址，索引MyISAM表可以没有主键，MyISAM表的数据和索引是分开的，是单独存放的。
MyISAM表中的主键索引和非主键索引的区别，仅在于主键索引B+tree上的key必须符合主键的限制，非主键索引B+tree上的key只要符合相应字段的特性就可以了。
转载地址：http://kmomi.baihongyu.com/