MySQL索引原理

1.Mysql概述

  • 介绍：Oracle旗下开源的最流行的关系型数据库（Relational Database Management System）管理系统。

  • 常见面试题：

    • SQL与Mysql区别：
      • SQL(Structured Query Language)是一种查询数据库的标准计算机语言，可以查询关系型数据库，包括但不限于Mysql。
      • Mysql是关系型数据库，支持SQL语言，但不支持全部的SQL（例如full outer join）
    • Mysql与Oracle使用场景区别：
      • 错误答案：大公司用Oracle，小公司用mysql
      • 正确答案：金融场景会使用Oracle
    • RDMS与NoSQL的主要区别：
      • 强一致性、弱一致性
      • 不可水平拓展、可水平拓展
    • NewSQL：可水平扩展的RDMS，代替“中间件+关系型数据库分库分表”，例如TiDB、OceanBase
    • DML、DDL、DCL：数据操作语言、数据定义语言、数据控制语言

  • 客户端与服务端通讯方式：

    • TCP/IP
    • 命名管道和共享内存【Windows】
    • Unix域套接字文件【Unix系】

MySQL逻辑层次图

MysqlServer层：连接管理、解析与优化

  • 查询缓存：5.7.20不推荐，8.0删除
    • 表的任何变动都会失效
    • 前后两次查询SQL完全一致
  • 语法解析
  • 查询优化：执行计划等（EXPLAIN）

存储引擎层：负责数据的存储和提取。

  • InnoDB：默认且最为常用
  • MyISAM
  • 其他存储引擎：Memory、Archive等

查询计划是MysqlServer层的职责，不跟随存储引擎而改变

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Mysql提供给存储引擎需要实现的接口实例（部分）：

//使用索引前调用该方法

int ha_foo::index_init(uint keynr, bool sorted) 

//使用索引后调用该方法

int ha_foo::index_end(uint keynr, bool sorted)

//读取索引第一条内容

int ha_index_first(uchar * buf);

//读取索引下一条内容

int ha_index_next(uchar * buf);

//读取索引前一条内容

int ha_index_prev(uchar * buf);

//读取索引最后一条内容

int ha_index_last(uchar * buf);

面试题

  • Innodb与Myisam引擎的区别

Myisam：支持表锁；不支持外键，事务；表的索引与数据在不同的文件；支持全文索引；允许没有主键

Innodb：支持行锁、表锁；支持外键，事务；表索引与数据在同一的文件；不支持全文索引（5.6+开始支持）；会有默认主键

  • 数据库的1NF、2NF、3NF：

1NF：关系中每一分量不可再分。即不能以集合、序列等作为属性。大白话：列不能存多个属性

2NF：在1NF基础上，消除非主属性对键的部分依赖。大白话：不同实体的表不要存在一张表里

3NF：在2NF基础上，消除非主属性对键的传递依赖。大白话：不要有重复字段

2.Mysql索引概述

  • What？

    • 帮助Mysql高效获取数据的数据结构。

  • Why？

    • 加快查询速度。（否则只能全表扫描）
    • 代价：额外的存储空间

  • How？

    • 增：CREATE <索引类型> INDEX <索引的名字> ON (列的列表)；
    • 删：DROP INDEX ON ;
    • 查：SHOW INDEX FROM ;
    • 强制指定索引：select <列名> from where <查询条件> force index(${index_name})

面试题1：当mysql执行计划选择错了索引，怎么办？

面试题2（非主流）：一个表最多可以可以新建多少个索引？16个？谈谈你对这个限制的理解

