MySQL实战45讲-04.深入浅出索引（上）总结

对Mysql实战45讲索引部分总结。

1.索引的常见模型

索引常见的模型有三种：哈希表、有序数组、搜索树

（1）哈希表

哈希表是以键-值结构存储的数据结构，数据结构主体是一个数组，同一个key下可能会悬挂链表。

由于哈希表是根据key经过哈希函数计算后放入数组的，所以哈希表中存放的数据不是根据key值顺序存放的，这就导致哈希表的范围查询非常慢（下面会提到），但是如果是新增或删除数据的时候则不需要进行数据的挪动，只需要添在之前的数据后就可以了，新增效率和删除效率快。

哈希表索引的等值查询非常快，只需要把key值根据哈希函数算出后直接在哈希表中获取。

但是哈希表的区间查询非常慢，这是因为上面我们提到，哈希表中存放的数据并不是根据key值顺序存放的，所以使用哈希表索引进行范围查询时，只能将哈希表中每个元素遍历进行查询，效率很低。

（2）有序数组

有序数组则解决了哈希表范围查询慢的缺点，我们只需要通过二分法找到第一个符合范围条件的数据，然后向后遍历获取元素知道不满足范围条件的数据就行了，而且由于使用二分法查找，所以等值查询效率也高。

但是更新数据的时候，有序数组索引就涉及到了数据的挪动，成本太高，效率太低。

所以有序数组只适用于静态存储引擎，比如只需要保存2017年某个城市的所有人口这种不会有任何变化、只需要进行查询的数据。

（3）二叉搜索树

二叉搜索树即平衡二叉树，特点就是左子树中节点的值要小于父节点，右子树中节点的值要大于父节点。

二叉树的搜索效率是O(log(N))，而且我们更新数据的时候还要保持这个数是平衡二叉树，所以更新的时间复杂度也是O(log(N))。

虽然平衡二叉树的查找和更新效率都还不错，但实际上存储引擎中并不会使用平衡二叉树作为索引，因为一个节点只有两个分叉，如果数据量巨大，就需要二叉树索引层级很深，但是索引不只存于内存中，还存于磁盘上，假设树高20，极端下如果我们查询到了树的叶子节点层，我们就需要访问20个数据块（一个数据块就是一个节点），从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说，单独访问一个行可能需要 20 个 10 ms 的时间，效率很慢。

为了尽可能少的读磁盘，就必须让查询过程访问尽量少的数据块，就需要让层级变浅，也就是分叉变多，变为N叉树，N叉树中的N取决于数据块的大小。

2.InnoDB索引模型

在InnoDB中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表，InnoDB使用了B+树索引，所以在InnoDB引擎中，数据都是存储在B+树中的，每一个索引在InnoDB中都对应着一颗B+树，即InnoDB中的表，就是一颗颗B+树。

现使用建表语句创建一个表，并为k字段创建一个索引：

mysql> create table T(
id int primary key, 
k int not null, 
name varchar(16),
index (k))
engine=InnoDB;

其中id键，拥有主键索引，k也拥有索引，所以表中的数据是以两棵B+Tree的形式存在的：

可以看出，在主键索引中，叶子节点存放的数据是一整行的数据，在InnoDB中，主键索引也被称为聚簇索引（clustered index）；

非主键索引的叶子节点存放的数据是该行的主键，InnoDB中，非引也被称为二级索引（secondary index）；

那通过主键索引查询和通过非主键索引查询有什么区别？

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

也就是说我们如果通过非主键索引进行查询，会导致我们多扫描一次索引树，这个过程称为回表，回表查询会导致查询效率降低。

索引维护

（1）页分裂与页合并

为了维护B+树索引的有序性，在插入新值的时候需要做必要的维护，来确保索引满足B+树的有序性。以上图为例，如果新插入一个id为700的值，只需要在R5节点后追加即可，但是如果插入一个id为400的值，就需要挪动数据，将400插到空位中，这就相对麻烦些了。

而且如果R5所在的这一页的数据已经满了，就需要重新申请一个新的数据页，然后将旧节点中的一些数据挪动进去，这个过程叫做页分裂，这种情况下，效率必然更低。

页分裂除了影响性能外，还会影响数据页的利用率，原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约50%。

当然，有页分裂就有页合并，当相邻的两个页因为删除了数据，利用率降低后，会将两个数据页合并，合并的过程可以看做页分裂过程的逆过程。

（2）自增主键的选择

在某些建表规范中可能会有下面的描述：建表语句里一定要有自增主键。当然事无绝对，我们需要在一些场景下判断是否使用自增主键。

自增主键是指自增列上定义的主键，在建表语句中一般是这么定义的： NOT NULL PRIMARY KEY AUTO_INCREMENT。

使用自增主键作为索引，我们在插入数据的时候只需要在后面一直追加就可以了，不需要挪动其他数据，，也不会触发叶子节点的分裂。

但是如果我们采用有业务逻辑的字段作为主键，则往往不容易保证有序插入，写数据成本较高。

除了上面从性能的角度考虑，我们还可以从存储空间的角度看。业务逻辑字段的长度往往比自增主键要大，比如唯一字段字符串类型的身份证号，由于非主键索引的叶子节点存储的是该表主键，使用身份证号作为主键会导致叶子节点占用空间变大，所以我们最好采用长度小的字段作为主键，自增主键往往满足这个需求。

但是在一些业务环境下使用业务逻辑字段作为主键是合理的，比如下面的业务场景：

• 只有一个索引
• 该索引必须是唯一索引

由于只有一个索引，那么只能是主键索引，也就不存在其他索引，所以不必考虑非主键索引B+树叶子节点的大小问题，这个时候业务逻辑字段作为主键是可以的，但实际中更多的还是采用自增主键作为索引。