从联合索引到最左匹配

索引

数据库索引是为了提高查询速度而对表的字段附加的一种标识。

简单来说，索引其实是一种数据结构。数据库的索引类似于书籍的目录。

在书籍中，目录允许用户不必翻阅整本书就能迅速地找到所需要的信息。在数据库中，索引也允许数据库程序迅速找到表中的数据，而不必扫描整个数据库。

首先，我们要明白为什么索引会提高查询速度。数据库在执行一条 SQL 语句的时候，默认的扫描方式是根据搜索条件进行全表扫描，遇到符合匹配条件的就加入搜索结果集合中。

如果我们对某一字段增加索引，查询时就会先去索引列表中一次定位到特定值的行数，大大减少了遍历匹配的次数，所以数据库索引能明显提高查询的速度。

哈希（Hash）比树（Tree）快，为什么 InnoDB 热衷于树型？

对于等值查询的 SQL，如：

1	SELECT * FROM user t WHERE t.user_id = "1356894556";

因为上述每次查询肯定只会返回一条记录，所以采用 hash 结构索引的话，确实会比树结构快。

但是除了等值查询，数据库中还有范围查询，分组 group by，排序 order by 等等。此时 hash 索引将会退化为 $O(n)$ 复杂度。而树型索引由于其结构的 “有序性” ，依旧保持 $O(logn)$ 的高效率，时间复杂度不会退化。

索引采用的数据结构

数据结构中，可以充当字典的树主要有以下几种：

二叉搜索树。
B 树。
B+ 树。

1° 二叉搜索树

最简单的树结构，主要特征：

（1）若它的左子树不为空，则左子树所有节点的值均小于它的根节点的值。

（2）若它的右子树不为空，则右子树所有节点的值均大于它的根节点的值。

那么，为什么二叉搜索树不适合用作数据库索引？

① 数据量大的时候，树的高度比较高，导致查询比较慢。

② 每个节点只存储一个记录，可能导致一次查询进行多次磁盘 IO。

2° B 树

B 树是为磁盘或其他直接存储的辅助存储设备而设计的一种平衡搜索树，在降低磁盘 IO 操作数方面要更好一些。B 树以一种自然的方式扩广了二叉搜索树。其主要特征：

（1）每个叶子节点具有相同的高度，即树的高度。

（2）除了根节点和叶子节点外，其它内部节点（非叶子节点）至少有 $\lceil \frac{m}{2}\rceil$ 个孩子（$\lceil ~\rceil$ 表示向上取整）。

（3）如果根节点不是叶子节点，那么它至少有两个子节点。

（4）叶子节点，非叶子节点，都存储数据（非叶子节点还存储指向其子节点的指针）。

（5）有 $k$ 个子节点的非叶子节点拥有 $k - 1$ 个键，且升序排列，满足 $k[i] \le k[i + 1]$。

一个简单的图例如下：

那么，为什么B 树适合用作数据库索引？

① B 树结构是 m 分叉的，高度能够大大降低。

② 每个节点可以存储 $j$ 条记录，节点通常和磁盘页一样大，能够充分利用预读的特性，极大减少磁盘 IO。

3° B+ 树

一个常见的 B 树变种，在 B 树的基础上，做了一些改进：

（1）数据都存储在叶结点中，内部结点只存放关键字和孩子指针。

（2）叶子节点存储实际记录行，记录行相对比较紧密的存储，适合大数据量磁盘存储；非叶子节点存储记录的PK，用于查询加速，适合内存存储。

（3）所有叶子节点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接。

（4）非叶子节点，不存储实际记录，而只存储记录的 KEY 的话，那么在相同内存的情况下，B+ 树能够存储更多索引。

同时，B+ 树为了方便范围查询，叶子节点之间还用指针串联起来。

以下是一棵 B+ 树的典型结构：

B+ 树相比于 B 树的优势

由于索引节点上只有索引而没有数据，所以索引节点上能存储比 B 树更多的索引，这样树的高度就会更矮。树的高度越矮，磁盘寻道的次数就会越少。

因为数据都集中在叶子节点，而所有叶子节点的高度相同，那么可以在叶子节点中增加前后指针，指向同一个父节点的相邻兄弟节点，这样可以更好地支持查询一个值的前驱或后继，使连续访问更容易实现。

