mysql 索引

前言

• 前言
• msyql分层
• 索引
  • 索引实现
  • 为什么是B+树——B+树的逻辑结构
  • B+树的物理结构——按页批量读写索引数据
  • B+树的物理结构——如何映射逻辑结构
  • B+树的物理结构——页的写入与读取
  • 为什么SELECT * 效率低
• 效率
• explain
• 其它

解决 MySQL 作为硬盘存储技术，要解决读写速度的问题。再简化一下，就是尽量减少 I/O 次数。选择的手段，就是通过索引，来帮我们快速找到特定值，提高查找效率。索引的本质，就是像目录一样的，一种排好序的数据结构。

选择索引是优化器的工作。而优化器选择索引的目的，是找到一个最优的执行方案，并用最小的代价去执行语句。优化器主要会根据以下条件考虑：查询语句中的条件、索引的选择性（基数）、索引的大小和数据类型、数据块的大小、索引的覆盖度。PS：查询优化器并不总是很聪明。

索引是在存储引擎层实现的。在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的，B+ 树适配磁盘读写特性，减少查询所需的磁盘 I/O。根据叶子节点的内容，索引类型分为主键索引和非主键索引。主键索引（聚簇索引）直接存储数据行，而非主键索引（二级索引）存储主键值，并在查询时可能涉及“回表”操作，即先查二级索引再查主键索引。主键索引因需维护唯一性约束，在插入性能上有时逊于非主键索引。

msyql分层

MySQL在SQL计算和数据存储之间设计了一套标准的数据访问控制接口(Plugable Engine Interface)，SQL层通过这个标准的接口进行数据的更新、查询和管理，存储引擎得以作为独立组件实现“热插拔”式集成。

InnoDB的架构是天然为OLTP设计，虽然在TP业务场景下能够有非常优秀的性能表现。但InnoDB在分析型业务场景下的查询效率非常的低。DuckDB 是一个开源的在线分析处理（OLAP）和数据分析工作负载（列式存储）而设计，非常适合成为MySQL的AP存储引擎。两者结合，为MySQL扩展了一种使用场景：分析型业务和主库业务分离，和普通只读实例一样，通过Binlog复制机制从主库复制数据。

索引

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

1. 自增主键的插入数据模式，每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。而身份证号做主键，则往往不容易保证有序插入，这样写数据成本相对较高。
2. 每个非主键索引的叶子节点上都是主键的值。如果用身份证号做主键，那么每个二级索引的叶子节点占用约 20 个字节，而如果用整型做主键，则只要 4 个字节。主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。
3. 典型的 KV 场景适合用业务字段直接做主键：只有一个索引；该索引必须是唯一索引。

基数（优化器选择索引时会参考基数值）：一个索引上不同的值越多，这个索引的区分度就越好。而一个索引上不同的值的个数，我们称之为“基数”（cardinality）。也就是说，这个基数越大，索引的区分度越好。我们可以使用 show index 方法，看到一个索引的基数。基数是一个估计值，MySQL 使用采样统计的方法得到索引的基数：InnoDB 会选择 N 个数据页，统计这些页面上的不同值，得到一个平均值，然后乘以这个索引的页面数，就得到了这个索引的基数。当变更的数据行数超过 一定数量时，会自动触发重新做一次索引统计。

select count(*) 优化：InnoDB 是索引组织表，主键索引树的叶子节点是数据，而普通索引树的叶子节点是主键值。所以，普通索引树比主键索引树小很多。对于 count(*) 这样的操作，遍历哪个索引树得到的结果逻辑上都是一样的。因此，MySQL 优化器会找到最小的那棵树来遍历。在保证逻辑正确的前提下，尽量减少扫描的数据量，是数据库系统设计的通用法则之一。

唯一索引和普通索引在查询性能上差别不大，在插入/更新性能上，如果相关数据页不在内存中时，还需将相关数据页加载到内存以判断是否违反了唯一性约束。

索引实现

《MySQL实战45讲》索引是在存储引擎层实现的

