深入浅出数据库索引

一、索引的常见模型

1. 哈希表

是键值对（key-value）存储结构，只要根据 key 就可以找到 value。

可以理解为一个数组，对 key 进行哈希计算，换算成一个确定的位置，把 value 放入此位置。

因为存储hash冲突的情况，多个value可能在同一个位置上，使用链表，后来的就追加到链表中。

例如存储身份证号和名字的信息：

这种结构只适用于 等值查询 场景，如果要找某个区间的用户就需要全部扫描一遍了。

2. 有序数组

按照身份证号递增的顺序保存。

有序数组非常适合 等值查询和范围查询 。

例如查找 [ID_X, ID_Y] 内的，先用二分法找到 ID_X，然后向右遍历，直到找到大于 ID_Y 的就结束了。

有序数组的优势是查询效率高，缺点是更新麻烦，插入一个记录就需要挪动后面所有的记录，效率低。

有序数组索引只适用于 静态存储引擎 ，不会修改的数据情况。

3. 搜索树

先看最经典的二叉树：

二叉树中，左儿子 < 父节点，父节点 < 右儿子。

例如查找 ID_2，路径就是：

UserA -> UserC -> UserF -> User2

二叉树搜索效率最高，但实际数据库却不适用二叉树，因为索引是需要写到磁盘上的，例如一棵100万节点的二叉树，高度是20，一次查询需要访问20个数据块，从磁盘随机读一个数据块需要10ms左右的寻址时间，那么这个查询就需要200ms，很慢了。

所以需要使用N叉树，每个节点可以有多个儿子，儿子间从左到右递增，这样可以让查询过程访问尽量少的数据块儿。

二、InnoDB 索引

1. 为什么使用 B+ tree 索引模型？

例如插入数据：1,a,b,c,d,e。

二叉树的结构：

红黑树的结构：

B+ tree 的结构：

二叉树上面说过，效率太低，高度完全不可控，红黑树优化了不少，但高度仍然不可控，B+ tree 的高度恒定，而且只在叶子节点中存储数据，叶子节点间也是顺序链接的，做范围查找时非常高效。

2. 为什么建议使用自增主键？

涉及到1个概念：页分裂。

插入时，如果新值比现有值都大，那么只需要在后面插入即可，否则需要挪动现有数据。

如果插入目标位置的数据页满了，就要申请新的数据页，并挪动数据。

所以自增ID能够连续申请页空间，提升空间的操作效率和利用率。

三、MySQL 索引的3个重要概念

例如有一个表：

有2个索引，ID 和 k。

InnoDB 主键索引的叶子节点存储的是行数据，非主键索引的叶子节点存储的是主键。

查询 k 在 [3,5] 区间内的所有行数据：

select * from T where k betweet 3 and 5

在 k 索引树上找到符合条件的，得到 ID 值，回到 ID 索引树取得行数据。

回到主键索引搜索的过程称为 回表 。

1. 覆盖索引

上面的查询如果改为：

select ID from T where k betweet 3 and 5

只查询ID这个字段，那么只搜索 k 树索引即可，不需要回表了。

索引 k 已经覆盖了我们的查询需求，这种情况称为 覆盖索引 。

覆盖索引可以显著提升查询性能，所以做优化时可以考虑是否适合使用此方式。

例如用户表，有身份证号、姓名字段，身份证号是唯一的，建了一个索引。

如果业务中有根据身份证号搜索姓名的高频需求，就可以创建一个（ 身份证号+姓名 ）的联合索引，实现覆盖索引，即使增加了索引的维护成本也是值得的。

2. 最左前缀原则

索引项是按照字段顺序排序的。

查询“张三”时，会快速定位到 ID_4，然后向后遍历需要的结果。

查询“张%”也可以用这个索引，定位到 ID_3，向后找，直到不满足条件为止。

所以，只要满足最左前缀就可以用到索引。

涉及到一个问题：如何安排索引内的字段顺序？

需要考虑 索引的复用能力 ，如果通过调整顺序，可以少维护一个索引，那么这个顺序就是优先考虑的。

3. 索引下推

例如用户表有字段：ID,name,age,ismale …，建有一个索引（name,age）。

现在查询：

select * from tuser where name like '张 %' and age=10 and ismale=1;

MySQL5.6 之前，查询过程是：

根据索引找到以“张”开头的名字的ID，然后回表，进一步判断 age 和 ismale。

在 5.6 引入了 索引下推 ，在索引中找到“张”开头的以后，先在索引中判断其 age 是否符合条件，因为 age 已经在索引中，不需要回表判断了，把 age 不符合要求的先过滤掉，然后再回表判断 ismale，这就减少了回表次数，提升了查询效率。

欢迎工作一到五年的Java工程师朋友们加入Java程序员开发： 721575865

群内提供免费的Java架构学习资料（里面有高可用、高并发、高性能及分布式、Jvm性能调优、Spring源码，MyBatis，Netty,Redis,Kafka,Mysql,Zookeeper,Tomcat,Docker,Dubbo,Nginx等多个知识点的架构资料）合理利用自己每一分每一秒的时间来学习提升自己，不要再用"没有时间“来掩饰自己思想上的懒惰！趁年轻，使劲拼，给未来的自己一个交代！