MySQL索引工作原理、优化及基本知识点详细分析

索引

在之前，我对索引有以下的认知：

• 索引可以加快数据库的检索速度
• 表经常进行INSERT/UPDATE/DELETE操作就不要建立索引了，换言之：索引会降低插入、删除、修改等维护任务的速度。
• 索引需要占物理和数据空间。
• 了解过索引的最左匹配原则
• 知道索引的分类：聚集索引和非聚集索引
• Mysql支持Hash索引和B+树索引两种

看起来好像啥都知道，but，但面试让你说的时候可能就GG了：

• 使用索引为什么可以加快数据库的检索速度啊？
• 为什么说索引会降低插入、删除、修改等维护任务的速度？
• 索引的最左匹配原则指的是什么？
• Hash索引和B+树索引有什么区别？主流的使用哪一个比较多？InnoDB存储都支持吗？
• 聚集索引和非聚集索引有什么区别？
• ........

索引的基础知识

首先Mysql的基本存储结构是页(记录都存在页里边)

可以得出以下结论：

　　1. 各个数据页可以组成一个双向链表

　　2. 而每个数据页中的记录又可以组成一个单向链表

　　3. 每个数据页都会为记录生成一个页目录，通过主键查找某条记录时可以在页目录中使用二分法快速定位到对应的槽，然后遍历该槽对应分组中的记录找到指定的记录

　　4. 以其他列(非主键)作为搜索条件：只能从最小记录开始依次遍历单链表中的每条记录。

所以说，如果我们写select * from user where username = 'Java3y' 这样没有进行任何优化的sql语句，默认会这样做：

• 遍历双向链表，定位到所在的页
• 从所在的页内中查找相应的记录，因为不是根据主键查询，因而只能遍历

很明显，在数据量很大的情况下这样查找会很慢！

索引提高检索速度

通过上面可知，加快查找速度势在必行，那么，索引做了些什么可以让我们查询加快速度呢？其实就是将无序的数据变成有序(相对)

例如：要找到id为8的记录简要步骤如下

很明显的是：

• 没有用索引我们是需要遍历双向链表来定位对应的页，现在通过**“目录”**就可以很快地定位到对应的页上了！
• 其实底层结构就是B+树，B+树作为树的一种实现，能够让我们很快地查找出对应的记录。

【参考资料】：Mysql索引

索引降低增删改的速度

平衡树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

B+树是平衡树的一种，是不会退化成链表的，树的高度都是相对比较低的(基本符合均衡的结构)【这样一来我们检索的时间复杂度就是O(logn)】！从上一节的图我们也可以

看见，建立索引实际上就是建立一颗B+树。

• B+树是一颗平衡树，如果我们对这颗树增删改的话，那肯定会破坏它的原有结构。
• 要维持平衡树，就必须做额外的工作。正因为这些额外的工作开销，导致索引会降低增删改的速度

【参考资料】：B+树删除和修改

哈希索引

除了B+树之外，还有一种常见的是哈希索引。哈希索引就是采用一定的哈希算法，把键值换算成新的哈希值，检索时不需要类似B+树那样从根节点到叶子节点逐级查找，只

需一次哈希算法即可立刻定位到相应的位置，速度非常快。但是hash索引有好几个局限：

• 哈希索引也没办法利用索引完成排序
• 不支持最左匹配原则
• 在有大量重复键值情况下，哈希索引的效率也是极低的---->哈希碰撞问题。
• 不支持范围查询

【参考资料】：B+树索引和哈希索引的区别

InnoDB支持哈希索引嘛？

主流的还是使用B+树索引比较多，对于哈希索引，InnoDB是自适应哈希索引的（hash索引的创建由InnoDB存储引擎引擎自动优化创建，用户干预不了）！

聚集和非聚集索引

• 聚集索引就是以主键创建的索引
• 非聚集索引就是以非主键创建的索引

聚集索引有2个特点：

1. 使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义

• 页内的记录是按照主键的大小顺序排成一个单向链表。
• 各个存放用户记录的页也是根据页中记录的主键大小顺序排成一个双向链表。
• 各个存放目录项的页也是根据页中记录的主键大小顺序排成一个双向链表。

2. B+树的叶子节点存储的是完整的用户记录，就是指这个记录中存储了所有列的值。

