数据库和索引的关系就像新华字典和目录的关系一样，索引存在的目的就是为了提高数据查询效率。索引其实就是一种数据结构，存储引擎能通过索引能快速找到你想要的数据。尤其是当下海量数据存储的情况下，索引的使用显得尤为重要。索引能大大减少磁盘扫描的数量，可以将随机IO变为顺序IO，避免排序，高效的索引能将查询性能提升N多倍，今天我们就说一说关于”索引”的那些事。
B+Tree
Innodb的索引是B+Tree结构，B+Tree是比较经典的数据结构，它也是由二叉树、平衡二叉树、B-Tree演变过来的，它的定义在一些数据结构或者算法编程的书中都能找到，推荐一个网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html，
这里可以演示各种数据结构insert、delete、find的过程，这里不在赘述，只说下特点和优势。
特点：
B+Tree的节点可以拥有多于两个子节点。
所有的数据都保存在叶子节点，这也是区别于B-Tree结构的主要特点。
非叶子节点只包含索引。
叶子节点按照关键字从左至右顺序排列。叶子节点之间通过指针相连，形成一个双向链表。
所有非叶子节点元素同时存在于叶子节点，在叶子节点中是最大或者最小的元素。
优势：
由于非叶子节点只存储索引，所以每个页中可以存储更多的元素，这样B+Tree就会更加”矮胖”，这样树的层次就会更低，IO次数更少。
叶子节点通过双向链表连接，范围查询更方便。
所有查询都要从根节点查询到叶子节点，查询性能稳定，因为只有叶子节点存储了对应值。
注意：B+树索引找到的并不是具体某行数据，而是数据所在的页。我们都知道当SQL要修改某行数据时需要把要修改的数据从磁盘拿到内存中，在内存中进行修改，但是却不一定知道拿到内存中的数据并不是某行数据而是数据所在的页，InnoDB 的数据是按数据页为单位来读写的。
关于B+Tree索引的分类
我们先建一个表
CREATE TABLE `t` (`id` int(11) NOT NULL,`age` int(11) NOT NULL,`name` varchar(20) NOT NULL,`addr` varchar(60) NOT NULL,PRIMARY KEY (`id`),KEY `age` (`age`)) ENGINE=InnoDB复制
插入数据,部分数据如下：
mysql> select * from t limit 7;+----+-----+------+--------------------+| id | age | name | addr |+----+-----+------+--------------------+| 5 | 37 | tom | 山东省济南市 || 8 | 17 | jim | 深圳市 || 10 | 30 | hack | 北京市海淀区 || 20 | 23 | jack | 上海市 || 21 | 50 | lili | 江苏南京 || 23 | 41 | lucy | 重庆市 || 25 | 39 | hm | 湖北武汉 |+----+-----+------+--------------------+复制
聚簇索引其实就是每个表按照主键顺序构建的B+Tree，这棵树的叶子节点存放的是整张表的记录数据，所谓聚簇的意思也是指索引和数据行比较紧凑的存储在一起。一张表只有一个聚簇索引，如果这张表没有显式的创建主键，那么innodb会选择第一个唯一非空索引作为主键，如果连唯一非空索引也没有，innodb会隐式的给该表生成一个6字节的rowid作为主键。
本例中聚簇索引展示如下：根据主键id构建的B+树，叶子节点中包含了索引和行数据（data）。
非聚簇索引就是二级索引，也叫普通索引、辅助索引，普通索引的叶子节点中不包含数据行，只包含自身的索引和主键的值，拿着主键值就能到聚簇索引中查询到我们需要的数据行。
本例中二级索引就是用age构建的B+Tree，其中叶子节点保存的是主键的值。
联合索引是指对表上的多个列进行索引，并且是按照索引定义里面出现的字段顺序排序的。联合索引的使用必须遵循最左原则。
首先我们先说一下什么是最左原则。
还是上面的t表，我们做些修改，删除之前的(age)索引，新增一个联合索引(age,name)。
alter table t drop index age;alter table t add index idx_age_name(age,name);复制
#注意再多插入一些其他数据，不然数据太少的话，引擎会认为走全表扫描比走索引更快。
最左原则，是指一条查询可以只使用索引的一部分，但是必须从最左侧开始使用。
比如刚才创建的t1表，下列查询是可以用到索引的：
select * from t where age='30';select * from t where age like '3%';select * from t where age='17' and name='tom';select * from t where age='17' order by name;复制
下列这些查询是无法使用索引的：
select * from t where name='jim'; #未使用索引最左侧的索引列aselect * from t where age like '%7';#范围查找时%不能放在前面select * from t where left(age,1)=3;# 索引列不能是表达式的一部分，也不能作为函数的参数，否则无法使用索引查询select * from t where age=30 or name='hm';#尽量避免使用or关键字，多列查询可以使用union进行关联。复制
按照最左原则使用索引能提高SQL的查询性能，我们要把哪个字段放在最左侧呢？
选择索引的顺序基本遵循以下2个原则：
首先考虑的是经常用于排序和分组查询的字段，这样就避免了内存排序和随机I/O。
在不考虑排序和分组的情况下，建议将选择性高的字段放到最左侧。
索引的选择度可以用选择度百分比来衡量，选择度百分比可以用以下公式计算，比值越接近1说明选择度越好，如果该字段的的选择度超过33%，则认为是比较高效的索引。
select count(distinct a)/count(*) from t1复制
如何利用索引的排序功能？
前面我们说过索引是经过排序的，那我们如何利用索引列的排列顺序呢？我们新建一个表t1,建立联合索引（a,b）,建表语句如下：
CREATE TABLE `t1` (`a` int(11) NOT NULL,`b` int(11) NOT NULL,`c` int(11) NOT NULL,KEY `idx_a_b` (`a`,`b`)) ENGINE=InnoDB复制
表数据如下，注意再多插入一些其他数据，不然数据太少的话，引擎会认为走全表扫描比走索引更快。：
select * from t1 limit 6;+---+---+---+| a | b | c |+---+---+---+| 1 | 1 | 1 || 2 | 1 | 2 || 2 | 2 | 3 || 3 | 1 | 4 || 3 | 2 | 5 || 3 | 3 | 6 |+---+---+---+复制
下图这颗B+Tree是联合索引 idx_a_b(a,b)
这颗树是按照（a,b）进行排序的，当SQL语句是select * from t1 where a=3 order by b时不需要再进行排序，通过上图可以看出当a=3时b的值是已经是按照（1,2,3）的顺序排列好的。但是如果直接使用select * from t1 where c=3 order by b的话通过执行计划能看到Using filesort，就无法利用索引排列好的顺序。
想利用索引的排序功能，要满足以下条件：
ORDER BY子句后的列顺序要与组合索引的列顺序一致，且所有排序列的排序方向(正
序/倒序)需一致。
所查询的字段值需要包含在索引列中，要满足覆盖索引的使用条件。
我们来举几个例子来说明下，大家可以在自己的测试环境进行验证：
可以使用索引的排序功能的查询：
select a,b from t1 order by a;select a,b from t1 order by a,b;select a,b from t1 order by a desc,b desc;select a,b from t1 where a=10 order by b;复制
当利用索引使用max()/min()两个函数时也得益于索引的顺序排列。
select max(b) from t1 group by a;# Using index for group-by，MySQL不需要进行额外的磁盘查找，通过索引的少量条目就能进行group by，索引以最高效的方式使用。select max(a) from t1;;# Select tables optimized away，innodb没有遍历表或者索引就返回了数据，它的意思是这条SQL已经优化到不能再继续优化了。复制
无法使用索引排序的情况：
select a,b from t1 order by c; #是因为c不在索引列里select a,b,c from t1 order by a;#要查询的字段c不包含在索引列里select a,b from t1 order by a asc,b desc; #排序方向不一致select a,b from t1 where a like '1%' order by b;#where条件中的a用的是范围查找，无法使用索引的其他列。复制
前缀索引就是在数据列的前几个字符上建立索引，一般对于BLOB、TEXT或者较长的VARCHAR类型的列采用前缀索引，因为MySQL不允许索引这些列的完整长度，前缀索引可以节约索引空间。
那么我们选择前几个字符作为前缀索引呢？可以通过下面这个公式计算，比值越接近1的前缀索引的选择性越高，那么就可以使用对应的字符截取长度来做前缀索引。
selectcount(distinct left(column_name,3))/count(*),count(distinct left(column_name,4))/count(*),count(distinct left(column_name,5))/count(*),.............from table_name;复制
注意：前缀索引是一种能使索引更小，更快的有效办法，但是MySql无法使用前缀索引做ORDER BY和GROUP BY以及使用前缀索引做覆盖扫描。
往期推荐
关注MySQL
数据库技术栈
MySQL
