简介

索引的出现其实就是为了提高数据查询的效率，就像书的目录一样。一本 500 页的书，如果你想快速找到其中的某一个知识点，在不借助目录的情况下，那我估计你可得找一会儿。同样，对于数据库的表而言，索引其实就是它的“目录”。

索引的常见模型

哈希

哈希表是一种以键 - 值（key-value）存储数据的结构，我们只要输入待查找的键即 key，就可以找到其对应的值即 Value。哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。
不可避免地，多个 key 值经过哈希函数的换算，会出现同一个值的情况（哈希冲突）。处理这种情况的一种方法是，拉出一个链表。假设，你现在维护着一个身份证信息和姓名的表，需要根据身份证号查找对应的名字，这时对应的哈希索引的示意图如下所示：

这样，如果遇到哈希冲突的数据，只需要再遍历一下链表就行了。
使用哈希数据结构的索引的优势在于查询效率高，在没有哈希冲突的情况下为O(1) 时间复杂度，但是遇到非等值查询哈希算法就歇菜了，比如范围查找，模糊查询这些基本的查询方式哈希表就体现不出优势而来，基本只能遍历。
总结，哈希表这种结构只适用于等值查询的场景。

有序数组

有序数组在等值查询和范围查询场景中的性能就都非常优秀。还是上面这个根据身份证号查名字的例子，如果我们使用有序数组来实现的话，示意图如下所示：
有序数组在查找方面也很快，使用二分查找的时间复杂度为 O(log(N))，范围查找也是这种数据结构的优势。
如果仅仅查看查询效率，那么有序数组就是最好的数据结构了，但是在需要更新数据的时候就麻烦了，在中间插入一个数据得挪动后面所有的记录，成本太高。
总结，有序数组只适用于静态存储引擎，比如你要保存的是 2017 年某个城市的所有人口信息，这类不会再修改的数据。

二叉搜索树

二叉搜索树也是课本里的经典数据结构了。还是上面根据身份证号查名字的例子，如果我们用二叉搜索树来实现的话，示意图如下所示：

二叉搜索树的特点是：父节点左子树所有结点的值小于父节点的值，右子树所有结点的值大于父节点的值。这样如果你要查 ID_card_n2 的话，按照图中的搜索顺序就是按照 UserA -> UserC -> UserF -> User2 这个路径得到。这个时间复杂度是 O(log(N))。
当然为了维持 O(log(N)) 的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是 O(log(N))。
树可以有二叉，也可以有多叉。多叉树就是每个节点有多个儿子，儿子之间的大小保证从左到右递增。二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上。
你可以想象一下一棵 100 万节点的平衡二叉树，树高 20。一次查询可能需要访问 20 个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 20 个 10 ms 的时间，这个查询可真够慢的。
总结，二叉搜索树的树高不好控制，效率太低。

InnoDB 索引模型

数据结构

InnoDB 引擎使用的索引数据结构，本质上是一个多叉树，特点是只有叶子节点才存储值，其他的节点只存储索引信息，且叶子节点上的值有序。

索引的分类

根据叶子结点的内容分

根据叶子节点的内容，索引分为主键索引（聚簇索引）和非主键索引（二级索引），主键索引的叶子节点上存储的是主键对应的整行记录的值，而非主键索引的叶子节点上存储的是该索引对应的主键的值，如下图所示（ID 为主键，k 为非主键索引）：

基于主键索引和非主键索引的查询有什么区别？

以上面的图为例，有这样两条SQL 语句：

select * from T where ID=500
select * from T where k=5

第一条 SQL 使用了主键索引，只需要搜索 ID 这一颗索引树。
而第二条 SQL，由于 select 需要查询整行的数据，因此InnoDB 需要先搜索 k 这颗索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为*回表。
也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。

索引的维护

插入和删除

B+ 树为了维护索引有序性，在插入新值的时候需要做必要的维护。以上面这个图为例，如果插入新的行 ID 值为 700，则只需要在 R5 的记录后面插入一个新记录。如果新插入的 ID 值为 400，就相对麻烦了，需要逻辑上挪动后面的数据，空出位置。
而更糟的情况是，如果 R5 所在的数据页已经满了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能自然会受影响。
除了性能外，页分裂操作还影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约 50%。
当然有分裂就有合并。当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。

自增主键的使用场景

为了避免叶分裂这种情况发生，许多的教程推荐建表时采用自增主键，因为自增主键的每一次插入都是追加操作，不会挪动其他的记录。
设置主键时，除了性能还需要考虑存储空间的影响，主键占用的空间越小，那么非主键索引上的叶子节点能存储的内容也就越多；相同数据规模下，非主键索引的占用空间也就越小；索引树层数相同的情况下，能存储的数据也就越多。
而使用自增主键，整形只需要 4 个字节，长整型（bigint）则是 8 个字节，往往小于业务字段的大小。因此，从性能和存储空间的考量，自增主键往往是更合理的选择。
有没有什么场景适合用业务字段直接做主键的呢？还是有的。比如，有些业务的场景需求是这样的：

只有一个索引；
该索引必须是唯一索引。

这就是典型的 KV 场景。由于没有其他索引，所以也就不用考虑其他索引的叶子节点大小的问题。
这时候我们就要优先考虑上一段提到的“尽量使用主键查询”原则，直接将这个索引设置为主键，可以避免每次查询需要搜索两棵树。

索引的操作

# 删除索引
alter table T drop index k;
# 添加索引
alter table T add index(k);
# 删除主键
alter table T drop primary key;
# 添加主键
alter table T add primary key(id);
# 重建索引
alter table T engine=InnoDB

索引的优化

回表

在上文基于主键索引和非主键索引的查询有什么区别？中，我们讲到了回表的概念。下面，我们会对这个现象进行深入学习和有关这个现象的 MySQL 索引优化技巧。

什么是回表

下面，我们以表 T 为例，下面是T 的建表语句：

mysql> create table T (
  ID int primary key,
  k int NOT NULL DEFAULT 0, 
  s varchar(16) NOT NULL DEFAULT '',
  index k(k))
  engine=InnoDB;
insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

以 select * from T where k between 3 and 5 这条 SQL 为例,以下是这条语句的执行流程：

在 k 索引树上找到 k=3 的记录，取得 ID = 300；
再到 ID 索引树查到 ID=300 对应的 R3；
在 k 索引树取下一个值 k=5，取得 ID=500；
再回到 ID 索引树查到 ID=500 对应的 R4；
在 k 索引树取下一个值 k=6，不满足条件，循环结束。

在这个过程中，回到主键索引树搜索的过程，我们称为回表。可以看到，这个查询过程读了 k 索引树的 3 条记录（步骤 1、3 和 5），回表了两次（步骤 2 和 4）。

覆盖索引

上文中，我们介绍了什么是回表，接下来，我们会介绍一个常用来规避回表这个过程的优化方式——覆盖索引。
上文中回表之所以会发生是因为我们要查询的是结果集是 select *，而一整行的数据只存在聚簇索引中，查询语句要想获取结果集必须在聚簇索引中重新查询一次。
但是，如果查询的是 select ID，那么情况就不一样了，ID 的值已经存储在 k 的索引树上了，可以直接返回结果集。也就是说，在这个查询里面，索引 k 已经“覆盖了”我们的查询需求，我们称为覆盖索引。
由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。

索引

简介