索引是SQL优化中最重要的手段之一，本文从基础到原理，带你深度掌握索引。
一、索引基础
1、什么是索引
MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构，索引对于良好的性能非常关键，尤其是当表中的数据量越来越大时，索引对于性能的影响愈发重要。索引优化应该是对查询性能优化最有效的手段了。索引能够轻易将查询性能提高好几个数量级。
通俗来讲，索引类似文章的目录，用来提高查询的效率。
2、索引分类
常见的索引类型有：主键索引、唯一索引、普通索引、全文索引、组合索引
2.1、主键索引
当一张表，把某个列设为主键的时候，则该列就是主键索引
create table a (
id int primary key auto_increment,
name varchar(20) not null default ''
);
这里id就是表的主键，如果当创建表时没有指定主键索引，也可以在创建表之后添加：
alter table table_name add primary key (column_name);
1.2、普通索引
用表中的普通列构建的索引，没有任何限制
create index 索引名 on table_name(column1);
alter table table_name add index 索引名(column1);
1.3、全文索引
全文索引主要针对文本文件，比如文章，标题。在MySQL5.6之前，只有MyISAM存储引擎支持全文索引，MySQL5.6之后InnoDB存储引擎也支持全文索引。
create table c(
id int primary key auto_increment ,
title varchar(20),
content text,
fulltext(title,content)
) engine=myisam charset utf8;
insert into c(title,content) values
('MySQL Tutorial','DBMS stands for DataBase ...'),
('How To Use MySQL Well','After you went through a ...'),
('Optimizing MySQL','In this tutorial we will show ...'),
('1001 MySQL Tricks','1. Never run mysqld as root. 2. ...'),
('MySQL vs. YourSQL','In the following database comparison ...'),
('MySQL Security','When configured properly, MySQL ...');
1.4、唯一索引
见名知义，索引列中的值必须是唯一的，但是允许为空值。d表中name就是唯一索引，相比主键索引，主键字段不能为null，也不能重复
create table d(
id int primary key auto_increment ,
name varchar(32) unique
)
1.5、组合索引
用多个列组合构建的索引，这多个列中的值不允许有空值。
ALTER TABLE 'table_name' ADD INDEX index_name('col1','col2','col3')；
组合索引遵循“最左前缀”原则，使用时最好把最常用作为检索或排序的列放在最左，依次递减。组合索引相当于建立了col1，col1col2，col1col2col3 三个索引，而col2或者col3是不能使用索引的。在使用组合索引的时候可能因为列名长度过长而导致索引的key太大，导致效率降低，在允许的情况下，可以只取col1和col2的前几个字符作为索引。
ALTER TABLE 'table_name' ADD INDEX index_name(col1(4),col2（3))；表示使用col1的前4个字符和col2的前3个字符作为索引
3、索引机制浅析
我们这里先简单剖析一下索引的机制，为接下来的深入做一些铺垫。
3.1、索引加快查询的原理
传统的查询方法，是按照表的顺序遍历的，不论查询几条数据，MySQL需要将表的数据从头到尾遍历一遍。
在我们添加完索引之后，MySQL一般通过BTREE算法生成一个索引文件，在查询数据库时，找到索引文件进行遍历，使用能够大幅地查询的效率的折半查找的方式，找到相应的键从而获取数据。
3.1、索引的代价
创建索引是为产生索引文件的，占用磁盘空间。索引文件是一个二叉树类型的文件，可想而知我们的DML操作((数据操作语言,对表记录的(增、删、改)操作)同样也会对索引文件进行修改，所以性能会相应的有所下降。
二、索引存储数据结构
上面已经说到，索引实际上是数据库中满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法 。
可能我们都知道，MySQL索引是B+树数据结构，当然，实际上索引还有哈希表、有序数组 等常见的数据结构。
1、哈希表
哈希表是一种以键-值（key-value）存储数据的结构，我们只要输入待查找的值即key，就可以找到其对应的值即Value。哈希的思路很简单，把值放在数组里，用一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置。
不可避免地，多个key值经过哈希函数的换算，会出现同一个值的情况。处理这种情况的一种方法是，拉出一个链表。
所以，需要注意，哈希表后的链表并不是有序的，区间查询的话需要扫描链表，所以哈希表这种结构适用于只有等值查询的场景，比如Memcached及其他一些NoSQL引擎。
2、有序数组
另外一个大家比较熟悉的数组结构，有序数组在等值查询和范围查询场景中的性能都非常优秀。
如果仅仅看查询效率，有序数组是非常棒的数据结构。但是，在需要更新数据的时候就麻烦了，你往中间插入一个记录就必须得挪动后面所有的记录，成本太高。
所以，有序数组索引只适用于静态存储引擎，比如你要保存的是2017年某个城市的所有人口信息，这类不会再修改的数据。
这两种都不是最主要的索引，常见的索引使用的数据结构是树结构，树是数据结构里相对复杂一些的数据结构，我们来一步步认识索引的树结构。
3、二分查找
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
查找方法：首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
上面提到的有序数组的等值查询和比较查询效率非常高，但是更新数据存在问题。
为了支持频繁的修改，比如插入数据，我们需要采用链表。链表的话，如果是单链表，它的查找效率还是不够高。
所以，有没有可以使用二分查找的链表呢?
为了解决这个问题，BST(Binary Search Tree)也就是我们所说的二叉查找树诞生了。
4、二叉查找树
二叉树具有以下性质：左子树的键值小于根的键值，右子树的键值大于根的键值。
如下图所示就是一棵二叉查找树，
在这种比较平衡的状态下查找时间复杂度是O(log(n))。
但是二叉查找树存在一个问题：在某些极端情况下会退化成链表。
同样是2,3,4,6,7,8这六个数字，如果我们插入的数据刚好是有序的，那它就变成这样