MySQL 索引

date

Aug 5, 2021

slug

mysql-innodb-basic-concept-index

status

Published

存储的硬件结构

软件是跑在硬件上的，很多软件之所以形成现在的体系结构往往跟硬件结构有很大关系。

先看看普通磁盘的示意图：

磁盘是由盘片 platter 构成的。每个盘片有两面或者成为表面 surface，表面覆盖着磁性记录材料。盘片中央有一个可以旋转的主轴 spindle，使得盘片以固定的旋转速率 rotational rate 旋转，通常是 5400 ~ 15000 转每分钟 Revolution Per Minute RPM。磁盘通常包含一个或多个这样的盘片，并封装在一个密封的容器内。（CSAPP 第六章有介绍）

磁道和扇区

每个表面 surface 有一组磁道 track 的同心圆组成。每个磁道被分为多个扇区 sector，扇区之间由一些间隙 gap 分隔开。读取数据时需要确认数据所在的物理地址，即哪个磁道，哪个扇区，之后磁头移动到相应的磁道，即寻道时间。之后磁盘旋转使磁头可以读取到磁道上的扇区，即旋转时间。最后还要从目标扇区第一位开始读/写，直到最后一位读/写完成，即传送时间。以上操作是机械的，非常耗时，所以需要减少磁盘的 IO 操作。

Linux 查看扇区大小：

其中 Sector size 就是扇区大小，一般为 512 byte。扇区是物理层面的概念，一般无法对其大小改变。由于每个扇区太小，数量太多，操作系统直接操作扇区效率不高，所以操作系统逻辑上不直接与扇区交互，而是与块交互。

磁盘块 IO Block

块是文件系统读写数据的最小单位，操作系统将相邻的多个扇区组合在一起形成一个磁盘块 Block。

Linux 查看块的大小：

其中表示每个块大小 4096 byte，即 4KB，由 8 个扇区组成。

由于块是操作系统读写文件的最小单位，所以文件的大小都是块的整数倍，如果实际文件大小不足一个块大小，也会占用一个块大小空间，如图，文件实际大小 111 bytes，但占用了磁盘上 4KB 空间：

内存中的页 Page

页 page 是内存中最小的存储单位，页大小通常是磁盘块大小的 2^n 倍，但一般与磁盘块大小一致。可通过 getconf PAGE_SIZE 命令获取页大小：

局部性原理

局部性原理分为时间局部性和空间局部性。

时间局部性是指如果程序中的某条指令一旦执行，则不久之后该指令可能再次被执行；如果某数据被访问，则不久之后该数据可能再次被访问。

空间局部性是指一旦程序访问了某个存储单元，则不久之后。其附近的存储单元也将被访问。

磁盘预读

磁盘预读即在读取数据时，一次性读取连续多个页的数据。比如 MySQL 一次 IO 读取会读 4 个页的数据，即 4 x 4KB = 16KB。

索引类型

索引是一种数据结构，用于快速查找和排序。

MySQL 支持的索引数据结构有 FullText、Hash、B-tree、R-tree 等等。其中 B+Tree 最为常用。

B Tree 和 B+Tree

B Tree 在每个节点上存储索引值和具体数据，可以有效减少读取数据的时的 IO 次数，但没有数据之间的关联关系，导致查询某一范围内的数据时，只能反复的从根节点向下查找，导致 IO 次数增多。

B+Tree 在非叶子节点中不存储数据，数据都存储在叶子节点上，且叶子节点之间带有关联关系，这使得节点中可以存储更多的索引区间，保证树的高度处在较矮的状态下，降低 IO 次数。

`explain` 查询计划各列说明：

id 列：

表示查询中执行 select 子句或操作表的顺序

id 相同，执行顺序由上到下

id 不同，如果是子查询 id 序号会递增，id 值越大越先被执行。一般先执行括号里的子查询

id 有相同有不同，先执行序号大的，序号相同的再按顺序执行

select_type 列：

SIMPLE：简单 select 查询

PRIMARY：查询中最外层的查询，最后被执行，一般出现在有子查询的句子

SUBQUERY：在 select 或 where 中包含的子查询

DERIVED：包含子查询的查询被标记为 DERIVED 衍生之意，需要先执行子查询后才能执行的句子。derived4 表示衍生自第 4 个子句执行之后。

UNION：在 union 之后的子句被标记成 UNION

UNION RESULT：从 UNION 表获取结果的那条 select 句子

type 列：

type 列的值依照查询效率从高到低依次为：

system：系统表，少量数据，往往不需要进行磁盘IO

const：在主键上查询，且仅有一条匹配

eq_ref：通过主键连接查询，且连接条件只有一条结果匹配

ref：在非主键索引上查询，值可能有多个

range：在索引上范围扫描

indxe：在索引上全部扫描

ALL：全表扫描

possible_keys、key、key_len、rows、ref 列：

possible_keys 可能用到的索引

key 实际用到的索引

key_len 索引中使用的字节数，相同查询结果下，长度越短越好

rows 有多少列匹配

ref 与 key 列中用到的索引去做比较的那些列

Extra 列：

Using filesort 无法用索引完成排序，需要利用文件排序，性能较差，一般出现在排序字段无法利用索引时。

Using temporary 使用临时表保存中间结果，性能更差。一般出现在 group by 查询时。

Using index 执行了覆盖索引，无需再次查询数据文件，直接从索引中返回。

Using where 使用了 where 条件。

查询优化技巧

外连接查询时，索引加在副表上

例如左外连接需要左表全部数据加上右表匹配的数据，所以左表肯定是要扫全表的，索引加在右表能够好地发挥作用。右外连接也相同。

小表驱动大表

大量数据范围查询优化

通过覆盖索引找到二级索引确定目标数据的大致范围，再通过主键去查找具体数据。

参考：

What are the differences between B trees and B+ trees?：https://stackoverflow.com/questions/870218/what-are-the-differences-between-b-trees-and-b-trees

计算机存储术语: 扇区，磁盘块，页：https://zhuanlan.zhihu.com/p/117375905

性能优化之分页查询：https://www.infoq.cn/article/ptwslcp4lvkjoe7kxlii

从局部性原理与磁盘预读原理来了解索引机制：https://blog.csdn.net/xd_1437/article/details/103253632

马士兵 MySQL 索引机制：https://www.bilibili.com/video/BV1K64y1F76m