你好，我是猿java。
提到 MySQL索引，相信使用过的小伙伴并不陌生，日常开发中，我们经常会通过创建索引来提升查询效率，那么，为什么一个慢查询加上索引查询速度就能提升一个档次？索引后面的实现机制到底是什么？今天一起聊一聊。
1、索引是什么？
读书时，如果要快速找到某篇文章，我们通常会通过目录定位到页码，再根据页码定位到文章。其实，MySQL的索引如同数据库的“目录”，当数据达到千万级别时，如果没有这个“目录”，想要查找某条数据，势必花费大量的时间，因此，为了能提高查询效率，MySQL提供了索引这样一个机制。
2、索引常见的数据结构
用于索引的数据结构通常有3种：哈希表、有序数组和搜索树。
2.1、哈希表
哈希表是一种以key-value键值对存储数据的结构，比如：java的 HashMap，redis的 key-value都是这样一种形式。
哈希表的实现思路也很简单：用一个哈希函数把 key 换算成数组确定的位置，然后把 value 放在数组的这个位置。下图为哈希表的一个简略图：
从上图我们可以知道：当 key的 hash值相同时（hash冲突），会采用链表的方式把 value串起来。
缺点
1. hash冲突
随着数据的增多，不同的 key经过哈希计算后结果是一样，这种情况叫做hash碰撞。处理 hash碰撞的一种方法是链表，但是当数据量比较大时，链表的长度还是会比较大，性能开销会花在链表查询上。
2. 无法范围查询
哈希表是散列存储，这种结构适用于只有等值查询的场景，无法范围查询。
2.2、有序数组
如下图，如果数据按照id的升序存放到数组中，就形成了一个有序数组，这样既能根据等值查询，也方便范围查询。
缺点
如果仅仅看查询效率，有序数组是比较好的数据结构，但如果有数据的插入和删除，插入和删除点后面的数据需要移动，所以整体性能会下降，因此，有序数组只适合静态存储引擎。
2.3、搜索树
2.3.1 二叉树
二叉树（Binary Tree）的定义很简单，它是很多其他搜索树的基础，主要特点如下：
每个节点最多只能有两个子节点就是二叉树
除了根节点外，每个节点最多有一个父节点
2.3.2 二叉搜索树
二叉搜索树(Binary Search Tree)，是一种特殊的二叉树，主要特点如下：
左子树节点比父节点小，右子树节点值比父节点大。
根据二叉搜索树的特点可以使用二分查找法，比如，在二叉查找树中查询 5。 首先，从根节点开始遍历，5 > 3，可以定位5在节点3的右子树。 其次，遍历节点3的右子树，5 < 6，可以定位 5在节点6的左子树。 最后，遍历节点6的左子树，因为左子树只有一个节点5，5=5，即目标值。
缺点
当数据是有序增长，极端情况下，整个二叉搜索树就会变成一棵斜树。如下图：
2.3.4 平衡二叉树
平衡二叉树(Balanced Binary Search Tree)，又被称为 AVL树，是为了解决二叉树退化成链表而诞生的，主要特点如下：
每个节点的左子树和右子树的高度差至多等于1。
为了解决二叉搜索树在极情况下变成斜树的问题，平衡二叉树增加了 左右子树的高度差 小于等于1.
缺点
平衡二叉树追求绝对严格的平衡，平衡条件必须满足左右子树高度差不超过1，该规则在频繁的插入、删除等操作的情景性能肯定会出现问题，因此诞生了红黑树。
2.3.5 红黑树
红黑树是一种特殊的平衡二叉树，主要特点如下：
1.具有二叉树所有特点。
下图展示了一棵红黑树：
2.3.6 B-树
B-树（Balance Tree）是平衡的多路搜索树，它的高度远小于平衡二叉树的高度。在文件系统和数据库系统中的索引结构经常采用 B-树来实现，主要特点如下：
每个节点最多只有m个子节点。
B-树示意图：
2.3.7 B+树
B+树是基于B-树做了优化，B+树和 B-树的差异如下：
有k个孩子的节点就有k个关键字，即孩子数量 = 关键字数，而 B-树中，孩子数量 = 关键字数 + 1。
B+树示意图：
常见的面试问题
问题1：为什么 MySQL选择B+树做索引？
MySQL的数据都是存放在磁盘，因此磁盘 IO是 MySQL的性能瓶颈，而二叉树，二叉搜索树，二叉平衡树，红黑树都属于二叉树，当 MySQL表中的数据量比较大时，索引的体积也会很大，树高就会很大，内存放不下的需要从磁盘读取，树的层次太高的话，读取磁盘的次数就多了，影响 MySQL的使用性能。
问题2：B+树是怎么实现索引？
我们分别从 MyISAM 和 InnoD两个引擎讲解
MyISAM引擎
MyISAM采用的非聚簇索引，B+树的非叶子节点存储索引值和指向子节点的指针，叶子节点上存放的是索引值和数据在磁盘上的物理地址，所以通过索引定位到数据地址后，需要到磁盘上回表获取数据，索引模型示意图如下：
Innodb引擎
Innodb采用的聚簇索引(主键索引)，B+树的非叶子节点(内部节点)存放的是索引值和指向子节点的指针，叶子节点上存放的是索引值和数据。
非聚簇索引，B+树的非叶子节点存储索引值和指向子节点的指针，叶子节点存放的是索引值和聚簇索引值。因此非聚簇索引需要先遍历非聚簇索引B+树定位到聚簇索引的值，再到聚簇索引上回表获取数据。 聚簇索引的优点：可以避免每棵索引树上都存放数据，使得在相同的内存空间下存放的更多的索引节点，减少磁盘IO。
聚簇索引示意图如下：
非聚簇索引示意图如下：
聚簇索引和非聚簇索引
聚簇索引：将数据存储与索引放到了一块，找到索引也就找到了数据。 非聚簇索引：是一种数据库索引结构，它与数据存储在不同的物理位置，与表的物理存储顺序无关
索引覆盖
在当前索引树上能直接查找所需结果，不需要回表，这就是索引覆盖。
比如上面的案例：select id from user where age = 30 and sex = ‘男’; 因为id已经在当前索引的叶子节点，所以不需要到聚簇索引上回表，因此这就是一个索引覆盖的场景。由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。
联合索引
联合索引是指将表中多个字段联合组合成一个索引，比如：index(age, sex)
那么联合索引是如何用 B+树实现的呢？
场景：查询用户表中年龄为30岁的男性 表结构：
mysql> create table user(
id int primary key,
name varchar(16),
age int not null,
sex varchar(4) not null,
index(age, sex)) engine=InnoDB;
联合索引在 B+树索引模型示意图如下：
查询分析：
首先，从根节点根据组合索引里面的所有字段进行精确匹配查到
age=30 and sex='男'的记录有两条；然后，获取 id2和 id3两个节点中指向子节点的指针，定位到子节点，再定位到叶子节点，从叶子节点中拿到聚簇索引的值 id2和 id3；
最后，到聚簇索引上遍历 id2和 id3，直到叶子节点上获取目标数据；
最左前缀原则
在日常的工作中，我们发现查询条件比较多，比如上面的用户表，有根据 age和 sex查询，有根据 name和age查询，也有根据 name和sex查询，各种查询组合，那是不是都要为它们创建一个索引呢？
答案是不一定。B+树可以利用索引的最左前缀来定位记录。最左前缀可以是联合索引的最左 N个字段，也可以是字符串索引的最左 M个字符。
比如：有一个联合索引union_index(a, b, c)，对于下面几种 where查询条件都可以匹配索引：
where a = ?
where a = ? and b = ?
where a = ? and b = ? and c = ?
但是，当查询条件是where a = ？and c = ? 时，where条件中的 a,c，只有a条件可以匹配联合索引的a字段。
为了更好的解释最左前缀原则，这个以一个示例来分析：
场景：查询用户表中姓刘的男性，联合索引：index(name, sex)，B+树索引模型示意图如下：
查询分析：
- 首先，从根节点查到第一个
'刘'开头的记录是 id2，然后向后遍历，直到不满足条件为止，最后结果id2，id3两条； - 然后，获取指向子节点的指针，定位到子节点，一直到叶子节点，接着比较第 2个字段
sex='男'，定位到 id2； - 最后，根据id2到聚簇索引上遍历，直到叶子节点上获取目标数据； 从上面的查询分析可以看到：索引前缀原则，查询条件
where name like '刘%' and sex = '男'，只用到了联合索引中的 name字段，那么 set条件没有用到索引会怎么处理呢？ 这个就是 MySQL5.6引入的索引下推机制，name字段定位了一批数据减少了全表扫描，在符合where name like '刘%'的数据集中再筛选sex='男'，这样减少了回表的次数，降低了磁盘IO。
问题3：一棵三层的 B+树，可以存放多少行数据？
在 Innodb存储引擎里，最小的存储单元是页(page)，一个页的大小是 16KB， 也就是一个节点的大小。根据上文，非叶子节点保存的是索引值和指针， 假设索引id是 Long类型，占 8个byte，指针占 6个byte，所以， 根节点可以存放 16KB / (8 + 6) = 1170 个索引值，因此就有 1170个指针， 假设一条数据的大小是 1K，因此，叶子节点可以存放 16Kb / 1K = 16条数据， 所以，3层的 B+树可以存放1170 * 1170 * 16 = 21902400(2190多万)行记录
总结
本文分析了索引的常用的3种数据结：哈希表、有序数组和搜索树。同时分析了它们的性能，优缺点以及使用场景。
本文通过分析搜索树，我们对比了几种常见的树结构以及它们的特点。
通过本文的分析，我们可以发现，检索是海量数据查询的一个重要课题，针对不同的场景，我们需要采用不同的数据结构。
最后，如果本文对你有帮助，请帮忙点赞或转发，想获取更多技术好文和面试经，请关注我。