一、什么是索引
索引用于快速找出在某个列中有一特定值的行。无索引的表，查询时，是按照顺序存储的方法扫描每个记录来查找符合条件的记录。不使用索引，MySQL必须从第一条记录开始读完整个表，直到找出相关的行，表越大，查询数据所花费的时间就越多，如果表中查询的列有一个索引，MySQL能够快速到达一个位置去搜索数据文件，而不必查看所有数据，那么将会节省很大一部分时间。索引主要目的是提高了数据库系统的性能，加快数据的查询速度与减少系统的响应时间 。
二、索引的本质
索引（Index）是帮助MySQL高效获取数据的数据结构。
数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找（linear search），这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找（binary search）、二叉树查找（binary tree search）等。如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
三、索引的存储机制
1、索引的分类
（1）从存储结构上划分：BTree索引（B-Tree或B+Tree）、Hash索引、full-index全文索引、R-Tree索引。描述的是索引存储时保存的形式。
MySQL默认存储引擎Innodb只显式支持B-Tree（技术上说是B+Tree）索引，对于频繁访问的表，Innodb会透明建立自适应Hash索引，即在B树索引的基础上建立Hash索引，可以显著提高查找效率，对于客户端是透明的，不可控制的，隐式的。
B-Tree索引：能加快数据的访问速度，因为存储引擎不再需要进行全表扫描来获取数据，数据分布在各个节点之中。
B+Tree索引：是B-Tree的改进版本，同时也是数据库索引所采用的存储结构。数据都在叶子节点上，并且增加了顺序访问指针，每个叶子节点都指向相邻的叶子节点的地址。相比B-Tree来说，进行范围查找时只需要查找两个节点，进行遍历即可。而B-Tree需要获取所有节点，相比之下B+Tree效率更高。
例子：假设有一张学生表，id（主键），name，birthday。
Hash索引：基于哈希表的实现，只有精确匹配索引所有列的查询才有效。对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（hash code），并且Hash索引将所有的哈希码存储在索引中，同时在索引表中保存指向每一个数据行的指针。
创建表和Hash索引
CREATE TABLE testhash(
fname VARCHAR(50) NOT NULL,
lname VARCHAR(50) NOT NULL,
KEY USING HASH(fname)
)
查看数据
SELECT * FROM testhash
假设索引的哈希函数f(x)
Hash表的数据结构
索引的编号是顺序的，但是数据行不是。
执行索引的查询：SELECT * FROM testhash WHERE fname='Peter'；MySQL先计算'Peter'的哈希值，并找对对应的记录指针（7437），最后比较是否为'Peter'，确保就是要找到的行。
Hash索引的限制：
- 只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行；
- 并不是按照索引值顺序存储的，所以无法用于排序；
- 不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的；
- 只支持等值比较查询，也不支持任何范围查询；
- 访问哈希索引的数据非常快，除非有很多哈希冲突（不同的索引列值却有相同的哈希值）。当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行；
- 如果哈希冲突很多的话，一些索引维护操作的代价也会很高。例如，如果在某个选择性很低（哈希冲突很多）的列上建立哈希索引，那么当从表中删除一行时，存储引擎需要遍历对应哈希值的链表中的每一行，找到并删除对应行的引用，冲突越多，代价越大。
- Hash 索引不支持多列联合索引的最左匹配规则；
- Hash 索引在任何时候都不能避免表扫描。（由于不同索引键存在相同 Hash 值，所以即使取满足某个 Hash 键值的数据的记录条数，也无法从 Hash 索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。）
自适应Hash索引
在B-Tree基础上创建一个伪哈希索引。这和真正的哈希索引不是一回事，因为还是使用B-Tree进行查找，但是它使用哈希值而不是键本身进行索引查找。需要做的就是在查询的WHERE子句中手动指定使用哈希函数。
例如：SELECT word,crc FROM word WHERE crc=CRC32('gnu') AND word='gnu'
（2）从应用层次上划分：普通索引、唯一索引、复合索引。（平时讲的索引类型一般是指在应用层次的划分）
- 普通索引：即一个索引只包含单个列，一个表可以有多个单列索引。
普通索引（由关键字KEY或INDEX定义的索引）的唯一任务是加快对数据的访问速度。允许被索引的数据列包含重复的值。
应该只为那些最经常出现在查询条件 （WHEREcolumn=）或排序条件（ORDERBYcolumn）中的数据列创建索引。
只要有可能，就应该选择一个数据最整齐、最紧凑的数据列（如 一个整数类型的数据列）来创建索引。
- 唯一索引：索引列的值必须唯一，但允许有空值。创建唯一索引的目的往往不是为了提高访问速度，而只是为了避免数据出现重复。
- 复合索引：多列值组成一个索引，专门用于组合搜索，其效果大于索引合并。
复合索引允许一个查询可以只使用索引中的一部分，但只能是最左侧部分。
例如：索引是key index (a,b,c). 可以支持a | a,b| a,b,c 3种组合进行查找，但不支持 b,c进行查找 。
复合索引的建立原则：
如果可能仅对一个列多次执行搜索，则该列应该是复合索引中的第一列。
如果对一个两列索引中的两个列执行单独的搜索，则应该创建另一个仅包含第二列的索引。
包含多个列的主键始终会自动以复合索引的形式创建索引，其列的顺序是它们在表定义中出现的顺序，而不是在主键定义中指定的顺序。
创建复合索引应当包含少数几个列，并且这些列经常在select查询里使用。
在复合索引里包含太多的列不会带来太多好处。而且由于使用相当多的内存来存储复合索引的列的值，其后果是内存溢出和性能降低。
复合索引对排序的优化：复合索引只对和索引中排序相同或相反的order by 语句优化。
同时存在多个单列索引和一个有多列的复合索引，怎么用索引
优化器会选择最优索引策略，可能只用一个索引，也可能将多个索引全用上！
但多个单列索引底层会建立多个B+索引树，比较占用空间，也会浪费一定搜索效率，故如果只有多条件联合查询时最好建联合索引！
（3）从数据的物理顺序与键值的逻辑顺序关系上划分：聚集索引、非聚集索引。
聚集索引和非聚集索引的根本区别是表记录的排列顺序和与索引的排列顺序是否一致，其实理解起来非常简单，举字典的例子：如果按照拼音查询，那么都是从a-z的，是具有连续性的，a后面就是b，b后面就是c， 聚集索引就是这样的，他是和表的物理排列顺序是一样的，例如有id为聚集索引，那么1后面肯定是2,2后面肯定是3，所以说这样的搜索顺序的就是聚集索引。非聚集索引就和按照部首查询是一样是，可能按照偏房查询的时候，根据偏旁‘弓’字旁，索引出两个汉字，张和弘，但是这两个其实一个在100页，一个在1000页，（这里只是举个例子），他们的索引顺序和数据库表的排列顺序是不一样的，这个样的就是非聚集索引。
索引是在MySQL的存储引擎层中实现的，而不是在服务层实现的。所以每种存储引擎的索引都不一定完全相同，也不是所有的存储引擎都支持所有的索引类型。因此MySQL数据库支持多种索引类型，如BTree索引，哈希索引，全文索引等等。为了避免混乱，本文将只关注于BTree索引，因为这是平常使用MySQL时主要打交道的索引，至于哈希索引和全文索引本文暂不讨论。
四、索引的语法
1、创建索引
ALTER TABLE table_name ADD INDEX index_name (column_list)
ALTER TABLE table_name ADD UNIQUE (column_list)
CREATE INDEX index_name ON table_name (column_list)
CREATE UNIQUE INDEX index_name ON table_name (column_list)
2、删除索引
DROP INDEX index_name ON table_name
ALTER TABLE table_name DROP INDEX index_name
3、查看索引
show index from table_name
五、索引的选择性原则
1、选择性高原则：索引列的基数越大，索引的效果越好。
基数是指不重复的索引值Cardinality与表记录数（#T）的比值：Index Selectivity = Cardinality / #T
显然选择性的取值范围为(0, 1]，选择性越高的索引价值越大，这是由B+Tree的性质决定的。
例如：SELECT count(DISTINCT(title))/count(*) AS Selectivity FROM employees.titles;
2、最左匹配原则
3、最少空间原则：关键字占用的空间越小，则每个节点保存的关键字个数就越多，每次加载进内存的关键字个数就越多，检索效率就越高。
六、索引的弊端
确实，索引能够极大地提高数据检索效率，也能够改善排序分组操作的性能，但有不能忽略的一个问题就是索引是完全独立于基础数据之外的一部分数据。假设在Table ta 中的Column ca 创建了索引 idx_ta_ca，那么任何更新 Column ca 的操作，MySQL在更新表中 Column ca的同时，都须要更新Column ca 的索引数据，调整因为更新带来键值变化的索引信息。而如果没有对 Column ca 进行索引，MySQL要做的仅仅是更新表中 Column ca 的信息。这样，最明显的资源消耗就是增加了更新所带来的 IO 量和调整索引所致的计算量。此外，Column ca 的索引idx_ta_ca需要占用存储空间，而且随着 Table ta 数据量的增加，idx_ta_ca 所占用的空间也会不断增加，所以索引还会带来存储空间资源消耗的增加。
七、索引失效的情况
1、使用不等于操作符(<>, !=)；
2、使用 is null 或 is not null；
3、使用函数；
4、比较不匹配的数据类型；
5、对于使用like的查询，查询如果是‘%aaa’不会使用到索引，‘aaa%’会使用到索引；
6、如果条件中有or，那么除非or条件都带有索引，否则还是会全表扫描；
7、如果列类型是字符串，那一定要在条件中将数据使用引号引用起来，否则不使用索引；
八、扩展
1、为什么索引结构默认使用B+Tree，而不是Hash、二叉树、红黑树？
二叉树：树的高度不均匀，不能自平衡，会出现线性链表的情况。查找效率由数据所处的深度，决定了搜索时的IO次数。并且节点存储的数据内容太少，没有很好利用操作系统和磁盘数据交换特性，也没有利用好磁盘IO的预读能力。
B-Tree：不管叶子结点还是非叶子节点，都会保存数据。这样导致在非叶子节点中能保存的指针数量变少，指针少的情况下要保存大量数据，只能增加树的高度，导致IO操作变多，查询性能变低。
Hash：虽然能快速定位，但是没有顺序，IO复杂度高。
红黑树：树的高度随着数据量增加而增加，IO代价高。
B+Tree的优势：根节点和支节点没有数据区，关键字对应的数据只保存在叶子节点中，并且叶子节点之间有指针相连接，是顺序排列的，扫库和扫表时，不需要遍历整棵树，只需要遍历他的所有叶子节点即可；所有根节点和支节点同样大小的情况下，保存的关键字要比B-Tree要多。
2、为什么官方建议使用自增长主键作为索引？
结合B+Tree的特点，自增主键是连续的，在插入的过程中尽量减少页分裂，即使要进行页分裂，页只会分裂很少一部分。并且能减少数据的移动，每次插入都是插入到最后。总之就是减少分裂和移动的频率。
插入连续的数据
插入不连续的数据
九、总结
1、MySQL使用B+Tree作为索引数据结构。
2、B+Tree在新增数据时，会根据索引指定列的值对旧的B+Tree做调整。
3、从物理存储结构上说，B-Tree和B+Tree都是以页（4k）来划分节点的大小，但是由于B+Tree中中间节点不存储数据，因此B+Tree能够在同样大小的节点中存储更多的key，提高查找效率。
4、影响MySQL查找性能的主要还是磁盘IO次数，大部分是磁头移动到指定磁道的时间花费。
5、MyISAM存储引擎下索引和数据时分离的，而InnoDB索引和数据存储在一起。
6、InnoDB存储引擎下索引的实现，（辅助索引）全部是依赖于主索引建立的（辅助索引中叶子节点存储的并不是数据的地址，而是主索引的值。因此，所有依赖于辅助索引的都是先根据辅助索引查找到主索引，根据主索引查数据的地址。）。
7、由于InnoDB索引的特性，如果主索引不是自增的（id作为主键），那么每次插入新的数据，都很可能对B+Tree的主键索引进行调整，影响性能。因此，尽量以自增id作为InnoDB的主索引。