当某一个SQL查询比较慢，分析后你可能就会说“给某个字段加个索引吧”。 到底什么是索引，索引又是如何工作的呢？

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

索引的常见模型

索引的出现是为了提高查询效率，但是实现索引的方式却有很多种。
提高读写效率的数据结构很多，先介绍三种常见/较简单的数据结构：哈希表、有序数组和搜索树。

下面我主要从使用的角度，为你简单分析一下这三种模型的区别。

  1. 哈希表是一种以键-值（key-value）存储数据的结构。哈希的思路很简单，把值放在数组里，用一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置。
  • 处理冲突的一种方法：拉出一个链表。
  • 哈希表这种结构适用于只有等值查询的场景，比如Memcached及其他一些NoSQL引擎。（无序）
  1. 有序数组在等值查询 / 范围查询的场景中性能优秀。（如利用二分查找）
  • 有序数组索引只适用于静态存储引擎，比如你要保存的是2017年某个城市的所有人口信息，这类不会再修改的数据。（更新不方便）
  1. 二叉搜索树也是课本里的经典数据结构了。

二叉树搜索效率最高，但实际大多数据库存储不使用二叉树。原因：索引既存在内存，还写到磁盘。

  • 为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。那么，我们就不应该使用二叉树，而是要使用“N叉”树。这里，“N叉”树中的“N”取决于数据块的大小。

    以InnoDB的一个整数字段索引为例，这个N差不多是1200。这棵树高是4的时候，就可以存1200的3次方个值，这已经17亿了。考虑到树根的数据块总是在内存中的，一个10亿行的表上一个整数字段的索引，查找一个值最多只需要访问3次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。

  • N叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。

  • 数据库技术发展到今天，跳表、LSM树等数据结构也被用于引擎设计中。

你心里要有个概念，数据库底层存储的核心就是基于这些数据模型的。每碰到一个新数据库，我们需要先关注它的数据模型，这样才能从理论上分析出这个数据库的适用场景。

现在，我们一起进入相对偏实战的内容吧。
在MySQL中，索引是在存储引擎层实现的，所以不同存储引擎的索引的工作方式并不一样。而即使多个存储引擎支持同一种类型的索引，其底层的实现也可能不同。
由于InnoDB存储引擎在MySQL数据库中使用最广泛，所以下面以InnoDB为例分析其中的索引模型。

InnoDB 的索引模型

在InnoDB中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。
InnoDB使用了B+树索引模型，数据都存储在B+树中。每一个索引在InnoDB里面对应一棵B+树。

假设，我们有一个主键列为ID的表，表中有字段k，并且在k上有索引。
这个表的建表语句是：
create table ``T(
**id** int primary key,
**k **int not null,
name varchar(16),
index (k)
)engine=InnoDB;
表中R1~R5的(ID,k)值：(100,1)、(200,2)、(300,3)、(500,5)和(600,6)，两棵树的示例示意图如下：
image.png
图4 InnoDB的索引组织结构

从图中不难看出，根据叶子节点的内容，索引类型分为主键索引和非主键索引。

  • 主键索引的叶子节点存的是整行数据。在InnoDB里，主键索引也被称为聚簇索引。
  • 非主键索引的叶子节点内容是主键的值。在InnoDB里，非主键索引也被称为二级索引。

根据上面的索引结构说明，我们来讨论一个问题：基于主键索引和普通索引的查询有什么区别？

  • 如果语句是select * from T where ID=500，即主键查询方式，则只需要搜索ID这棵B+树；
  • 如果语句是select from T where k=5，即普通索引查询方式，则需要先搜索k索引树，得到ID的值为500，再到ID索引树搜索一次。这个过程称为*回表。

总结：基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。

索引维护

B+树为了维护索引有序性，在插入新值的时候需要做必要的维护。

以上面这个图为例，

  1. 如果插入新的行ID值为700，则只需要在R5的记录后面插入一个新记录。
  2. 如果新插入的ID值为400，就相对麻烦了：需要逻辑上挪动后面的数据，空出位置。
  3. 而更糟的情况是，如果R5所在的数据页已经满了，根据B+树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能自然会受影响。
  • **除了性能外，页分裂操作还影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约50%。**

基于上面的索引维护过程，我们来分析一下哪些场景下应该使用自增主键，而哪些场景下不应该。

  • 自增主键是指自增列上定义的主键： NOT NULL PRIMARY KEY AUTO_INCREMENT。
  1. 适合自增主键的场景

（1）性能。自增主键的插入模式：每次插入都是追加操作，不涉及挪动其他记录，不触发叶子节点的分裂。而有业务逻辑的字段做主键，则往往不容易保证有序插入，这样写数据成本相对较高。
（2）存储空间。

假设表中确实有一个唯一字段，比如字符串类型的身份证号，那用身份证号 还是 自增字段做主键？

  • 由于每个非主键索引的叶子节点上都是主键的值。如果用身份证号做主键，那么每个二级索引的叶子节点占用约20个字节，而如果用int做主键，则只要4个字节，如果是bigint则是8个字节。

显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。

  1. 适合用业务字段直接做主键的场景
    1. 只有一个索引；
    2. 该索引必须是唯一索引。

    你一定看出来了，这就是典型的KV场景。

由于没有其他索引，所以也就不用考虑其他索引的叶子节点大小的问题。
优先考虑“尽量使用主键查询”原则，直接将这个索引设为主键，可避免每次查询需要搜索两棵树。

小结

  1. 分析了数据库引擎可用的数据结构，
  2. 介绍了InnoDB采用的B+树结构，
  3. 为什么InnoDB要这么选择。
  • B+树能够很好地配合磁盘的读写特性，减少单次查询的磁盘访问次数。
  • 由于InnoDB是索引组织表，一般情况下我会建议你创建一个自增主键，这样非主键索引占用的空间最小。但事无绝对，
  1. 我也跟你讨论了使用业务逻辑字段做主键的应用场景。

思考

对于上面例子中的InnoDB表T，

  • 如果你要重建索引 k，你的两个SQL语句可以这么写 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);

问题：上面这两个重建索引的作法，说出你的理解。如果有不合适的，为什么，更好的方法是什么？

为什么要重建索引？

  • 索引可能因为删除 / 页分裂等原因，导致数据页有空洞。重建索引的过程会创建一个新的索引，把数据按顺序插入，这样页面的利用率最高，也就是索引更紧凑、更省空间。
  • 重建索引k的做法是合理的，可以达到省空间的目的。
  • 但是，重建主键的过程不合理。不论是删除主键还是创建主键，都会将整个表重建。所以连着执行这两个语句的话，第一个语句就白做了。这两个语句，你可以用这个语句代替 ： alter table T engine=InnoDB。（《为什么表数据删掉一半，表文件大小不变？》将分析这条语句的执行流程）