Mysql索引类别【重点】

  • 按照实现的数据结构区分：

    • B+树索引（InnoDB,MyISAM存储引擎）
    • Hash索引（Memory存储引擎等）
    • 倒排索引（ InnoDB,MyISAM存储引擎针对全文索引）
    • LSM-Tree索引：Hbase、OceanBase的索引数据结构

  • 按照约束（或者创建语句）区分：

    • 普通索引： CREATE INDEX
    • 唯一索引： CREATE UNIQUE INDEX
    • 主键索引： 创建表自带， { PRIMARY KEY (id) }
    • 全文索引： CREATE FULLTEXT INDEX【没人用，ES替代】

  • 按照索引列的数量区分：

    • 单列索引
    • 联合索引（复合索引、组合索引）【最左匹配原则】

  • 按照存储的内容区分(innodb存储引擎)

    • 聚簇索引：存储了索引列与数据【索引即数据，数据即索引】
    • 非聚簇索引（辅助索引/二级索引）：存储了索引列与主键

检查理解情况：（判断题）

  1. 主键索引是单列索引，也是聚餐索引。
  2. 使用CREATE INDEX语句创建的索引均为辅助索引。
  3. 聚餐索引存储了mysql表的所有的数据，支持按照主键查询。
  4. 使用Innodb存储引擎的表的主键索引是B+树索引。
  5. 使用Innodb存储引擎的表聚簇索引与非聚餐索引均采用B+树索引，存储原理是一致的。

注意：

只有B树，B+树

B-树 = B树，不要读B减树

  • 面试题1：Key（键/约束）与Index（索引）的区别与联系：

    • Index：方便查询
    • Key：方便查询 + 约束（主键、唯一键、外键）

  • 最左匹配原则:以最左边的为起点任何连续的索引都可匹配

  • 面试题2：

  • 索引：index(a, b, c )

  • 以下查询语句是否可以使用此索引：

  1. where a = 1：ok
  2. where a = 1 and c = 1：索引效果与上面一样
  3. where b = 1：不ok
  4. where a = 1 and b = 1 ：ok
  5. where b = 1 and a = 1：k【与条件先后顺序无关】
  • 面试题3：有哪些索引？

面试题

  • mysql innodb等值查询除了会使用到B+树索引，还可能使用到什么索引？
  • 谈谈哈希索引（自适应hash索引）
    • 哈希索引适合等值查询，但是无法进行范围查询
    • 哈希索引没办法利用索引完成排序
    • 哈希索引不支持多列联合索引的最左匹配规则
    • 如果有大量重复键值的情况下，哈希索引的效率会很低，因为存在哈希碰撞问题
    • 由innodb自行建立维护，DBA无法介入
  • 谈谈哈希索引与B+树索引的区别？

3.Innodb记录格式

行格式：

  • What 行？

    • 执行 insert into values(<值>) 语句便向数据库插入了一条数据，此条数据称之为行或者记录

  • What 行格式？

    • 存储上述行（或记录）在磁盘上的存放方式，即行格式/记录格式

  • How 行格式？

    • 指定：CREATE TABLE 表名 (列的信息) ROW_FORMAT=行格式名称
    • 修改：ALTER TABLE 表名 ROW_FORMAT=行格式名称

  • 行格式的类型有哪些？

    • Redundant：5.0-，冗余行格式，远古时期
    • Compact：5.6默认
    • Dynamic：5.7+默认，动态行格式，和Compact区别不大，仅在行溢出情况下存在区别
    • Compressed：压缩行格式，采用压缩算法节约磁盘空间，仅在数据归档时才会使用

Dynamic行格式【重点】

示意图

记录存储在“页”中，一页16KB

记录的额外信息：

  • 变长字段长度列表：变长字段（占用存储字节数不固定的字段，例如VARCHAR）的实际长度
  • NULL值列表：
    • 标示了哪些列：主键列、被NOT NULL修饰的列都是不可以存储NULL值，其他都存储
    • 如何标示：二进制位的值为1时，代表该列的值为NULL；二进制位的值为0时，代表该列的值不为NULL
    • 占用的字节数：必须用整数个字节的位表示（如果使用的二进制位个数不是整数个字节，则在字节的高位补0）
  • 记录头信息：占用5个字节（40位）
    • delete_mask：该记录是否被删除
    • next_record：下一条记录的相对位置（并不是插入顺序的下一条记录，而是按照主键值/索引列值的下一条记录）
    • record_type：记录类型， 0表示普通记录，1表示B+树非叶子节点记录，2表示最小记录，3表示最大记录
    • heap_no：当前记录所属的页号
    • 其他（预留位1、预留位2、 min_rec_mask、 n_owned）