　　我们把具有这两种特性的B+树称为聚集索引，所有完整的用户记录都存放在这个聚集索引的叶子节点处。这种聚集索引并不需要我们在MySQL语句中显式的去创建，

InnoDB存储引擎会自动的为我们创建聚簇索引。另外有趣的一点是，在InnoDB存储引擎中，聚集索引就是数据的存储方式（所有的用户记录都存储在了叶子节点），也

就是所谓的索引即数据。

非聚集索引也叫做二级索引

　　上边介绍的聚簇索引只能在搜索条件是主键值时才能发挥作用，因为B+树中的数据都是按照主键进行排序的。那如果我们想以别的列作为搜索条件该怎么办呢？难道

只能从头到尾沿着链表依次遍历记录么？我们可以多建几棵B+树，不同的B+树中的数据采用不同的排序规则。比方说我们用c2列的大小作为数据页、页中记录的排序规则，

再建一棵B+树

• 其中，B+树的叶子节点存储的并不是完整的用户记录，而只是c2列+主键这两个列的值。
• 索引项记录中不再是主键+页号的搭配，而变成了c2列+页号的搭配。

　过程如下：首先根据c2列的值，定位到非聚集索引中的某一个叶子节点，然后根据该叶子节点中的主键去聚簇索引中再查找一遍完整的用户记录，称之为回表

索引优化

在执行SQL时，MySQL只能使用一个索引，会从多个单列索引中选择一个限制最为严格的索引，根据B+树的性质，很容易理解各种常见的MySQL索引优化思路

1. 优先使用自增key作为主键

假设用4B的自增key作为索引，则m可达到512，层高仅有3。参考这里，使用自增的key有两个好处：

　　1. 自增key一般为int等整数型，key比较紧凑，这样m可以非常大，而且索引占用空间小。最极端的例子，如果使用50B的varchar（包括长度），那么m = 4 * 1024 /

54m = 75.85 ~= 76，深度最大log(76/2)(10^7) = 4.43 ~= 5 ，再加上cache缺失、字符串比较的成本，时间成本增加较大。同时，key由4B增长到50B，整棵索引树

的空间占用增长也是极为恐怖的（如果二级索引使用主键定位数据行，则空间增长更加严重）

　　2. 自增的性质使得新数据行的插入请求必然落到索引树的最右侧，发生节点分裂的频率较低，理想情况下，索引树可以达到“满”的状态。索引树满，一方面层高更低，一

方面删除节点时发生节点合并的频率也较低

优化案例：

曾使用varchar(100)的列做过主键，存储containerId，过了3、4天100G的数据库就满了，之后增加了自增列作为主键，containerId作为unique的二级索引，时间、空间优化效果相当显著。

2. 最左前缀匹配 

• 索引可以简单如一个列(a)，也可以复杂如多个列(a, b, c, d)，即联合索引。如果是联合索引，那么key也由多个列组成，同时，索引只能用于查找key是否存在（相等）
• 遇到范围查询(>、<、between、like左匹配)等就不能进一步匹配了，后续退化为线性查找，也就是此时不会通过索引来查询
• =、in自动优化顺序，mysql会自动优化这些条件的顺序

3. 索引列不能参与计算 

有索引列参与计算的查询条件对索引不友好（甚至无法使用索引）。原因很简单，如何在节点中查找到对应key？如果线性扫描，则每次都需要重新计算，成本太高；如果二分

查找，则需要确定大小关系

4. 能扩展就不要新建索引

如果已有索引(a)，想建立索引(a, b)，尽量选择修改索引(a)为索引(a, b)。MySQL可以直接在索引a的B+树上，经过分裂、合并等修改为索引(a, b)

5. 不需要建立前缀有包含关系的索引

如果已有索引(a, b)，则不需要再建立索引(a)，但是如果有必要，则仍然需考虑建立索引(b)。

6. 选择区分度高的列作索引

这很容易理解。如，用性别作索引，那么索引仅能将1000w行数据划分为两部分（如500w男，500w女），索引几乎无效。区分度的公式是count(distinct <col>) /

count(*)，表示字段不重复的比例，比例越大区分度越好。唯一键的区分度是1，而一些状态、性别字段可能在大数据面前的区分度趋近于0