理解数据库如何使用索引
不要再用排列组合的方式寻找合适的索引了！从数据库的视角带你理解数据库是如何使用索引的。更轻松地设计索引！ 本文讨论的索引为最常见的 B+ 树索引。
抛开 B+ 树
索引就像是一本书的目录，可以协助查找所需的内容。目录设计的好可以提高查找的效率，反之则会降低查找的效率。所以，索引的设计是非常重要的。要设计出高效的索引，重点在于理解数据库是怎么利用索引来查找数据的。
我学习数据库索引的时候，每本书每篇文章上来就讲 B+ 树，还没开始就想放弃了。但实际上，大多数时候我们并不需要深入了解这些。
这是一个棵简单的 B+ 树：
+----+----+
| 10 | 20 |
+----+----+
/ | \
+---+ +----+----+ +----+
| 5 | | 15 | 18 | | 25 |
+---+ +----+----+ +----+
/ | \ / | \ / | \
1 6 9 11 16 19 21 26 30
看起来很复杂，但除了叶子节点，其他节点的作用是为了能够快速定位到叶子节点。我们只关注叶子节点，把其他节点忽略掉，就变成了一个简单的有序的双向链表：
+---+---+---+----+----+----+----+----+----+
| 1 | 6 | 9 | 11 | 16 | 19 | 21 | 26 | 30 |
+---+---+---+----+----+----+----+----+----+
只需要记住 B+ 树有以下三个特性：
- 叶子节点是有序的
- 可以快速定位到叶子节点
- 叶子节点间是相连的，可以快速前后遍历
之后我都会用链表来表示索引。至于 B+ 树是怎么维持有序的，怎么插入、删除的，有兴趣的话可以自行了解。
数据库怎么使用索引
我们先假设数据库已经选择了一个它认为合适的索引，它使用索引来查找数据的过程简单来说如下：
- 通过索引数据结构的特性，快速定位到第一个符合条件的索引节点。这个节点对应的行不一定符合查询条件，因为索引的列不一定包含查询条件所需的所有列。
- 从步骤 1 定位到的节点开始单向遍历，利用索引节点的值进行初步筛选。因为 B+ 树的叶子节点是有序且相连的，所以可以快速地单向遍历。通过符合初步筛选的节点，从硬盘中读取对应行的数据。
- 对步骤 2 中初步筛选出的行，进行进一步的筛选。这一步不是必须的，如果索引的列包含了查询条件所需的所有列，就不需要再进行筛选了，这也是最理想的情况。
下面会介绍一些常见的查询场景，以及数据库是怎么利用索引来查找数据的，希望能给你一些启发。
快速定位
对主键 id 进行查询是最简单的情况，当我们查询 SELECT * FROM table WHERE id = 2 时，数据库可以通过索引快速的找到符合条件的行。非常高效没有多余的步骤。
index on (id)
|
v
+------++-----+-----+-----+-----+-----+
| id || 1 | 2 | 3 | 4 | 5 |
+------++-----+-----+-----+-----+-----+
✅
单向遍历
当我们要查找大于等于 20 岁的最年轻的 3 个人时 SELECT * FROM table WHERE age >= 20 LIMIT 3，数据库可以通过索引快速的找到第一个符合条件的节点，然后再进行单向遍历，找到符合条件的前 3 行。
index on (age)
|
v ------------>
+-------++------+------+------+------+------+
| age || 18 | 20 | 21 | 22 | 23 |
+-------++------+------+------+------+------+
✅ ✅ ✅
多列索引（联合索引）
多列索引和单列索引没什么区别，只是多列索引的叶子节点中含有多列的值，也是有序的。多列索引中节点的排序规则和字符串的排序规则相似，从左到右逐列比较，以第一个值不同的列的比较结果为准。比如有一个多列索引 (a, b, c)，节点 (1, 2, 3) 小于 (1, 2, 4)，大于 (1, 1, 4)。当我们查询 SELECT * FROM table WHERE a = 1 AND b = 2 AND c = 3 时，同单列索引，数据库可以通过多列索引快速的找到符合条件的节点。
index on (a, b, c)
|
v
+-----++-----+-----+-----+-----+-----+
| a || 1 | 1 | 1 | 1 | 2 |
+-----++-----+-----+-----+-----+-----+
| b || 1 | 1 | 2 | 2 | 5 |
+-----++-----+-----+-----+-----+-----+
| c || 1 | 3 | 2 | 3 | 4 |
+-----++-----+-----+-----+-----+-----+
✅
以下是能够完全利用 (a, b, c) 索引的查询：
SELECT * FROM table WHERE a = 1 AND b = 2 AND c = 3SELECT * FROM table WHERE a = 1 AND b = 2SELECT * FROM table WHERE a = 1
也就是说拥有一个 (a, b, c) 索引相当于同时拥有 (a, b) 和 (a) 索引。
数据库利用多列索引快速定位符合条件的节点的规则是：依据索引列的顺序，从左到右依次匹配，如果某一列没有匹配到，或者某一列不在查询条件中，就会停止匹配。
比如我们查询 SELECT * FROM table WHERE a = 1 AND c = 3，使用 (a, b, c) 索引时，从左到右，先匹配 a = 1，然后因为 b 不在查询条件中，就停止匹配。在这个查询中 (a, b, c) 索引在定位第一个符合条件的节点时等同于索引 (a)，因为不同的 b 值都可能有符合 c = 3 的行。所以数据库必须遍历所有 a = 1 的行进行筛选。
index on (a, b, c)
|
v ---------------->
+-----++-----+-----+-----+-----+-----+
| a || 1 | 1 | 1 | 1 | 2 |
+-----++-----+-----+-----+-----+-----+
| b || 1 | 1 | 2 | 2 | 5 |
+-----++-----+-----+-----+-----+-----+
| c || 1 | 3 | 2 | 3 | 4 |
+-----++-----+-----+-----+-----+-----+
❌ ✅ ❌ ✅
Note 但在单向遍历筛选的过程中，索引
(a, b, c)会比索引(a)要更快，因为索引(a, b, c)的节点中包含c的值，不需要从硬盘中读取对应行c的值。内存中的读取速度要比硬盘的随机读取速度快得多。
如果我们为这个查询设计一个新的多列索引 (a, c)，就可以更高效地查找到符合条件的行。
index on (a, c)
|
v ---->
+-----++-----+-----+-----+-----+-----+
| a || 1 | 1 | 1 | 1 | 2 |
+-----++-----+-----+-----+-----+-----+
| c || 1 | 2 | 3 | 3 | 4 |
+-----++-----+-----+-----+-----+-----+
✅ ✅
多列索引的顺序
多列索引列的顺序很重要。比如一个成绩表，含有 id, class, score 三列，有一个多列索引 (score, class)。如果我们查询 SELECT * FROM table WHERE class = 2 AND score >= 60，索引 (score, class) 貌似是可以帮助查询。但实际上，它的帮助是有限的。数据库快速定位到第一个符合条件的节点后，它需要遍历所有分数大于 60 的节点，才能找到所有符合条件的节点。其中可能包含了大量不符合条件的节点。
index on (score, class)
|
v ------------------->
+---------++------+------+------+------+------+------+
| score || 45 | 52 | 60 | 64 | 75 | 95 |
+---------++------+------+------+------+------+------+
| class || 1 | 2 | 2 | 1 | 1 | 2 |
+---------++------+------+------+------+------+------+
✅ ❌ ❌ ✅
但如果用 (class, score) 索引，就可以更高效的查找到符合条件的所有行。单向遍历的过程中也没有不符合条件的节点。
index on (class, score)
|
v ----->
+---------++------+------+------+------+------+------+
| class || 1 | 1 | 1 | 2 | 2 | 2 |
+---------++------+------+------+------+------+------+
| score || 45 | 64 | 75 | 52 | 60 | 95 |
+---------++------+------+------+------+------+------+
✅ ✅
不仅仅要设计出能被数据库采用的索引，还要根据实际的查询需求，设计出能够高效利用的索引。
利用索引的有序
索引本身就是有序的，所以可以针对查询需求设计无需额外排序的索引。比如上面成绩表的例子，我们使用索引 (class, score) 查询 SELECT * FROM table WHERE class = 2 ORDER BY score ASC 时，数据库通过索引单向遍历到的节点是有序的，所以不需要对结果进行额外的排序。如果无法利用索引的有序，即使你只需要查询一条数据，数据库也需要把所有符合条件的数据全部找出来，然后再进行排序，这是非常低效的。
index on (class, score)
|
v ------------>
+---------++------+------+------+------+------+------+
| class || 1 | 1 | 1 | 2 | 2 | 2 |
+---------++------+------+------+------+------+------+
| score || 45 | 64 | 75 | 52 | 60 | 95 |
+---------++------+------+------+------+------+------+
✅ ✅ ✅
因为索引叶子节点是双向链表，所以也可以高效地查询 SELECT * FROM table WHERE class = 2 ORDER BY score ASC。
index on (class, score)
|
<----------- v
+---------++------+------+------+------+------+------+
| class || 1 | 1 | 1 | 2 | 2 | 2 |
+---------++------+------+------+------+------+------+
| score || 45 | 64 | 75 | 52 | 60 | 95 |
+---------++------+------+------+------+------+------+
✅ ✅ ✅
总结
- 设计索引时，要根据实际的查询需求，要尽可能让查询结果的索引叶子节点相邻，这样可以减少单向遍历时不符合条件的节点的数量。
- 筛选条件中的列要尽可能放在索引中，这样筛选时可以减少从硬盘中读取数据的次数。
- 如果需要对结果进行排序，尽可能利用索引的有序性，避免额外的排序操作。
挖一些坑：有时间还打算总结一下数据库的查询优化器是怎么选择索引的、join, group by, subqueries 等操作是怎么利用索引的、索引的一些坑等等。
转载自:https://juejin.cn/post/7340109700767105076