MySQL索引 | Keep Moving

对于数据库索引，我们的第一反应就是，让查询变得更快。
为什么会快，当你进行一条数据查询的时候，没有索引的帮助，你只能从头查起，一行一行遍历，直到符合条件为止。索引就像书的目录，你可以通过它，快速定位到你要的章节，从而快速许多。

数据库索引常见数据结构有：

哈希表查询数据时，key根据哈希函数换算得到位置，位置就是value存放的地方。但由于哈希存放数据并不是有序的，所以根据区间查询数据时会很慢。

有序数组查询区间数据时比较高效，然而在插入数据时，需要挪动插入位置后的所有元素，所以更新成本高。

搜索树可以有二叉和多叉，如果使用的是二叉搜索树，时间复杂度是O(log(N))，效率最高，然而二叉树的树高会很高，对于索引写在硬盘上的场景来讲，树的高度决定了访问磁盘的次数，磁盘效率相对内存极其低下，所以为了减少磁盘读写次数，可以使用N叉树（N取决于数据块大小）。

InnoDB的索引

在InnoDB引擎中，索引使用的结构是B+树。
关于B+树是什么一种结构，可以参考这里另外一篇文章：B树(B+树)

对于每一个索引，InnoDB中都会创建一棵B+树。

主键与非主键对应的树是不同的：

两种索引查询的区别就在于，非主键索引查询完之后，需要回到主键索引再搜索一次（回表），也就意味着对非主键索引的查询，会多查找一棵树。

由于索引要保持B+树的结构，那么当新增删除节点时，就会产生树的维护成本。

比如数据页满了，那么需要进行页分裂，而删除时，可能需要页合并。对于分裂和合并，都会使空间利用率发生变化，分裂使得利用率降低，合并提高了利用率。

我们前面提到过，对于非主键索引，索引叶子结点存放的是主键的值，查询了非主键索引树后，还需要进行一次回表，而回表则代表了多一次索引树的搜索。

有没有情况是不需要回表的？
那就是我们要查的值已经在索引树上，比如

1	SELECT id FROM t WHERE index_key BETWEEN 10 AND 20

索引index_key查询完，已经能拿到id的数据，不需要回表。

联合索引也可以避免回表，比如建立联合索引(key1, key2)，当我们根据key1去查询key2的值时，也可以避免回表。

在MySQL里，对联合索引的查询会优先从左边的关键字查起。

假如我们现在的表里有几个字段，其中有字段: key1: int, key2: int。

我们经常需要对(key1, key2)进行查询，也会根据key1单独进行查询。那我们可以建立联合索引(key1, key2)，这个索引可以同时满足两个查询要求。

另外，当我们的查询条件顺序不同时，比如：

1 2	SELECT key1, key2 FROM t WHERE key1 = 10 AND key2 = 12; SELECT key1, key2 FROM t WHERE key2 = 12 AND key1 = 10;

两条语句其实都可以用到联合索引(key1, key2)，这是MySQL进行优化，使得查询满足最左前缀原则，匹配到索引进行查询。

注意：当我们单独对key2进行查询时，该联合索引是无效的，因为它不满足索引的顺序条件。

最左前缀原则，满足的不只是联合索引的最左字段，对于字符串索引来说，它也是满足的。
比如现在有name字段类型为varchar，同时我们为它建立了一个索引。

下面的查询语句是可以命中索引的

1	SELECT id, name FROM t WHERE name LIKE '张%';

「极客时间」-「MySQL实战45讲」