由浅入深 MySQL 索引原理

2019-09-30 本文已影响0人小道萧兮

〇、索引的作用

索引的作用：快速找出特定的行。

如果不使用索引，为了从数据库中查找特定的数据，那么就必须从第一条记录开始，遍历整张表，直到找出相关的行。数据量越大，查询数据所花费的时间就越多。

如果表中查询的列有一个索引，MySQL 能通过索引，够快速到达一个位置去搜索数据文件，而不必查看所有数据，那么将会节省很大一部分时间。就行翻字典一样，我们需要查找一条数据，你是愿意从第一页开始找，还是愿意通过目录(索引)找呢？

总之，你可以简单的理解索引就是数据表的目录，索引 ≈ 目录。

一、从二叉树开始

说 MySQL 索引，为啥要说二叉树呢？因为 MySQL 的索引就是树形结构，只不过是一颗特殊的树，所以先从二叉树入手，这样能更好的理解。

首先应考虑的是二叉查找树，这是一种节点值之间具有一定数量级次序的二叉树，对于树中每个节点：

若左子树存在，则左子树中每个节点的值都不大于该节点值；
若右子树存在，则右子树中每个节点的值都不小于该节点值。

由于二叉查找树有上述特性，所以每次查找的时候，只需要去左边或者右边查找就可以了，而不需要全部遍历，类似于二分查找，大大缩短了查询所需时间。所以二叉搜索树也能用来做索引，但是：

在一般情况下，二叉查找树的平均时间复杂度是O(logN)，但如下图所示，最差情况下的时间复杂度为O(N)。这样跟全表扫描没有区别了，所以二叉查找树可以用来做索引，但不是一个好的选择。

二叉查找树

这时，你可能会想到红黑树，红黑树就能避免上述情况。但是，红黑树也是二叉树，当数据量大的时候，树的高度会非常高，这时候，二叉树就不够用了，需要多叉树才行。

二、B-Tree

上面说到二叉树不适合做索引，因为它太“高”了，其查询次数与树的高度成正比，为了减小高度，那么就很容易想到 B-Tree，因为 B-Tree 是多叉树。

B-Tree 是一种多路平衡查找树，它的每个节点最多包含 k 个子节点，k 被称为 B-Tree 的阶，k 的大小取决于磁盘页的大小。通常来说，k 的值都比较大，所以 B-Tree 是一颗“矮胖”树。

“页”是存储器的逻辑块，操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页大小通常为4k），主存和磁盘以页为单位交换数据。

下面来具体介绍一下 B-Tree，一个 k 阶的 B-Tree 具有如下几个特征：

根结点至少有两个子节点；
每个中间节点都包含 k-1 个元素和 k 个子节点；
每一个叶子节点都包含 k-1 个元素；
所有的叶子结点都位于同一层；
每个节点中的元素从小到大排列，节点当中 k-1 个元素正好是 k 个子节点包含的元素的值域分划。

B-Tree

从 B-Tree 的结构来看，它确实可以做索引，但是其一个变种 B+Tree 有更大的优势。

三、B+Tree

终于说到重点了，MySQL 的默认索引就是使用 B+Tree 来实现的。

一个 k 阶的 B+Tree 具有如下几个特征：

有 k 个子树的中间节点包含有 k 个元素（B-Tree 中是 k-1 个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

B+Tree

为什么 MySQL 的默认索引是 B+Tree 而不是 B-Tree 呢？

因为，B-Tree 的数据可以保存在非叶子节点中，搜索时不一定需要找到叶子节点，可能找到某个非叶子节点时就返回了，而 B+Tree 的数据均保存在叶子节点中，搜索时一定要找到叶子节点。

为什么数据要保存在叶子节点呢？

这样做的好处是：一次可以读取更多的索引。

磁盘一次 IO 操作读取的是一个磁盘页大小的数据。如果数据存放在非叶子节点中，那么一次 IO 操作能读取的索引量肯定就少，就可能产生更多的 IO 操作。如果非叶子节点不存储数据，那么一次 IO 操作就能读取到更多的索引，这样检索到数据就能产生更少的 IO 操作，花费的时间也就更少。