比如这样的 SQL 语句：select * from tbl where t > 10，如果使用 B+ 树存储数据的话，可以首先定位到数据为 10 的节点，再沿着它的 next 指针一路找到所有在该叶子节点右边的叶子节点，返回这些节点包含的数据。

而如果使用 B 树结构，由于数据既可以存储在内部节点也可以存储在叶子节点，连续访问的实现会更加繁琐（需要在树的内部结构中进行移动）。

为什么 m 叉的 B+ 树比二叉搜索树的高度大大降低？

(1) 局部性原理，将一个节点的大小设为一页，一页 4K，假设一个 KEY 有 8 字节，一个节点大约可以存储 500 个KEY，即 j = 500；（1KB = 1024 字节，4KB = 4096 字节， 4096 / 8 = 512 个）

(2) m 叉 B+ 树，大概 m / 2 <= j <= m，即可以差不多是 1000 叉树；

(3) 那么：

一层树：1 个节点，1 * 500 个 KEY，大小 4K；

二层树：1000 个节点，1000 * 500 = 50W 个KEY，大小 1000 * 4K = 4M

三层树：1000 * 1000 个节点，1000 * 1000 * 500 = 5 亿个KEY，大小 1000 * 1000 * 4K = 4G

可以看到，存储大量的数据（5亿），并不需要太高树的深度（高度3），索引也不是太占内存（4G）。

从联合索引到最左匹配

联合索引是指在 MySQL 数据库的表中基于多个列创建的索引。与单列索引只针对单个列进行索引不同，联合索引可以同时对多个列进行索引，以提高多列查询的性能。联合索引的创建和使用，对于优化数据库查询性能具有重要意义。

对于联合索引，MySQL 从左到右使用索引中的字段，一个查询可以只使用索引中的一部分，但只能是最左侧部分（前缀部分）。例如 key index（a,b,c），可以支持a | a,b| a,b,c 3 种组合进行查找，但不支持 b, c 进行查找。当最左侧字段是常量引用时，索引就十分有效。

最左匹配原则：

在通过联合索引检索数据时，从索引中最左边的列开始，一直向右匹配，如果遇到范围查询（>、<、between、like 等），当前字段使用前半段索引（算是断点），就停止后边的匹配。

举例：对字段 (a, b, c) 建立联合索引，现在有这样一条查询语句：

1 2	WHERE a > xxx AND b=yyy AND c=zzz WHERE a LIKE 'xxx%' AND b=yyy AND c=zzz

在这个条件语句中，只有 a 用到了索引，后面的 b,c 就不会用到索引。这就是“如果遇到范围查询(>、<、between、like等)，就停止后边的匹配”的意思。

PS： 优化器偷偷干的事。如果建的索引顺序是 (a, b)，而查询的语句是 WHERE b = xxx AND a = xxx; 为什么还能利用到索引？

理论上索引对顺序是敏感的，但由于 MySQL 的查询优化器会自动调整 where 子句的条件顺序以使用适合的索引，所以 MySQL 不存在 where 子句的顺序问题而造成索引失效。当然了，SQL书写的好习惯要保持，这也能让其他同事更好地理解你的SQL。

PS：违背最左原则导致索引失效的情况。

假设以联合索引 abc_index(a, b, c) 来进行讲解。

1°缺失优先级最高的索引

当查询 WHERE b=xxx AND c=xxx 这种没有以优先级最高的 a 为条件来检索时，B+ 树就不知道第一步该查哪一个节点，导致去走全表扫描了（即不走索引）。因为建立搜索树时 a 是第一个比较因子，必须要先根据 a 来搜索，进而才能往后继续查询 b 和 c。

2°缺失优先级居中的索引

当查询 WHERE a=xxx AND c=XXX 这样的数据来检索时。B+ 树可以用 a 来指定第一步搜索方向，但由于下一个字段 b 的缺失，所以只能把 a = xxx 的数据主键 ID 都找到，通过查到的主键 ID 回表查询相关行，再去匹配 c=xxx的数据了。当然，这至少把 a = xxx 的数据筛选出来了，总比直接全表扫描好多了。

每一次的探索都是一个成长的过程🍃，我深信知识📖的积累是一场不断进步的旅程。

这篇博客是我学习过程中的一个小小总结，我希望这些分享能够为您带来一些启发。

如果您在阅读中发现任何勘误或有其他观点和经验想要分享，我非常欢迎您在评论中提出😃。

【References】