记录的真实数据：

  • 隐藏列：
    • row_id：行ID，非必须，无主键且无NOT NULL的UK时才会有
    • transaction_id：事务ID
    • roll_pointer：回滚指针
  • 数据列：存储真实的数据

示意图2

其他概念-行溢出：当记录中的数据太多，当前页放不下的时候，会把多余的数据存储到其他页中的现象

面试题1：delete语句之后，空间会不会自动释放？

答：不会，会将此记录标记为己删除，页内已删除的记录做为一个垃圾链表，下次需要向此页插入数据时，优先使用此块空间。

面试题2：表创建时无主键，会怎么办？

答：

  1. 首先选择第一个被NOT NULL修饰的UK索引做为聚簇索引
  2. 若无，则会在记录中添加隐藏列的row_id

面试题3：为什么查询数据时不建议select *

  1. 网络IO 2. 发生回表现象 3. 回表时命中溢出页

4.Innodb页格式

索引页/数据页

页： InnoDB管理存储空间的基本单位，也是MySQL中磁盘和内存交互的基本单位，一个页的大小一般是16KB

数据页/索引页格式示意图

  • 文件头：File Header，页的一些通用信息

    • 页号
    • 校验和：与页尾一起校验页是否完整，刷盘时首先写校验和，通过和文件尾的校验和一同判断是否存在同步一半的情况。
    • 上一个页的页号、下一个页的页号：组成B+树的双向链表

  • 页头：Page Header，数据页专有的一些信息

    • 本页中的记录的数量（包括最小和最大记录以及标记为删除的记录）
    • 第一个已经标记为删除的记录地址【为了找到垃圾链表，插入数据】
    • 还未使用的空间最小地址【为了插入数据】
    • 页类型等其他

  • 虚记录：最小虚记录和最大虚记录

    • 最小虚记录：此记录的next_record指向本页中最小的记录
    • 最大虚记录：指向本页中最大的记录的next_record指向此记录

  • 用户记录*/*记录堆：实际存储的记录内容，由一堆行记录组成

    • 既有有效记录，又有已删除的记录

  • 未分配空间：页中尚未使用的空间

    • 下次需要向此页插入数据时，若无垃圾链表，则会使用此块空间。

  • 页目录/Slot**区：页中的某些记录的相对位置，为了快速查询

  • 文件尾：与页头一起校验页是否完整

示意图3

记录的页内插入

  • 插入位置：

    • 垃圾链表（页头记录了第一个已经标记为删除的记录地址）
    • 未分配的空间（页头记录了还未使用的空间最小地址）

  • 插入策略：物理有序 vs 逻辑有序

    • 举例：依次插入顺序10、9、8

    物理有序：

物理有序

逻辑有序：

逻辑有序

记录的页分裂【重点】

  • 该页装不下怎么办？假设页10只能装下3条记录，现在要插入id=4的记录

image-20230624094252434

思考：为什么mysql主键不建议使用UUID

  • 在对页中的记录进行增删改操作的过程中，我们必须通过一些诸如记录移动的操作来始终保证这个状态一直成立：下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。这个过程我们也可以称为页分裂。

记录的页内查找（了解）

image-20230624094451483

问：此时查找id=3的数据的时间复杂度是多少？

记录的页内二分查找（了解）

  • Slot区：也称Page Directory区，页目录区，记录页中的某些记录的相对位置。
  • Slot：槽，对于页内记录（含最大记录与最小记录，不包括标记为已删除的记录）进行分组，每个组的最后一条记录的地址偏移量即为槽。
    • 每个组的最后一条记录（也就是组内最大的那条记录）的头信息中的n_owned属性表示该记录拥有多少条记录

  • 分组依据：

    • 对于最小记录所在的分组只能有 1 条记录
    • 最大记录所在的分组拥有的记录条数只能在 1~8 条之间
    • 剩下的分组中记录的条数范围只能在是 4~8 条之间

  • 如何二分查找：O(Log2N)

    • 通过二分法确定该记录所在的槽，并找到该槽所在分组中主键值最小的那条记录二分过程：(high槽 + low槽) / 2 得到当前槽，判断当前槽所指记录的大小，决定high/low的变化查找主键值最小的那条记录：(high – 1)槽所指的记录的next_record

    • 通过记录的next_record属性遍历该槽所在的组中的各个记录

5.再看B+树索引【重点】

B+树聚簇索引

    1. 页之间存在双向链表（通过页的文件头区域的“上一页的页号”与“下一页”页号）

    image-20230624095018218

此时查找办法：从左到右遍历页，看当前记录是否在最小记录与最大记录之间，若不在则判断下一页，若在则在页内二分查找。

    1. 给每个页建立个目录，记录“页的用户记录中最小的主键值”与页号

    image-20230624095038737

此时的查找方法：在目录页二分查找（距离此记录最近的所在的页），再在目标页内，二分查找。

    1. “目录”太多，一页装不下，分多个页来装。

此时的查找方法：先从根页查找“距离此记录最近的记录”所在的页，再到索引页“距离此记录最近的记录”，最后到叶子节点二分查找

  • 根节点：存放索引信息（或者称为目录项）的页
  • 非叶子节点（内节点）：存放索引信息的页
    • 下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。
  • 叶子节点（外节点）：存放索引信息与实际数据的页
    • 下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。

Innodb的聚簇索引与非聚簇索引均采用此结构进行存储，区别在于：

  1. 聚簇索引的叶子节点存储的是全量数据
  2. 非聚簇索引的叶子节点存储的是索引列的值 + 主键

下一个数据页中用户记录的索引列值必须大于上一个页中用户记录的索引列值。

=>

非聚簇索引的存储的索引数据一定会有主键。

**如上图某非聚簇索引橙色为索引的key绿色为页号蓝色为主键 **

此时若插入索引key=1的数据改插入到页4还是页5？

面试题：

表：user（id，name、sex）

查询条件： where name = ？ and sex =? order by id

为了高效查询，建立索引有4种方式，以下哪种最优？

  1. idx_name_sex_id（name、sex、id）
  2. idx_sex_ name_ id （sex、name、id）
  3. idx_sex_name（sex、name）
  4. idx_name_sex （name、 sex）

6.索引的使用

访问类型概述

访问类型：也称访问方法，access method，MySQL执行查询语句的方式。

  • 使用全表扫描进行查询（all）
  • 使用索引进行查询（const、ref、ref_or_null、range、index等）

注意：数据量大的表，一定要避免all的发生

访问类型-const

  • const：
    • 直接利用主键值在聚簇索引中定位对应的一条记录
    • 根据唯一辅助索引列来定位一条记录

访问类型-ref【重点】

  • ref：对某个普通的二级索引列与常数进行等值比较

  • 回表：通过辅助索引查询到的数据，不包含用户查询的全量数据，需要用主键去聚簇索引中再次查询的过程。（随机IO）

  • 索引覆盖：只需要在一棵索引树上就能获取SQL所需的所有列数据，无需回表。

面试题：

  1. 为什么不select *？
  2. 什么是索引覆盖？
  3. 为什么要尽量避免回表？

访问类型-ref_or_null

访问类型-range

  • range：区间查询，使用=、<=>、IN、NOT IN、IS NULL、IS NOT NULL、>、<、>=、<=、BETWEEN、!=、 <>、like左匹配，就可以产生一个所谓的区间。

举例：SELECT * FROM single_table WHERE key2 IN (1438, 6328) OR (key2 >= 38 AND key2 <= 79);

image-20230624095852531

访问类型-index

  • index：查询的值以及返回的结果恰好在某个辅助索引里，但是无法通过索引列查询，全部扫描此索引。

举例：

表：

CREATE TABLE single_table (

​ id INT NOT NULL AUTO_INCREMENT,

​ key1 VARCHAR(100),

​ key2 INT,

​ key3 VARCHAR(100),

​ key_part1 VARCHAR(100),

​ key_part2 VARCHAR(100),

​ key_part3 VARCHAR(100),

​ common_field VARCHAR(100),

​ PRIMARY KEY (id),

​ KEY idx_key_part(key_part1, key_part2, key_part3)

) Engine=InnoDB CHARSET=utf8;

查询语句：SELECT key_part1, key_part2, key_part3 FROM single_table WHERE key_part2 = ‘abc’;

辅助索引的数据比聚簇索引的数据小，全表所描辅助索引，也是个不错的选择

索引的注意事项

  1. ORDER BY子句里使用到了我们的索引列（但是 oder by a asc, b desc, c desc不行）
  2. 只为用于搜索、排序或分组的列创建索引
  3. 列的区分度大的列创建索引，重复数据多的字段不应设为索引
  4. 更新频繁的列不应设置索引
  5. 重复数据多的字段不应设为索引的例外情况（状态字段=有效/无效，仅根据“有效”查询时，可以建立）
  6. 联合索引，区分度大的列放在第一位
  7. 只有索引列在比较表达式中单独出现才可以适用索引 （ a > 2 可以，a + 1 > 1不行）
  8. 为了尽可能少的让聚簇索引发生页面分裂和记录移位的情况，建议让主键拥有AUTO_INCREMENT属性。
  9. 尽量使用覆盖索引进行查询，避免回表带来的性能损耗。
  10. 使用IN查询，IN的数量不能太大（<=2000），避免mysql走错索引
  11. Mysql会根据I/O成本以及CPU成本去估算，选择最终执行计划
  12. LIKE 右模糊（like kw%）可以使用到索引，LIKE左模糊（like %kw） 、全模糊（like %kw%）无法使用到索引。

神兵利器：

  • EXPLAIN：查看SQL的执行计划的结果。
  • optimizer trace：查看生成执行计划的整个过程。

面试题：

  1. 如何判断SQL走的是哪个索引？
  2. 如何优化慢SQL？
  3. 建立索引有哪些注意事项？

7.其他应该知道的知识点

innodb区/段/表空间

  • 区：连续的64个页就是一个区。

    • 设计的目的：一个区就是在物理位置上连续的64个页，物理连续，空间的局部性原理，发生连续IO几率更高。（利用磁盘预读原理）

  • 段：存储相同类型记录的区做为一个段，一个段会有256个区，一个表空间下会有多个段，如“叶子节点段”、“非叶子节点段”。

    • 设计的目的：范围查询，其实是对B+树叶子节点中的记录进行顺序扫描，而如果不区分叶子节点和非叶子节点，统统把节点代表的页面放到申请到的区中的话，进行范围扫描的效果就大打折扣。物理连续，空间的局部性原理，发生连续IO几率更高。

  • 表空间：为了更好的管理页，一个.idb结尾的表为一个独立表空间。

为什么使用B+树，不用B树/二叉树？

  1. 二叉树的高度太高，每次查找都是一次磁盘IO，很慢；B+树是一个多路查找树，高度一般2-4层，矮胖，IO较少。
  2. B+树仅在叶子节点存储数据，叶子节点之间有双向链表，范围扫描快，B树没有，B树的非叶子节点也存储数据。

索引下推（ICP）

  • 索引下推：5.6+，有效减少回表次数，从而提高效率。

  • 例子：

    • 语句：select * from table where k1 = a and k2 = b，索引为idx_k12(k1, k2)
    • 执行：innodb扫描到一条记录：k1 = a , k2 = c
      • 不使用ICP：innodb将此记录返回给mysql-server， mysql-server拿着主键去回表判断 k2 是否等于 b
      • 使用ICP：innodb自行判断，无需mysql-server回表判断

  • 区别：

    • 当你不使用ICP,通过使用非主键索引（普通索引or二级索引）进行查询，存储引擎通过索引检索数据，然后返回给MySQL服务器，服务器再判断是否符合条件。
    • 使用ICP，当存在索引的列做为判断条件时，MySQL服务器将这一部分判断条件传递给存储引擎，然后存储引擎通过判断索引是否符合MySQL服务器传递的条件，只有当索引符合条件时才会将数据检索出来返回给MySQL服务器。

进阶面试题：5.6之前为什么不下推？

所谓下推，不过是将MysqlServer做的事情下移至存储引擎来做，其实是一个很正常的操作，只不过Mysql在之前的版本，并没有把这部分判断条件传递给存储引擎，过于简单粗暴。

深翻页

  • 现象：select * from table_name limit m,n; 当m很大时，查询性能急剧下降。
  • 第一层原理：先读取符合where条件的前面m+n条记录，然后抛弃前m条，返回后面n条，所以m越大，偏移量越大，性能就越差。
  • 第二层原理：mysql server与存储引擎的交互，首先根据索引定位到第一条，往后一条条数据往后扫描，每条数据mysql server再判断是否要用，丢弃掉了前面m条数据。
  • 解决方案：
    • 优化前：select * from table_a limit 1000000, 10;
    • 优化后：select * from table_a where id > ${lastKey} limit 10;
  • 解决方案的局限性：
    • 1、没有总页数
    • 2、只能上下翻页
    • 3、id必须有序且唯一

面试题-情景题

  • 生产环境Mysql数据库所在服务器CPU飙升，如何排查？

  • 经验：mysql服务器的CPU飙升往往都是慢SQL导致的

  • 问题转换 => 如何找到慢SQL？

  • 方法1：查看数据库的慢SQL日志 slow.log

  • 方法2：查看CPU飙升的曲线，是从时候开始的，那段时间做了什么样的代码变更，查看查询的表与条件。

面试题-Mysql单表最多能存储多少数据？

  • 业内经验：
    • 阿里巴巴《Java开发手册》：单表行数超过 500 万行或者单表容量超过 2GB，才推荐进行分库分表。
    • 互联网圈流传：MySQL 单表数据量大于 2000 W行，性能会明显下降。
  • Mysql单表最多能存储多少数据？
    • 理论上可存储多少：取决于主键的数据类型，int为2^32 - 1，bigint为2^64 - 1
    • 实际上可存储多少：超过了多少将影响Mysql的性能
  • 分析：

Mysql单表最多能存储多少数据？ => Mysql单表数据量超过多少将较大的影响mysql的性能？

影响Mysql性能的主要原因是什么？=> 索引结构，B+树索引 => B+树的什么属性影响了性能 => 高度（一般2-3层，2-3次IO）

  • 如何理解业内经验？DBA基于大多数场景的经验

其他基础知识

  • 表的字符集要使用，utf8mb4
  • 表的比较规则要大小写敏感（默认不敏感），以_cs结尾的比较规则
  • union与union all的区别
  • char与varhcar的区别
  • 左连接，右连接，内连接的区别
  • Mysql时间/日期的数据类型：https://blog.51cto.com/u_15346415/3675766
  • 基础的SQL语句书写
Java知识体系 > 中间件 > Mysql
#MySQL
MySQL索引原理
http://example.com/2023/06/24/MySQL索引原理/
作者
子川
发布于
2023年6月24日
许可协议