此外，B+Tree 所有叶子节点均有一个链指针，指向下一个节点，这样十分适合做范围查询。

综合起来，B+Tree 比 B-Tree 的优势有3点：

单一节点存储更多的元素，非叶子节点不保存数据，使得查询的 IO 次数更少。
所有查询都要查找到叶子节点，查询性能稳定。
所有叶子节点形成有序链表，便于范围查询。

所以 B+Tree 更适合成为索引。

四、索引的缺点

上面说了索引能加快数据查询的速度，但是索引是建立的越多越好吗？

答：不是。

数据量小的表不需要建索引，建立索引会增加额外的开销；
数据变更需要维护索引，更多的索引意味着更高的维护成本；
更多的索引也意味着需要占用更多的硬盘空间。

尽管索引可以提高数据库的查询效率，但是索引有利也有弊，它也会让写入数据的效率下降。这是为什么呢?

数据的写入过程，会涉及索引的更新，这是索引导致数据写入变慢的主要原因。

建立索引后，索引就必须维持它的结构，即索引需要满足 B+Tree 的结构，而在 B+Tree 中，k 值是根据页的大小事先计算好的（一个磁盘页所能容纳索引的大小），也就是说，每个节点最多只能有 k 个子节点。

在往数据库中写入数据的过程中，这样就有可能使索引中某些节点的子节点个数超过 k，这个节点的大小超过 1 个磁盘页的大小，读取这样 1 个节点，就会导致多次磁盘 IO 操作。我们该如何解决这个问题呢?

实际上，我们只需要将这个节点分裂成两个节点。但是，节点分裂之后，其上层父节点的子节点个数就有可能超过 k 个。不过这也没关系，我们可以用同样的方法，将父节点也分裂成两个节点。这种级联反应会从下往上，一直影响到根节点。这个分裂过程，你可以结合着下面这个图一块看，会更容易理解。

图中的 B+Tree 是一个三叉树。我们限定叶子节点中，数据的个数超过 2 个就分裂节点；非叶子节点中，子节点的个数超过3个就分裂节点。

B+Tree 分裂

正是因为 B+Tree 需要维护一个这样的结构，所以，索引会导致数据库的写入速度变慢。实际上，不仅是写入速度变慢，删除速度也同样会变慢，当节点个数少于一定数量时，会进行节点的合并，原理与上图类似。

所以，不建议用 UUID 或者随机字符串作为主键值，尽量用连续增长的值对于 InnoDB 而言，因为节点下有数据文件，因此节点的分裂将会比较慢。对于 InnoDB 的主键，尽量用整型而且是递增的整型。如果是无规律的数据，在页的分裂时，影响速度。

五、索引失效

索引不是万能的，在一定的情况下，可能在有索引的情况下也不会用到索引，而是全表扫描。

1、联合索引的最左匹配原则

在联合索引的情况下，最左索引优先，以最左边的为起点任何连续的索引都能匹配上。同时遇到范围查询(>、<、between、like)就会停止匹配。

例如：如果建立 (a, b) 顺序的索引，b = 2，或者 a = 1 or b = 2 是匹配不到 (a, b) 索引的；但是如果查询条件是 a = 1 and b = 2，或者 a=1，又或者是 b = 2 and b = 1 就可以，优化器会自动调整 a, b 的顺序。

再比如 a = 1 and b = 2 and c > 3 and d = 4 如果建立 (a, b, c, d) 顺序的索引，d是用不到索引的，因为c字段是一个范围查询，它之后的字段会停止匹配。

联合索引

上图中的联合索引为(col3, col2)，先通过 col3 找到 col2，但是无法通过 col2 找到 col3，这就是联合索引的最左匹配原则。最左不能丢，中间不能断，其实就是最左索引对应树的最上层索引。

