在了解索引之前，先了解一下MySQL的两种最常见的存储引擎。

一、基础知识

1、MYSQL存储引擎–MyISAM与InnoDB

InnoDB和MyISAM是许多人在使用MySQL时最常用的两个表类型，这两个表类型各有优劣，视具体应用而定。

最常见的差别就是InnoDB支持事务处理和外键与行级锁。 MyISAM类型的表强调的是性能，其执行速度比InnoDB类型更快，但是不提供事务支持，而InnoDB提供事务支持以及外部键等高级数据库功能。

其他方面也有一些差别：

InnoDB不支持FULLTEXT类型的索引。
InnoDB 中不保存表的具体行数

也就是说，执行select count() from table时，InnoDB要扫描一遍整个表来计算有多少行，但是MyISAM只要简单的读出保存好的行数即可。注意的是，当count()语句包含 where条件时，两种表的操作是一样的。
对于AUTO_INCREMENT类型的字段，InnoDB中必须包含只有该字段的索引，但是在MyISAM表中，可以和其他字段一起建立联合索引。
DELETE FROM table时，InnoDB不会重新建立表，而是一行一行的删除。
LOAD TABLE FROM MASTER操作对InnoDB是不起作用的，解决方法是首先把InnoDB表改成MyISAM表，导入数据后再改成InnoDB表，但是对于使用的额外的InnoDB特性(例如外键)的表不适用。
InnoDB表的行锁也不是绝对的，假如在执行一个SQL语句时MySQL不能确定要扫描的范围，InnoDB表同样会锁全表，例如update table set num=1 where name like “%aaa%”

还有一种说法：

InnoDB行锁是通过给索引上的索引项加锁来实现的，因此InnoDB这种行锁实现特点意味着：只有通过索引条件检索数据，InnoDB才使用行级锁，否则，InnoDB将使用表锁！
两者索引的实现方式也不同，下面会单独分析

个人感觉，InnoDB更高级一点，支持事务外键和行级锁等特性，但是也牺牲了一定的性能作为代价，对于写入操作不是很频繁的，MyISAM可能更灵活一点。

参考的博客中给出了MyISAM的几点优势：

平台上承载的大部分项目是读多写少的项目，而MyISAM的读性能是比Innodb强不少的。
MyISAM的索引和数据是分开的，并且索引是有压缩的，内存使用率就对应提高了不少。能加载更多索引，而Innodb是索引和数据是紧密捆绑的，没有使用压缩从而会造成Innodb比MyISAM体积庞大不小。
从接触的应用逻辑来说，select count(*) 和order by 是最频繁的，大概能占了整个sql总语句的60%以上的操作，而这种操作Innodb其实也是会锁表的，很多人以为Innodb是行级锁，那个只是where对它主键是有效，非主键的都会锁全表的。

2、B-树与B+树

B-TREE就是B树，B+TREE就是B+树，后者是前者的变种。

B树的各种变种主要应用与操作系统中磁盘的读取，由于磁盘结构的特殊性，在读取数据时，磁头的定位到一页信息并读出的时间要比读出信息进行检查花的时间要多的多，所以应该尽量减少磁头的移动次数，而B树就是通过减少树的深度来做到这一点的。

2.1、B-TREE

B树是一种多路搜索树（并不是二叉的），一棵m阶的B 树：

定义任意非叶子结点最多只有M个儿子；且M>2；
根结点的儿子数为[2, M]；
除根结点以外的非叶子结点的儿子数为[M/2, M]；
每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
非叶子结点的关键字个数=指向儿子的指针个数-1；
非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
所有叶子结点位于同一层；

如：（M=3）

B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；

B-树的特点：

关键字集合分布在整颗树中；
任何一个关键字出现且只出现在一个结点中；
搜索有可能在非叶子结点结束；
其搜索性能等价于在关键字全集内做一次二分查找；
自动层次控制；

由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最低搜索性能为：

其中，M为设定的非叶子结点最多子树个数，N为关键字总数；

所以B树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题；

由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并；

2.2、B+TREE

B+树是B-树的变体，也是一种多路搜索树：其定义基本与B-树同，除了：

非叶子结点的子树指针与关键字个数相同；
非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B树是开区间）；
为所有叶子结点增加一个链指针；
所有关键字都在叶子结点出现；

如：（M=3）

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+树的特点：

所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
不可能在非叶子结点命中；
非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
更适合文件索引系统；

还有一种叫B*树，没有遇见过。

二、数据库索引

1、索引的定义

数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。它是用于提高数据库表数据访问速度的数据库对象。

优点：

通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
可以大大加快数据的检索速度，这也是创建索引的最主要的原因。
可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义。
在使用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间。
通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

缺点：

创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加。
索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。
当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，这样就降低了数据的维护速度。

2、索引的分类

从不同的角度，索引可以有很多种分类

2.1、索引的种类

从使用上，索引可以分为普通索引，唯一索引，主键索引与组合索引

普通索引：这是最基本的MySQL数据库索引，它没有任何限制

