MySQL- 基础概念篇 - 索引

MySQL- 基础概念篇 - 索引

什么是索引
索引的出现其实就是为了提高数据查询的效率，就像书的目录一样。

其实最好的例子就是我们从小就用的字典 里面的声母查询方式就是聚簇索引。 偏旁部首就是二级索引 偏旁部首 + 笔画就是联合索引。 这种方式比较适合人类的思维方式，设计也比较精妙。 还有比较有意思的一种查询方式就是 ES 里的倒排索引，感觉有点反人类，只适合机器用吧。

索引也是保存在磁盘中的，也需要考虑 io 性能，比如顺序 io 和随机 io 的差别。

索引实现方式：索引模型
常见的三种，哈希表、有序数组和搜索树。

哈希表这种结构适用于只有等值查询的场景，大于小于这样的查找，哈希索引的效率都不高

在 hashmap 中，通过 key 计算 hash，数组中保存的是 key-value 键值对 entry

有序数组
有序数组就是将此列数据排序好放到一个数组里面，很容易想到，通过二分查找算法，有序数组在等值查询和范围查询场景中的性能就都非常优秀。
但是有一个缺点，插入一条数据之后需要更新索引，而数组的更新是很慢的，需要把后面所有的元素都往后移动一位（那用链表做索引呢？）
因此有序数组索引只适用于静态存储引擎，数据存进来很少动的那种。

平衡二叉树/平衡 N 叉树
二叉搜索树的特点是：父节点左子树所有节点的值小于父节点的值，右子树所有结点的值大于父节点的值。这个时间复杂度是 O(log(N))。其实就是二分查找。
当然为了维持 O(log(N)) 的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是 O(log(N))。

二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上。而磁盘的读写是很慢的，进行几次分叉就要访问几次磁盘，因此为了减少访问磁盘的次数，我们就要减少树高，那就只能多分几个子节点了，于是就有了 N 叉树（n 就是树的度，注意不要看成树的高度，度表示一个父结点有多少个子结点）

InnoDB 的数据是按数据页为单位来读写的。也就是说，当需要读一条记录的时候，并不是将这个记录本身从磁盘读出来，而是以页为单位，将其整体读入内存。在 InnoDB 中，每个数据页的大小默认是 16KB。

在 MySQL 中，索引是在存储引擎层实现的，所以并没有统一的索引标准，即不同存储引擎的索引的工作方式并不一样。

InnoDB 的索引模型
二叉搜索树的基本概念和重点知识

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

InnoDB 中，每一张表其实就是多个 B+ 树，即一个主键索引树和多个非主键索引树。
主键索引的 b+ 树的叶子节点存储的是具体的行数据，非叶子节点存储的是主键的值。叶子节点之间通过链表连接 非主键索引的叶子节点存储的是主键的值，所以通过非主键索引查询数据时，先找到主键，再去主键索引上根据主键找到具体的行数据
新建索引就是新增一个 B+ 树，查询不走索引就是遍历主 B+ 树。

非主键索引会存储主键索引的值，因此推荐选用短字段当主键索引，不建议将长字段作为索引。
数据页大小固定，键值占用空间越小，一页存的键更多，一次 io 查的就越多，需要的 io 次数越少，查的就越快

索引的使用过程
基于主键索引和普通索引的查询有什么区别？
如果语句是 select * from T where ID=500，即主键查询方式，则只需要搜索 ID 这棵 B+ 树；
如果语句是 select * from T where k=5，即普通索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。
也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。

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

从性能和存储空间方面考量，自增主键往往是更合理的选择。
一般不建议使用业务相关字段作为主键，即使其具有唯一性特性（如身份证）。因为，当业务变更（如身份证升位），就会带来灾难。

有没有什么场景适合用业务字段直接做主键的呢？还是有的。比如，有些业务的场景需求是这样的：
只有一个索引；
该索引必须是唯一索引。
你一定看出来了，这就是典型的 KV 场景

索引重建
千万不要删除表主键

  1. 删除主键会导致所有二级索引失效，危险操作 2、删除主键后，会用 RAWID 作为主键，重建二级索引。如果这时候再创建主键，又会让二级索引失效，失效后再次触发二级索引重建