2、如果条件中有 or ，即使其中有条件带索引也不会命中。

3、like 查询是以 % 开头：如果是 int 型索引不会命中，字符型需要 % 只有在右边才可以命中，如 test%；而 %test 和 %test% 不会命中。

4、如果字段型是字符串，那一定要在条件中将数据使用引号引用起来，否则不使用索引。

5、没有查询条件，或者查询条件没有建立索引。

6、查询条件中，在索引列上使用函数（ + , - , * , / ）, 这种情况下需建立函数索引。

7、采用 not in，not exist。

六、InnoDB 与 MyISAM

InnoDB 与 MyISAM 都是 MySQL 的数据库引擎之一，现在 MySQL 的默认存储引擎为 InnoDB。

在 MyISAM 中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求 key 是唯一的，而辅助索引的 key 可以重复。

InnoDB 与 MyISAM

从上图中可以看出，MyISAM 叶子节点仅保存了键位信息以及该行数据的地址，并不保存真正的数据，索引和实际数据是分开的，只不过是用索引指向了实际的数据，MyISAM 索引仅仅保存数据记录的地址，这种索引就是所谓的非聚集索引。

相比 MyISAM 索引文件和数据文件是分离的，InnoDB 的叶节点 data 域保存了完整的数据记录。这个索引的 key 是数据表的主键，因此 InnoDB 表数据文件本身就是主索引。这被称为聚集索引。

InnoDB 其余的索引都作为辅助索引，辅助索引域存储相应记录主键的值。也就是说，InnoDB 在根据主索引搜索时，直接找到 key 所在的节点即可取出数据；在根据辅助索引查找时，则需要先取出主键的值，再走一遍主索引。

因此，在设计表的时候，不建议使用过长的字段作为主键，过长的主索引会令辅助索引变得过大，也不建议使用非单调的字段作为主键，这样会造成主索引频繁分裂。

因为 InnoDB 的数据文件本身要按主键聚集，所以 InnoDB 要求表必须有主键（MyISAM 可以没有），如果没有显式指定，则自动选择一个唯一标识数据记录的列作为主键，如果不存在这种列，则 MySQL 自动为 InnoDB 表生成一个隐含字段作为主键。

而 MyISAM 无论主索引还是辅助索引，都可以直接查找到对应的数据。

总结 InnoDB 与 MyISAM 的区别：

MyISAM 类型的表强调的是性能，其执行数度比 InnoDB 类型更快，但是不支持事务，不支持外键；而 InnoDB 提供事务支持外部键等高级数据库功能。
MyISAM 只支持表锁，不支持行锁；InnoDB 既支持表锁，也支持行锁，但只有在用到索引的情况下才会使用行锁。采用MVCC来支持高并发，有可能死锁。

MyISAM 适合：1、做 count 的计算；2、插入不频繁，查询非常频繁；3、没有事务。
InnoDB 适合：1、可靠性要求比较高，或者要求事务；2、表更新和查询都相当的频繁，并且行锁定的机会比较大的情况

七、如何定位并优化慢查询

1、根据慢日志定位慢 SQL

MySQL 的慢查询日志是一种日志记录，它用来记录在 MySQL 中响应时间超过阀值的语句，具体指运行时间超过 long_query_time 值的SQL，则会被记录到慢查询日志中。long_query_time 的默认值为 10s。

2、使用 explain 分析 SQL

explain 用来分析 SELECT 查询语句，通过分析结果来优化查询语句。在分析的结果中，比较重要的字段有：

select_type : 查询类型，有简单查询、联合查询、子查询等
key : 使用的索引
rows : 扫描的行数

3、修改 SQL 或让 SQL 走索引

只返回必要的列：最好不要使用 SELECT * 语句。
只返回必要的行：使用 LIMIT 语句来限制返回的数据。
缓存重复查询的数据：使用缓存可以避免在数据库中进行查询，特别在要查询的数据经常被重复查询时，缓存带来的查询性能提升将会是非常明显的。