创建：

1	CREATE INDEX indexName ON mytable(username(length));

删除：
1
DROP INDEX [indexName] ON mytable;

唯一索引：它与前面的普通索引类似，不同的就是：MySQL数据库索引列的值必须唯一，但允许有空值。
- 创建：
  1
  CREATE UNIQUE INDEX indexName ON mytable(username(length))
- 创建表的时候直接指定：
  1
  CREATE TABLE mytable( ID INT NOT NULL, username VARCHAR(16) NOT NULL, UNIQUE [indexName] (username(length)) );
主键索引：它是一种特殊的唯一索引，不允许有空值。
- 一般是在建表的时候同时创建主键索引
  1
  CREATE TABLE mytable( ID INT NOT NULL, username VARCHAR(16) NOT NULL, PRIMARY KEY(ID) );
- 查看：
  1
  SHOW INDEX FROM mytable;
组合索引：

也叫复合索引：Mysql从左到右的使用索引中的字段，一个查询可以只使用索引中的一部份，但只能是最左侧部分。例如索引是key index (a,b,c)。可以支持a | a, b |a, b, c 3种组合进行查找，但不支持b, c进行查找。当最左侧字段是常量引用时，索引就十分有效。
- 创建：
  1
  create index idx1 on table1(col1,col2,col3)
- 查询：
  1
  select * from table1 where col1= A and col2= B and col3 = C
  这时候查询优化器,不在扫描表了，而是直接的从索引中拿数据，因为索引中有这些数据，这叫覆盖式查询，这样的查询速度非常快。

利用索引中的附加列，可以缩小搜索的范围，但使用一个具有两列的索引不同于使用两个单独的索引。复合索引的结构与电话簿类似，它首先按姓氏对雇员进行排序，然后按名字对所有姓氏相同的雇员进行排序。如果您知道姓氏，电话簿将非常有用，如果您知道名字和姓氏，电话簿则更为有用，但如果只知道名字而不知道姓氏，电话簿将没有用处。

关于复合索引的注意事项：

对于复合索引，在查询使用时，最好将条件顺序按找索引的顺序，这样效率最高：

1	select * from table1 where col1=A AND col2=B AND col3=D

如果使用` where col2=B AND col1=A` 或者 `where col2=B` 将不会使用索引

对一张表来说,如果有一个复合索引 on (col1,col2),就没有必要同时建立一个单索引 on col1;
如果查询条件需要,可以在已有单索引 on col1的情况下,添加复合索引on (col1,col2),对于效率有一定的提高
同时建立多字段(包含5、6个字段)的复合索引没有特别多的好处,相对而言,建立多个窄字段(仅包含一个,或顶多2个字段)的索引可以达到更好的效率和灵活性

2.2、索引的结构

按照索引的结构，可以分为聚集索引与非聚集索引：

聚集索引，表数据按照索引的顺序来存储的。对于聚集索引，叶子结点即存储了真实的数据行，不再有另外单独的数据页。一个表只能包含一个聚集索引。
非聚集索引，表数据存储顺序与索引顺序无关。对于非聚集索引，叶结点包含索引字段值及指向数据页数据行的逻辑指针，该层紧邻数据页，其行数量与数据表行数据量一致。

2.3、索引的实现

从实现方式上，索引分为：

B-Tree 索引
Hash 索引
Fulltext 索引
R-Tree 索引

三、索引的实现

在 MySQL 中，主要有四种类型的索引，分别为： B-Tree 索引， Hash 索引， Fulltext 索引和 R-Tree 索引。我们主要分析B-Tree 索引。

参考的博客中说了很多，但是并不是很赞同。按照我的理解，下面介绍的两个引擎的索引都是通过B+树实现的，因为每次查找都是到了叶子节点才找到最后的结果，区别只是在于叶子节点中到底有没有存放数据。

1、MyISAM的索引实现

MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。

1.1、主键索引

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM主键索引的原理图：

这里设表一共有三列，假设我们以Col1为主键，图myisam1是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。

1.2、辅助索引

这个辅助索引我觉得就是上面说的普通索引。

在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：

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

MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

2、InnoDB的索引实现

虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同.

2.1、主键索引

MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

2.2、辅助索引

InnoDB的所有辅助索引都引用主键作为data域。例如，下图为定义在Col3上的一个辅助索引：

普通索引中不会保存行的物理位置，而是保存主键的值，所以通过”二级索引”进行查找是先找到主键，再找到行，要进行二次索引查找。

3、对比

InnoDB索引和MyISAM索引的区别：

一是主索引的区别，InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。
二是辅助索引的区别：InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。

InnoDB 表是基于聚簇索引建立的。因此InnoDB 的索引能提供一种非常快速的主键查找性能。不过，它的辅助索引（Secondary Index，也就是非主键索引）也会包含主键列，所以，如果主键定义的比较大，其他索引也将很大。如果想在表上定义、很多索引，则争取尽量把主键定义得小一些。InnoDB 不会压缩索引。

文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白：

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