1. 哈希表这种结构适用于只有等值查询的场景，没有办法做范围查找，在 Memcached、Redis 等 NoSQL 数据库中使用比较多。
2. 有序数组索引只适用于静态存储引擎，在需要更新数据的时候就麻烦了。
3. 二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。原因是，索引不止存在内存中，还要写到磁盘上。为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。那么，我们就不应该使用二叉树，而是要使用“N 叉”树。这里，“N 叉”树中的“N”取决于数据块的大小。以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。
4. innodb 采用聚簇索引，所以必须存在主键（一级索引）作为真实数据的存储载体。倘若表中未显式声明主键，则会隐藏字段 row_id 作为一级索引。

为什么是B+树——B+树的逻辑结构

查询需求：

1. 基本查询：即根据主键查询
2. 范围查询
3. 前缀匹配模糊查询
4. 排序和分页

每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上。

InnoDB存储B+Tree节点的方式确实非常精巧，MyISAM主要是记录了主键与对应记录地址（偏移）的映射关系。

B+树的物理结构——按页批量读写索引数据

与操作系统操作磁盘块的逻辑基本一致，操作时以块/页为单位，而不是直接从磁盘上读取记录。事实上，哪怕是访问内存，os也从未按字节读取过数据， 全部是按批量方式读取。

	读取过程	写回磁盘
操作系统读取磁盘块	判断目标数据所在的磁盘块是否在内存（对应的缓冲块），若在则修改数据，不在则读取磁盘块到内存。	操作系统负责将缓冲块同步到磁盘上。修改的缓冲块称为脏块，操作系统会根据脏块的占比决定同步到磁盘期间，是否继续响应用户操作。	磁盘块有超级块和一般数据块的不同，不准确的说，超级块的数据加载到磁盘，刚好是一个superblock list、inode list
innodb引擎读取页	类似	mysql有专门线程负责将脏页（有改动的页）写入到磁盘。因为redo 日志的存在，msyql会根据redo log的剩余空间占比决定在master thread中同步还是异步 将脏页写入到磁盘。	数据页组织在一起刚好是一个B+Tree

1. 有些文件格式（二进制文件），必须整体读取才能解析和展示，有些（主要是文本文件）则可以一部分一部分的解析和展示，比如txt。
2. 有些文件格式，在内存的数据结构与磁盘一致。有些则需要转换后写入到磁盘上。

读取记录，一次读取一页，还带来一个好处，一个页的数据结构是一个整体，支持复杂的数据结构。假设一个记录10byte，无需页offset 0~9就是第一条记录，offset10~19是第二条记录（以前我就是这么想的），即用链表而不是位置维持数据的有序性。

这其实解决了笔者一直以来的一个困惑：假设一个数据库表的主键按1~1亿分布，我先插入一条主键=1的记录，再插入主键=1000的记录，再插入主键从2~100的记录。无论采用何种索引方式，每次插入，都意味着数据文件或者索引文件中数据记录的移动，操作起磁盘来就不太高效。

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。在mysql中，将一个B+Tree节点的大小设为等于一个内存页，这样每个节点只需要一次I/O就可以完全载入。B-Tree中一次检索最多需要h（树的高度）-1次I/O（根节点常驻内存）。

B+树的物理结构——如何映射逻辑结构

逻辑结构	物理结构
非叶子节点	索引页
叶子节点	数据页

File Header 比较重要的几个字段

名称	大小	描述
FIL_PAGE_PREV	4	该页的上一个页
FIL_PAGE_NEXT	4	该页的下一个页
FIL_PAGE_LSN	8	该页最后被修改的LSN
FIL_PAGE_TYPE	2	该页的类型，0x45BF为数据页

Page Header 比较重要的几个字段

名称	大小	描述
PAGE_LAST_INSERT	2	最后插入记录的位置
PAGE_N_RECS	2	该页中记录（User Record）的数量
PAGE_LEVEL	2	该页在索引树中位置，0000代表叶子节点

数据页存放的是完整的每行的记录，而在非数据页的索引页中，存放的仅仅是键值及指向数据页的偏移量（页号），而不是一个完整的行级录。

Page 与 Page 之前组成双向链表（PS：貌似只有同级的页由双向链表关联），页按照主键的顺序排序，这样page 与page 可以在磁盘上隔的好远，但逻辑上是连续的。

