04 | 深入浅出索引（上）

此系列文章为极客时间课程《MySQL 实战 45 讲》的学习笔记！

索引的常见模型

可以提供查询效率的数据结构有很多，常见的有三种：哈希表、有序数组、搜索数。

• 哈希表是一种以 key-value 形式存储的数据结构。输入一个 key，通过固定的哈希算法，计算出这个 key 存储在数组的位置，若多个 key 计算的位置相同（也就是hash冲突），则用链表存储。这种数据结构的弊端是范围查找的效率非常低，需要全部扫描。哈希表这种结构适用于只有等值查询的场景。
• 有序数组中存储的数据是按照顺序依次存储的数据中，它在等值查询和范围查询中都是非常高效的。但是一旦涉及到更新或者新增时，效率就变得非常低，因为需要移动数组中的元素，以便满足有序。所以，有序数组索引只适用于静态存储引擎，比如你要保存的是 2017 年某个城市的所有人口信息，这类不会再修改的数据。
• 搜索数既能解决查询问题，又能解决更新问题，而且多叉搜索数还可以降低IO 磁盘的交互，从而提升查询效率。

InnoDB 的索引模型

在 MySQL 的InnoDB 存储引擎中，索引使用的是 B+ 树的存储结构，这种结构的特点是非叶子节点存储的是索引值，这样可以尽量使每个数据页存储最多的索引，叶子节点存储的是索引值对应的那一行数据。并且叶子节点之间是用双向链表连接的，且是按照顺序连接，这样就可以做范围查找。

InnoDB 中的索引分为主键索引（聚簇索引）和非主键索引（二级索引）。

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

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

索引维护

建立索引可以有效的提升查询效率，但是会不可避免的带来索引维护问题。

比如上面的图中我们添加一条 ID 是 700 的数据，则直接在 R5 的后面添加即可，此时的效率影响不大，但是要新增一条 ID 是 400 的数据，就需要在 R3 和 R4 中间添加了，这时若这个数据页满了，就会有页分裂的情况，就是产生一个新的数据页，将原数据页的一部分数据移动到新的数据页，此时数据页的利用率就低了。那么在删除数据时，若数据页的数据很少，且相邻数据也的数据也不多时，就会合并两个数据页，节省空间，这个过程叫做页分裂的逆向过程。

所以我们在日常创建数据库表的时候，建议主键自增，这样每次添加数据就不会产生页分裂了。