索引是如何使用的

执行 select * from T where k between 3 and 5，需要执行几次树的搜索操作，会扫描多少行？
假设主键为 ID 有主键索引，k 也有索引

首先在 k 的索引树上搜索满足条件的 k 值对应的主键，然后去主键索引树上找主键对应的整行，每一个满足条件的 k 值都要走一遍这个流程，直到 k 值不满足条件。
因为 k 值的索引树是 b+ 树，都是顺序存储的，所以找起来很快，范围查找也很方便

在这个例子中，由于查询结果所需要的数据只在主键索引上有，所以不得不回表。那么，有没有可能经过索引优化，避免回表过程呢？

二级索引查询结果仅仅是主键
当我们查询语句只需要返回主键时，二级索引的查询结果就已经覆盖到了所有的查询字段 ，这就叫覆盖索引
此时不需要回表查主键索引

由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。

联合索引解析
联合索引，又叫复合索引
https://cloud.tencent.com/developer/news/44861

联合索引具有最左匹配特性。什么意思？
当我们声明索引 KEY index(a,b,c) 的时候，b+ 索引树是按照从左到右的顺序来建立搜索树的，先比较 a，a 相同就比较 b，b 相同就比较 c，这样来排列数据，确定数据的挂接点，当然也以这样的顺序来检索数据。
也就是说 key index (a,b,c). 可以支持 a a,b a,b,c 这几种组合进行查找，但不支持 b,c 进行查找。a,c 也是可以的（索引下推），但是效率要打折扣。
当使用最左侧字段时，索引就十分有效。

同时根据索引声明时的列的顺序，如果排在前面的列出现范围查询，排在后面的列的查询都不能使用索引，（但是依然可以通过索引下推来优化查询），其实可以理解，只有前面的列的值确定时，后面的列的查询才能走索引，前面的列的匹配是一个范围而不是一个固定的值，后面的列的排序就不确定了，即无法走索引。

这让我明白了一点。
索引本质上就是一种预先排序的结果，我们的查询走索引就是复用了预先排序的结果，因此才快，重点是如何复用。

使用等值查询，多列同时查询，索引会一直传递并生效。因此等值查询效率最好。
索引查找遵循最左侧原则。但是遇到范围查询列之后的列索引失效。大于小于，like 查询，in 查询，应该都算范围查询
排序也能使用索引，合理使用索引排序，避免出现 file sort。
关于排序，请看《MySQL- 实践篇 -order by 是怎么工作的》

覆盖索引使用场景

在一个市民信息表上，是否有必要将身份证号和名字建立联合索引？

如果现在有一个高频请求，要根据市民的身份证号查询他的姓名，这个联合索引就有意义了。它可以在这个高频请求上用到覆盖索引，不再需要回表查整行记录，减少语句的执行时间。

当我们建立了一个 key index (a,b,c).这样的联合索引，就不需要再单独为 a 建立索引，但是仍然需要单独为 b 和 c 建立索引（如果有这个查询场景的话）

【索引下推】Index Condition Pushdown，简称 ICP。 是 Mysql 5.6 版本引入的技术优化。旨在 在“仅能利用最左前缀索的场景”下（而不是能利用全部联合索引），对不在最左前缀索引中的其他联合索引字段加以利用——在遍历索引时，就用这些其他字段进行过滤 (where 条件里的匹配)。过滤会减少遍历索引查出的主键条数，从而减少回表次数，提示整体性能。

如果查询利用到了索引下推 ICP 技术，在 Explain 输出的 Extra 字段中会有“Using index condition”。即代表本次查询会利用到索引，且会利用到索引下推。

索引下推技术的实现——在遍历索引的那一步，由只传入可以利用到的字段值，改成了多传入下推字段值。

在最左字段进行范围查询的时候，后续的字段可以通过索引下推发挥作用
索引下推优化（index condition pushdown)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

一个表如果既有主键索引，又有二级索引，那么二级索引，会默认和主键做联合索引。
假设 ID 字段有主键索引，name 字段有二级索引，那么当前数据库可以认为存在一个 顺序为
name，ID 的联合索引。