B+树的物理结构——页的写入与读取

按页的方式进行内存和磁盘的交互，并且几个页组织在一起刚好是一个完整的数据结构（B+Tree），在内存中改变B+Tree的操作负担不大，然后有一个周期性的机制将页刷新回磁盘。

查询时

1. 树的高度一般是2~4，假设树的高度是3，则page level=2 即表示根节点。先加载根节点，然后按需加载下一个page level的页 直到叶子/数据页。
2. B+Tree索引本身并不能直接找到具体的一行记录，只能找到该行记录所在的页。
3. 数据库把页载入到内存中，然后通过Page Directory（存放着行级录在页内的相对位置）再进行二分查找

《MySQL实战45讲》当内存数据页跟磁盘数据页内容不一致的时候，我们称这个内存页为“脏页”。内存数据写入到磁盘后，内存和磁盘上的数据页的内容就一致了，称为“干净页”。平时执行很快的更新操作，其实就是在写内存和日志，而 MySQL 偶尔“抖”一下的那个瞬间，可能就是在刷脏页（flush）。什么情况会引发数据库的 flush 过程呢？

1. InnoDB 的 redo log 写满了。这时候系统会停止所有更新操作，把 checkpoint 往前推进，redo log 留出空间可以继续写。checkpoint 可不是随便往前修改一下位置就可以的，需要将两个点之间的日志，对应的所有脏页都 flush 到磁盘上。
2. 系统内存不足。当需要新的内存页，而内存不够用的时候，就要淘汰一些数据页，空出内存给别的数据页使用。如果淘汰的是“脏页”，就要先将脏页写到磁盘。
3. MySQL 认为系统“空闲”的时候，刷一点“脏页”
4. MySQL 正常关闭

你要正确地告诉 InnoDB 所在主机的 IO 能力（innodb_io_capacity），这样 InnoDB 才能知道需要全力刷脏页的时候，可以刷多快。此外，innodb 会根据脏页比例（innodb_max_dirty_pages_pct） 和 redo log 写盘速度 来计算 刷盘速度。MySQL 中的一个机制（innodb_flush_neighbors具体控制），可能让你的查询会更慢：在准备刷一个脏页的时候，如果这个数据页旁边的数据页刚好是脏页，就会把这个“邻居”也带着一起刷掉；而且这个把“邻居”拖下水的逻辑还可以继续蔓延/连坐，也就是对于每个邻居数据页，如果跟它相邻的数据页也还是脏页的话，也会被放到一起刷。找“邻居”这个优化在机械硬盘时代是很有意义的，而如果使用的是 SSD 这类 IOPS 比较高的设备的话，建议你把 innodb_flush_neighbors 的值设置成 0。

为什么SELECT * 效率低

为什么大家都说SELECT * 效率低 其中一个原因是非聚簇索引/辅助索引。

有一个表为t(a,b,c,d,e,f)，其中，a为主键，b列有索引。那么，在磁盘上有两棵 B+ 树，即聚集索引和辅助索引（包括单列索引、联合索引），分别保存(a,b,c,d,e,f)和(a,b)，如果查询条件中where条件可以通过b列的索引过滤掉一部分记录，查询就会先走辅助索引，如果用户只需要a列和b列的数据，直接通过辅助索引就可以知道用户查询的数据。

如果用户使用select *，获取了不需要的数据，则首先通过辅助索引过滤数据，然后再通过聚集索引获取所有的列(回表（Bookmark Lookup / 回表查询）)，这就多了一次b+树查询，速度必然会慢很多。

由于辅助索引的数据比聚集索引少很多，很多情况下，通过辅助索引进行覆盖索引（通过索引就能获取用户需要的所有列），都不需要读磁盘，直接从内存取，而聚集索引很可能数据在磁盘（外存）中（取决于buffer pool的大小和命中率），这种情况下，一个是内存读，一个是磁盘读，速度差异就更显著了，几乎是数量级的差异。

效率

对于MySQL，最简单的衡量查询开销的三个指标如下：

1. 响应时间：服务时间和排队时间之和。服务时间是指数据库处理这个查询真正花了多长时间。排队时间是指服务器因为等待某些资源而没有真正执行查询的时间——可能是等I/O操作完成，也可能是等待行锁。
2. 扫描的行数：一条查询，如果性能很差，最常见的原因是访问的数据太多。大部分性能低下的查询都可以通过减少访问的数据量的方式进行优化。有时候也可能是访问了太多的列；（每次看到SELECT*的时候都需要用怀疑的眼光审视，是不是真的需要返回全部的列，很可能不是必需的。取出全部列，会让优化器无法完成索引覆盖扫描这类优化，还会为服务器带来额外的I/O、内存和CPU的消耗）
3. 返回的行数：会给服务器带来额外的I/O、内存和CPU的消耗（使用limit限制返回行数）

explain

explain结果中的type（the join type）字段代表什么意思？在 MySQL 内部所有查询都会被当成“多表 join 的特例”来处理，MySQL 的核心执行器是 Nested Loop Join（嵌套循环）模型。即便是单表查询，也被当作join 流程中的“第一层循环”：

for each row in table:
    check condition

type描述了如何访问这张表/找到所需数据使用的扫描方式（The join type indicates how MySQL finds rows in a table）。最为常见的扫描方式有：

1. system：系统表，少量数据，数据已经加载到内存里，往往不需要进行磁盘IO，是速度最快的；
2. const：主键等值/一次定位；
3. eq_ref：主键索引(primary key)或者非空唯一索引(unique not null)等值扫描；对于前表的每一行(row)，后表只有一行被扫描。
4. ref：非主键非唯一索引等值扫描/多次索引查找；
5. range：范围扫描；
6. index：索引树扫描/扫完整索引；
7. ALL：全表扫描(full table scan)；

Extra contains additional information about how MySQL executes the query. 描述执行过程中额外发生的操作或优化

1. 最优
   1. Using index, 查询所需所有列都在索引树上，无需回表访问数据行。
   2. Select tables optimized away, 优化器直接从索引取聚合值（如 MAX(id)、MIN(id)），无需访问表。
2. 优秀
   1. Using index condition, 命中索引，但需回表
   2. Using index for group-by, GROUP BY/DISTINCT 用索引完成，无需临时表 / 文件排序。
3. 一般
   1. Using where, 用 WHERE 条件过滤数据（可能在索引扫描后、也可能在回表后）。
4. 中危
   1. Using join buffer (Block Nested Loop), 多表连接时，关联字段无索引，用连接缓冲区做嵌套循环。
5. 高危
   1. Using filesort（文件排序）, 数据量大时极慢, 需给 ORDER BY 字段加索引，或用覆盖索引包含排序列。
   2. Using temporary, 需创建临时表存中间结果（常见于 GROUP BY/ORDER BY 不同字段）。
6. Impossible WHERE, WHERE 条件永远不成立（如 1=2），直接返回空集。

其它

索引可以提高查询效率，是不是一张表上索引越多越好呢，其实不然。索引可以提高效率也可以降低效率，因为MySQL优化器在选择如何优化SQL查询时，会对每一个索引进行评估，以生成一个最好的执行计划，如果同时有很多索引都可以使用，就会增加MySQL优化器生成执行计划的时间，同样会降低查询性能。所以一般建议单表索引不超过5个，根据实际频繁查询的字段设置索引。

唯一索引由于需要进行唯一性检查，不能利用change buffer进行更新优化。

1. 在InnoDB存储引擎中，change buffer是一种优化机制，它允许对不在内存中的数据页的更新操作先记录在change buffer中，而不是立即从磁盘读取数据页进行更新。这样做可以减少随机磁盘I/O操作，提高更新性能。
2. 对于普通索引，如果更新的数据页不在内存中，InnoDB可以将更新操作记录在change buffer中，然后在适当的时候（如查询访问该数据页时）再将这些操作应用到实际的数据页上，这个过程称为merge操作。但是，对于唯一索引，每次插入或更新操作都必须检查是否违反了唯一性约束。这种检查要求数据页必须首先被加载到内存中，以便进行唯一性判断。

没有任何一条优化规则是可以解决所有问题的（否则就被引擎内置了），你能做的是了解原理，根据实际业务场景做出更优的选择。