MySQL第二讲：MySQL innoDB存储引擎中索引原理

1、索引的常见模型

1.1、索引作用

• 提高数据查询的效率

1.2、Mysql存储引擎中索引的实现机制(底层）

1.2.1、什么是索引？

• 索引是对数据库表中一个或多个列的值进行排序的数据结构，以协助快速查询、更新数据库表中数据。往往以索引文件的形式存储在磁盘上(索引加速了数据访问，因为存储引擎不会再去扫描整张表得到需要的数据)
• 通常的索引指的是B数结构组织的索引（多路搜索树）包括聚集索引，次要索引，复合索引，前缀索引，唯一索引默认使用B+数索引

1.2.2、索引的优缺点和使用场景

• 优点：查找排序快、主键索引保证唯一(O(logn) 的时间复杂度)
• 缺点：存储空间、维护时间

使用场景：

• 查询多、更新少、空值少的数据；

1.2.3、索引种类有哪些，怎么分类

普通索引和唯一性索引：索引列的值的唯一性

• 唯一索引：可以保证行数据的唯一性，不允许其中任何两行具有相同索引值的索引（允许空）

create unique index indexName ON mytable(cliumnname(length));  
drop index indexname ON mytable;

• 单个索引和复合索引：索引列所包含的列数
  
• 单值索引：即一个索引只包含单个列，一个表可以有多个单列索引
  
• 复合索引：即一个索引包含多个列
  
• 聚簇索引与非聚簇索引：聚簇索引按照数据的物理存储进行划分的
  
• 聚集索引(主键索引)：提供更快的数据访问速度(堆划分)，表中行的物理顺序与键值索引顺序相同。一个表只能包含一个聚集索引
  
• 非聚集索引(非主键索引):是把一个很大的范围，转换成一个小的地图，然后你需要在这个小地图中找你要寻找的信息的位置，最后通过这个位置，再去找你所需要的记录
  
• 覆盖索引定义：如果查询条件使用的是普通索引（或是联合索引的最左原则字段），查询结果是联合索引的字段或是主键，不用回表操作，直接返回结果，减少IO磁盘读写读取正行数据
  
• 最左前缀：联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符
  
• 索引下推：like 'hello%’and age >10检索，MySQL5.6版本之前，会对匹配的数据进行回表查询。5.6版本后，会先过滤掉age<10的数据，再进行回表查询，减少回表率，提升检索速度

• 什么是回表查询，见第1.10节

1.2.4、主键、自增主键、主键索引与唯一索引概念区别(按数据的逻辑进行划分)

• 主键：指字段唯一、不为空值的列(主键是一种特殊的唯一性索引，其可以是聚集索引，也可以是非聚集索引) 对于没有主键的表，innodb会默认创建一个Rowid做主键
• 主键索引：要求主键值唯一，创建主键的时候，数据库默认会为主键创建一个唯一索引(叶子节点存的是整行数据)
• 非主键索引：叶子节点内容是主键的值（二级索引）
• 自增主键：字段类型为数字、自增、并且是主键；
• 唯一索引：索引列的值必须唯一，但允许有空值。主键是唯一索引，这样说没错；但反过来说，唯一索引也是主键就错误了，因为唯一索引允许空值，主键不允许有空值，所以不能说唯一索引也是主键

1.2.5、基于主键索引和普通索引的查询有什么区别？

• 如果语句是select * from T where ID=500，即主键查询方式，则只需要搜索ID这棵B+树；
• 如果语句是select * from T where k=5，即普通索引查询方式，则需要先搜索k索引树，得到ID的值为500，再到ID索引树搜索一次。这个过程称为回表。也就是说，基于非主键索引的查询需要多扫描一棵索引树。

1.2.6、 重建普通索引k和重建主键索引id，对于两个重建索引的做法，说出你的理解？

• 如果删除，新建主键索引，会同时去修改普通索引对应的主键索引，性能消耗比较大。删除重建普通索引貌似影响不大，不过要注意在业务低谷期操作，避免影响业务。可以使用sql语句alter table T engine = InnoDB 替代重建过程。

1.2.7、“N叉树”的N值在MySQL中是可以被人工调整的么？

• 可以按照调整key的大小的思路来说：如果你能指出来5.6以后可以通过page大小来间接控制应该能加分吧，面试回答不能太精减计算方法、前缀索引什么的一起上。

1.3、Mysql索引的实现机制有四种：（哈希表/有序数组/B树/B+树/全文索引）

1、hash索引：给表的某一列计算hash值，排序在hash数组上，hash索引可以一次定位，效率高（等值比较，适用于redis/memcached）

• 缺点：因为递增主键的存储位置不是连续的，所以哈希索引做区间查询的速度很慢。

2、有序数组索引：往中间插入一个记录就必须得挪动后面所有的记录，成本太高，只适用于静态存储引擎（通常不怎么变更的数据）

3、btree索引：是以B+树为存储结构实现的，B+树是为磁盘或其他存储设备设计的一种平衡的多叉树，从根节点到每个叶子结点的高度差值不超过1，而且同层级的节点间有指针相互连接。基于索引的顺序扫描时，可以利用双向指针快速左右移动，效率非常高，用于数据库，文件系统中。

• 最为常用和最为有效
• B代表的是平衡(balance)
• 采用二分查找法查询数据

hash和btree区别：

• 1、hash索引比较的是经过hash计算的值，所以只能进行等值比较，不能用于范围查询；
• 2、hash值映射的真正数据在hash表中就不一定按照顺序排序，所以无法利用hash索引来加速任何排序操作。以及like “xx%”这样的部分模糊查询；
• 3、hash索引也不支持多列联合索引

• 无论是二叉搜索树还是AVL树，当数据量比较大时，都会由于树的深度过大而造成I/O读写过于频繁，进而导致查询效率低下，因此对于索引而言，多叉树结构成为不二选择。随着数据库技术的发展，跳表、LSM树等数据结构也被用于引擎设计中(数据库底层存储的核心就是基于这些数据模型)

Action1：InnoDB存储引擎支持的哈希索引是自适应的，InnoDB存储引擎会根据表的使用情况自动为表生成哈希索引，不能人为干预。

1.3.1、B+ 树详解

1、B树和B+树特点

B树：多路平衡查找树(结点的最大值m称为B_TREE的阶,简称为m叉树)

• 特点：平衡（叶子节点位于同一层上，到达任意叶子节点的搜索代价相同）、层少、升序，树中每个结点最多有m个孩子结点/若根结点不是叶子节点，则根结点至少有2个孩子结点/除根结点外，其它结点至少有(m/2的上界)个孩子结点
• 结构：父节点、子节点指针数组、key信息数组（查找值或折半）

• n c0 d1 c1 d2 c2 … dn cn 有序//n为结点中关键字个数/di(1<=i<=n)为该结点的n个关键字值的第i个/ci(0<=i<=n)为该结点孩子结点的指针
• 所有的叶结点都在同一层上，并且不带信息(说明节点不存在)

• 优点：由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近(文件系统和数据库)

B+树（innoDB存储引擎使用的索引结构）

• B+树是b树的变种，主要区别在于：B+树的非叶子节点只存储 key + 指向下一层节点的指针。另外，B+树的叶子节点之间通过指针来连接，构成一个有序链表，因此对整棵树的遍历只需要一次线性遍历叶子结点即可。

• 结构区别：

• 非叶节点仅含有其子树根结点中最大(或最小)关键码、叶子节点保存key数组、有序链表(依关键码的大小自小而大的顺序链接)
• 所有数据地址必须要到叶子节点才能获取到，所以每次数据查询的次数都一样(除了非终端结点上的关键码等于给定值这种情况)
• 通常在B+树上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点。
• 因此可以对B+树进行两种查找运算：一种是从最小关键字起顺序查找，另一种是从根节点开始，进行随机查找

• 性能区别：

• IO少、平衡、范围查找，每一个关键字的查询效率相当
• B+与普通二叉树比较 IO少：
• 层数少、层间局部性原理、顺序读写

• B+ 树的高度一般都在 2 ~ 4 层，这就是说查询某一键值的行记录时，最多只需要 2到4次 IO，一般机械硬盘每秒至少可以做 100次IO，2 ~ 4次的 IO 意味着查询时间只需 0.02S ~0.04S。

• 缺点：（索引维护）

• 会产生大量的随机IO,随着新数据的插入，按照B+Tree算法，新增加一个数据页，叶子节点会慢慢分裂，逻辑上连续的叶子节点在物理上往往不连续。

• 解决方案：

• 1、LSM树 HBase使用LSM树(Log-Structured Merge Tree),同样支持增删读改、顺序扫描操作，而且通过批量存储技术规避磁盘随机写入的问题，LSM树牺牲了部分读性能，用来大幅提高写性能。

• LSM设计思想：将对数据的修改增量保持在内存中，达到指定大小限制后将这些修改操作批量写入磁盘。把一棵大树拆分成N棵小树，首先写入内存中，随着小树越来越大，内存中的小树会flush到磁盘中，磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能。

• 2、使用自增主键(从性能和存储空间方面考量)

• 每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂；有业务逻辑的字段做主键，则往往不容易保证有序插入，这样写数据成本相对较高

2、B+树中插入/删除操作

B+树中的插入必须保证插入后叶子节点中的记录依然有序，同时需要考虑插入到B+树的三种情况，每种情况都可能会导致不同的插入算法，入下表所示：

背景: B+ 树，高度为2，每页可存放4条记录，扇出为5

场景1：插入节点 28

• 直接插入即可
  

场景2：继续插入节点70

• 原来的 Leaf page 已经满了，但是 Index Page 还没有满，符合第二种情况，这时插入 Leaf page 后的情况为 50，55，60，65，70，并根据中间的值60来拆分叶子节点，如下图
• 

场景3：最后插入节点95

• 符合上表的第三种情况，即Leaf Flag和 Index Page都满了，这时需要做两次拆分
• 

场景4 旋转操作

• 发生在 leaf Flag 已经满，但是其左右兄弟节点没有满的情况下，这时B+树并不会急于去做拆分页操作，而是将记录移到所在页的兄弟节点上。
• 例如：在场景2的基础上，如果插入键值70，这时会执行旋转操作
• 

B+树中删除操作

• 使用填充因子(fill factor) 来控制树的删除变化，50%是填充因子可设的最小值。B+树的删除操作同样保证删除后的叶子节点记录保持有序。B+树删除后的场景如下所示

场景1：删除键值为70的记录

• 直接删除节点
  

场景2：接着删除键值为25的记录

• 删除Leaf Page 中的25后，还应将25的右兄弟节点的28更新到 Index Page中，如下图
  

场景3：删除键值为 60的情况

• Fill Factor 小于 50%，这时需要做合并操作，并且需要做 Index Page 的合并操作，如下图
  

3、B+树索引的管理

# 1、创建索引
alter table t add key idx_b (b(100));
# 2、创建联合索引
alter table t add key idx_a_c (a, c);

查看索引详情

show index from t;
**********************************
table: t    // 索引所在的表名
non_unique: 1  //非唯一的索引
key_name: idx_c //索引的名字
seq_in_index:1       //索引中该列的位置
column_name:c
collation:a
cardinality:2    //表示索引中唯一值的数目估计值，优化器根据这个值巨鼎是否使用该索引
sub_part:null
packed:null
null:
index_type:btree
comment:

注意事项：对应用程序的几张核心表做 analyze table操作，这能使优化器和索引更好地为你工作。

4、cardinality详解

• 对于什么时候添加B+ 树索引，一般的经验是：在访问表中很少一部分数据时，使用 B+树索引才有意义。对于性别字段、地区字段、类型字段，它们的可取值范围很小，称为低选择性。
• 相反，如果某个字段的取值范围很广，几乎没有重复，即属于高选择性。例如姓名

如何查看索引是否有高选择性呢？

• 可以通过 show index 结果中的列 cardinality来观察，其表示索引中不重复记录数量的预估值。

InnoDB中cardinality的统计？

• 在insert or update时采样，策略为：表中1/16的数据已发生过变化；stat_modified_counter >2000 000 000。

1.3.2、全文检索详解

背景：用户需要查询博客内容包含单词 xxx 的文章，sql如下

- 即使是加了索引，也需要对全文进行扫描，性能极低。

select * from blog where content like '%xxx%';

全文索引（也称全文检索）是目前搜索引擎使用的一种关键技术。它能够利用【分词技术】等多种算法智能分析出文本文字中关键词的频率和重要性，然后按照一定的算法规则智能地筛选出我们想要的搜索结果。

• innodb引擎从 1.2.x版本开始支持全文索引，对应MySQL版本为5.6
  
• 全文索引的创建

• 例如：我们有一个文章表（article），其中有主键ID（id）、文章标题（title）、文章内容（content）三个字段。现在我们希望能够在title和content两个列上创建全文索引，article表及全文索引的创建SQL语句如下：

CREATE TABLE `article` (
    `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
    `title` varchar(200) DEFAULT NULL,
    `content` text,
    PRIMARY KEY (`id`),
    FULLTEXT KEY `title` (`title`,`content`)
) ENGINE = MyISAM DEFAULT CHARSET = utf8;
# 给已经存在的表的指定字段创建全文索引
ALTER TABLE article 
    ADD FULLTEXT INDEX fulltext_article(title,content);

• 全文检索的查询

• 想要在 article 表的 title 和 content 列中全文检索指定的查询字符串，我们可以如下编写SQL语句

# 查询单列数据
 SELECT * FROM `student` WHERE MATCH(`name`) AGAINST('聪');
 # 等价于
 SELECT * FROM `student` WHERE MATCH(`name`) AGAINST('聪' in language mode);
 # 查询多列数据
 SELECT * FROM article WHERE MATCH(title,content) AGAINST (‘查询字符串’);

• in natural language mode 默认模式

• 观察执行计划，可得

id: 1
select_type: simple
table:fts_a
type:fulltext
possible_keys:idx_fts
key:idx_fts
key_len:0
ref:null
rows:1
extra:using where

• in boolean mode

• 当使用该修饰符时，查询字符串的前后字符会有特殊的含义，Boolean全文检索支持以下几种操作符

• 1、+ 表示该word必须存在
• 2、- 表示该word必须被排除
• 3、(no operator) 表示该word是可选的，但是如果出现，其相关度会更高
• 4、@distince 表示查询的多个单词之间的距离是否在distince之内， 如 MATCH(body) AGAINST (‘“Pease pot”@30’ in boolean mode) 表示字符串Pease和pot之间的距离需在30字节内
• 5、> 表示出现该单词时增加相关性
• 6、< 表示出现该单词时降低相关性
• 7、~ 表示允许出现该单词，但是出现时相关性为负
• 8、* 表示以该单词开头的单词，如 lik *，表示可以是 lik、like 或likes
• 9、" 表示短语

• demo如下所示

# A 且 B
select * from fts_a where match(body) against('+Pease +hot' in boolean mode)
# 有A无B
select * from fts_a where match(body) against('+Pease -hot' in boolean mode)
# A或B
select * from fts_a where match(body) against('Pease hot' in boolean mode)
# 模糊查询
select * from fts_a where match(body) against('po*' in boolean mode)
# 短语sql查询
select * from fts_a where match(body) against('"like hot"' in boolean mode)

• query expansion 隐式查询

• 会带来许多非相关性的查询，因此在使用时，用户可能需要非常谨慎

select * from fts_a where match(title, body) against('database' with query expansion)

• 强烈注意：

• MySQL是从5.6版本开始支持了Innodb的全文索引
• MySql自带的全文索引只能对英文进行全文检索，目前无法对中文进行全文检索。如果需要对包含中文在内的文本数据进行全文检索，我们需要采用Sphinx（斯芬克斯）/Coreseek技术来处理中文
• 目前，使用MySql自带的全文索引时，如果查询字符串的长度过短将无法得到期望的搜索结果。MySql全文索引所能找到的词默认最小长度为4个字符。另外，如果查询的字符串包含停止词，那么该停止词将会被忽略
• 一张表只能创建一个 FULLTEXT 索引
• 由多列组合而成的全文索引的索引列必须使用相同的字符集和排序规则

• 如果可能，请尽量先创建表并插入所有数据后再创建全文索引，而不要在创建表时就直接创建全文索引，因为前者比后者的全文索引效率要高。

• 如何解决：推荐使用ES，专业的全文检索引擎

• 删除全文索引

• 1、直接使用 drop index

DROP INDEX full_idx_name ON tommy.girl;

• 2、使用 alter table的方式

ALTER TABLE tommy.girl DROP INDEX ft_email_abcd;

• 在项目中的使用：场景1：查询品牌表适用类目
  
• 数据如下
  
  
• 查询语句如下：

SELECT * FROM  db_item_standard.`parana_brands` 
where MATCH( `apply_category`) AGAINST ('7eklpnznr7');

原理分析

• 倒排索引

• 全文检索通常使用倒排索引来实现。倒排索引同 B+树索引一样，也是一种索引结构。它在辅助表中存储了单词和单词自身在一个或多个文档中所在位置之间的映射。
• inverted file index，其表现形式为 {单词， 单词所在文档的ID}
• full inverted index, 其表现形式为 {单词，(单词所在文档的ID，在具体文档中俄位置)}

例如：全文检索表t存储的内容如表

• DocumentId 表示进行全文检索文档的Id，Text表示存储的内容，用户需要对存储的这些文档内容进行全文检索。

对于 inverted file index 的关联数据，其存储内容如表所示

• 查询时直接根据 Documents得到包含查询关键字的文档

对于 full inverted index ，存储的是对pair，即（DocumentId，Position），因此其存储的倒排索引如表所示：

• 相比之下，full inverted index 占用更多的空间，但能更好地定位数据，并扩充一些其他的搜索特性。

1.4、聚集索引与非聚集索引区别？

聚簇索引，在聚集索引中，表中行的物理顺序与键值的逻辑（索引）顺序相同。一个表只能包含一个聚集索引， 即如果存在聚集索引，就不能再指定CLUSTERED 关键字

• 聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。聚簇索引将索引和数据行放到了一块，找到索引也就找到了数据。因为无需进行回表操作，所以效率很高。
• 聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。聚簇索引将索引和数据行放到了一块，找到索引也就找到了数据。因为无需进行回表操作，所以效率很高。

非聚集索引，数据库表中记录的物理顺序与索引顺序可以不相同。一个表中只能有一个聚集索引，但表中的每一列都可以有自己的非聚集索引

• 非聚簇索引则将数据存储和索引分开，找到索引后，需要通过对应的地址找到对应的数据行。MyISAM 的索引方式就是非聚簇索引

1.4.1、聚集索引详解

先插入数据，如下表

create table t (
  a int not null,
  b varchar(8000),
  c int not null,
  primary key (a),
  key idx_c(c)
) engine = innodb;
insert into t select 1,repeat('a', 7000), -1;
insert into t select 2,repeat('a', 7000), -2;
insert into t select 3,repeat('a', 7000), -3;
insert into t select 4,repeat('a', 7000), -4;

插入的列长度为 7000，因此可以使用人为的方式使目前每个页只能存放两个行记录。可以发现数据页上存放的是完整的每行的记录。而在非数据页的索引中，存放的仅仅是键值及指向数据页的偏移量，而不是一个完整的行记录

• 大致的构造如下图所示
  
  如果使用explain关键字进行sql分析

场景1：对主键排序

explain select * from Profile order by id limit 10;
************* 1.row ***************
id : 1
select_type : simple
table: profile
type : index
possible_keys : null
key : primary
ken_len:4
ref:null
rows:10
extra:

• 可以看到，虽然使用 order by对记录进行排序，但是在实际过程中并没有进行所谓的filesort操作，而这就是因为聚集索引的特点。

场景2：范围查询

• 即如果要查询主键某一范围内的数据，通过叶子节点的上层中间节点就可以得到页的范围，之后直接读取数据页即可。

explain select * from Profile where id>10 and id <1000;
************* 1.row ***************
id : 1
select_type : simple
table: profile
type : range
possible_keys : primary
key : primary
ken_len:4
ref:null
rows:14868
extra:using where

• 注意：rows代表的是一个预估值，不是确切的值，如果实际执行这句 SQL 的查询，可以看到实际上只有 9946条数据

1.4.2、非聚集索引详解(辅助索引)

对于辅助索引，叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外，每个叶子节点中的索引中还包含一个书签，这个书签告诉innoDB存储引擎哪里可以找到与索引相对应的行数据。

• 辅助索引大致的构造如下图所示
  

1.5、为什么MySQL数据库要用B+树存储索引？

1.5.3、为什么MySQL数据库要用B+树存储索引？而不用红黑树、Hash、B树？

• 红黑树：

• 如果在内存中，红黑树的查找效率比B树更高，但是涉及到磁盘操作，B树就更优了。因为红黑树是二叉树，数据量大时树的层数很高，从树的根结点向下寻找的过程，每读1个节点，都相当于一次IO操作，因此红黑树的I/O操作会比B树多的多。

• hash 索引

• 如果只查询单个值的话，hash 索引的效率非常高。
• 但是 hash 索引有几个问题：

• 1）不支持范围查询；
• 2）不支持索引值的排序操作；
• 3）不支持联合索引的最左匹配规则。

• B树索引：

• B树索相比于B+树，在进行范围查询时，需要做局部的中序遍历，可能要跨层访问，跨层访问代表着要进行额外的磁盘I/O操作；
• 另外，B树的非叶子节点存放了数据记录的地址，会导致存放的节点更少，树的层数变高。

1.5.4、MySQL 中的索引叶子节点存放的是什么?

MyISAM和InnoDB都是采用的B+树作为索引结构，但是叶子节点的存储上有些不同。

• MyISAM：主键索引和普通索引的叶子节点都是存放 key 和 key 对应数据行的地址。在MyISAM 中，主键索引和普通索引没有任何区别。
  
• InnoDB：主键索引存放的是 key 和 key 对应的数据行。普通索引存放的是 key 和 key 对应的主键值。因此在使用普通索引时，通常需要检索两次索引，首先检索普通索引获得主键值，然后用主键值到主键索引中检索获得记录。
  

1.5.5、B+树中一个节点到底多大合适？

• 1页或页的倍数最为合适。因为如果一个节点的大小小于1页，那么读取这个节点的时候其实也会读出1页，造成资源的浪费。所以为了不造成浪费，所以最后把一个节点的大小控制在1页、2页、3页等倍数页大小最为合适。
  
• 这里说的“页”是 MySQL 自定义的单位（和操作系统类似），MySQL 的 Innodb 引擎中1页的默认大小是16k，可以使用命令SHOW GLOBAL STATUS LIKE ‘Innodb_page_size’ 查看。
  
  
• 在 MySQL 中 B+ 树的一个节点大小为“1页”，也就是16k。
  
• 为什么一个节点为1页就够了？

• Innodb中，B+树中的一个节点存储的内容是：

• 非叶子节点：key + 指针
• 叶子节点：数据行（key 通常是数据的主键）

• 对于叶子节点：我们假设1行数据大小为1k（对于普通业务绝对够了），那么1页能存16条数据。
• 对于非叶子节点：key 使用 bigint 则为8字节，指针在 MySQL 中为6字节，一共是14字节，则16k能存放 16 * 1024 / 14 = 1170个。那么一颗高度为3的B+树能存储的数据为：1170 * 1170 * 16 = 21902400（千万级）。

• 所以在 InnoDB 中B+树高度一般为3层时，就能满足千万级的数据存储。在查找数据时一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次 IO 操作即可查找到数据。千万级别对于一般的业务来说已经足够了，所以一个节点为1页，也就是16k是比较合理的
  

1.6、联合索引（复合索引）的底层实现？最佳左前缀原则？

• 联合索引

• 根据创建联合索引的顺序，以最左原则进行where检索，比如（age，name）以age=1或age=1 and name=‘张三’ 可以使用索引，单以name=‘张三’ 不会使用索引，考虑到存储空间的问题，还请根据业务需求，将查找频繁的数据进行靠左创建索引。

• 排序规则

• 首先按照第一个索引排序，在第一个索引相同的情况下，再按第二个索引排序，依次类推。

• 如果查询顺序和联合索引的顺序不一致，优化器会自动做优化

• 即查询语句的where里面各个判断调换顺序没关系的

• Action：联合索引踩坑

• 对于联合索引：MySQL从左到右的使用索引中的字段，一个查询可以只使用索引中的一部份，但只能是最左侧部分。例如索引是key index （a,b,c）。 可以支持a | a,b| a,b,c 3种组合进行查找，但不支持 b,c进行查找 .当最左侧字段是常量引用时，索引就十分有效

• a，c 也是不行的，不能直接拿到结果

• 以字典为例，我们如果要查第2个字母为 k 的，通过目录是无法快速找的，因为首字母 A - Z 里面都可能包含第2个字母为 k 的

1.7、什么情况下设置了索引但无法使用？

以“%(表示任意0个或多个字符)”开头的LIKE语句，模糊匹配；

OR语句前后没有同时使用索引

数据类型出现隐式转化（如varchar不加单引号的话可能会自动转换为int型）

对于多列索引，必须满足最左匹配原则(eg：多列索引col1、col2和col3，则索引生效的情形包括 col1或col1，col2或col1，col2，col3)

1.8、什么样的字段适合创建索引？

经常作查询选择的字段

经常作表连接的字段

经常出现在order by, group by, distinct后面的字段

1.9、创建索引时需要注意什么？

非空字段：应该指定列为NOT NULL，含有空值的列很难进行查询优化(你应该用0、一个特殊的值或者一个空串代替空值)；

取值离散大的字段:（变量各个取值之间的差异程度）的列放到联合索引的前面；

索引字段越小越好：数据库的数据存储以页为单位一页存储的数据越多一次IO操作获取的数据越大效率越高。

1.10、什么是回表查询？

1.10.1、什么是回表查询？

• InnoDB 中，对于主键索引，只需要走一遍主键索引的查询就能在叶子节点拿到数据。
  
• 而对于普通索引，叶子节点存储的是 key + 主键值，因此需要再走一次主键索引，通过主键索引找到行记录，这就是所谓的回表查询，先定位主键值，再定位行记录。
  

1.10.2、走普通索引，一定会出现回表查询吗？

• 不一定，如果查询语句所要求的字段全部命中了索引，那么就不必再进行回表查询。

• 很容易理解，有一个 user 表，主键为 id，name 为普通索引，则再执行：select id, name from user where name = ‘xx’ 时，通过name 的索引就能拿到 id 和 name了，因此无需再回表去查数据行了。

1.11、union 和 union all 的区别

• union all：对两个结果集直接进行并集操作，记录可能有重复，不会进行排序。
  
• union：对两个结果集进行并集操作，会进行去重，记录不会重复，按字段的默认规则排序。
  
• 因此，从效率上说，UNION ALL 要比 UNION 更快。
  

2、InnoDB 的索引模型

在innoDB引擎中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表

前置条件

创建一张表：	create table parana_properties ( id int primary key, k int not null, name varchar(16), index (k) ) engine=InnoDB;
插入5条数据	insert into parana_properties (ID,k) values (100,1),(200,2),(300,3),(500,5),(600,6);
图1：两棵树的存储示意图（两棵B+树）
索引类型	细节
–	–
主键索引	(ID)(也被称为聚簇索引) 叶子节点存的是整行数据
非主键索引 (K)(也被称为二级索引,非聚簇索引)	叶子节点内容是主键的值 （还有一些事务id等数据）
算法演示网站

2.1、基于主键索引和普通索引的查询有什么区别？

2.2、哪些情况需要创建索引？

1、主键自动建立唯一索引

2、频繁作为查询条件的字段(经常出现在order by, group by, distinct后面的字段)

3、查询中与其它表关联的字段，外键关系建立索引

4、单键/组合索引选择？ 高并发下选择组合索引

5、查询中排序的字段，统计，分组的字段

不适合：

1、频繁增删改的字段不适合

2、where条件里用不到的不创建

3、表记录太少时

4、字段重复数据太多时，如性别表

2.3、数据库索引的存储结构一般是B+树，为什么不使用红黑树等普通的二叉树 美团

1、局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中

• 1、磁盘会顺序预读 页的整数倍的数据到内存中，减少磁盘的IO次数
• 2、磁盘顺序读取的效率很高

2、B树的节点大小设置为一页（4k），减少层间索引次数，效率较高；

• 一次检索最多需要h-1次I/O，渐进复杂度为O(h)=O(logdN)
• 实际应用中，出度d是非常大的数字，通常超过100，因此h非常小；

3、红黑树等高度较高，索引次数较多，即磁盘IO次数较多，性能较慢；

4、B+树所有的关键字都出现在叶子节点，内存中可以存入更多的关键字，减少磁盘I/O次数；

5、B+树叶子节点通过双向链表相连，链表中的关键字是有序的，适合范围查找(在数据库中基于范围的查询是非常频繁的，而B树只能中序遍历所有节点，效率太低)；

6、哈希虽然能够提供 O(1) 的单数据行操作性能， 但是对于范围查询和排序却无法很好地支持， 最终导致全表扫描；

7、B 树能够在非叶节子点中存储数据， 但是这也导致在查询连续数据时可能会带来更多的随机 I/O；

8、B+树的所有叶节点可以通过指针相互连接， 能够减少顺序遍历时产生的额外随机 I/O；

9、B 树一个节点里存的是数据， 而 B+树存储的是索引（ 地址） ， 所以 B 树里一个节点存不了很多个数据， 但是 B+树一个节点能存很多索引， B+树叶子节点存所有的数据；

10、B+树的叶子节点是数据阶段用了一个链表串联起来， 便于范围查找；

2.4、什么是 Buffer Pool？

• Buffer Pool 是 InnoDB 维护的一个缓存区域，用来缓存数据和索引在内存中，主要用来加速数据的读写，如果 Buffer Pool 越大，那么 MySQL 就越像一个内存数据库，默认大小为 128M。
  
• InnoDB 会将那些热点数据和一些 InnoDB 认为即将访问到的数据存在 Buffer Pool 中，以提升数据的读取性能。
  
• InnoDB 在修改数据时，如果数据的页在 Buffer Pool 中，则会直接修改 Buffer Pool，此时我们称这个页为脏页，InnoDB 会以一定的频率将脏页刷新到磁盘，这样可以尽量减少磁盘I/O，提升性能。
  

2.5、InnoDB 四大特性知道吗？

InnoDB存储引擎的关键特性包括：

• 1、插入缓冲
• 2、两次写
• 3、自适应哈希索引
• 4、异步IO async IO
• 5、刷新邻接页
  这些特性为 InnoDB 存储引擎带来更好的性能以及更高的可靠性。

2.5.1、插入缓冲（insert buffer）

• 索引是存储在磁盘上的，所以对于索引的操作需要涉及磁盘操作。如果我们使用自增主键，那么在插入主键索引（聚簇索引）时，只需不断追加即可，不需要磁盘的随机 I/O。

• 比如按下列 SQL定义表

create table_t {
  a int auto_increment,
  b varchar(30),
  primary key(a)
};

• 一般情况下，不需要随机读取另一个页中的记录。但如果是 UUID这样的类，会导致和辅助索引一样，可能导致插入并非连续的情况。

• 但是如果我们使用的是普通索引，大概率是无序的，此时就涉及到磁盘的随机 I/O，而随机I/O的性能是比较差的（Kafka 官方数据：磁盘顺序I/O的性能是磁盘随机I/O的4000~5000倍）。
  
• 因此，InnoDB 存储引擎开创性的设计了 Insert Buffer ，对于非聚集索引的插入或更新操作，不是每一次直接插入到索引页中，而是先判断插入的非聚集索引页是否在缓冲池（Buffer pool）中，若在，则直接插入；若不在，则先放入到一个 Insert Buffer 对象中，然后再以一定的频率和情况进行 Insert Buffer 和辅助索引页子节点的 merge（合并）操作，这时通常能将多个插入合并到一个操作中（因为在一个索引页中），这就大大提高了对于非聚集索引插入的性能。
  
• 插入缓冲的使用需要满足以下两个条件：

• 1）索引是辅助索引；
• 2）索引不是唯一索引。

• 因为在插入缓冲时，数据库不会去查找索引页来判断插入的记录的唯一性。如果去查找肯定又会有随机读取的情况发生，从而导致 Insert Buffer 失去了意义。
  

2.5.2、二次写（double write）

• 脏页刷盘风险：InnoDB 的 page size一般是16KB，操作系统写文件是以4KB作为单位，那么每写一个 InnoDB 的 page 到磁盘上，操作系统需要写4个块。于是可能出现16K的数据，写入4K 时，发生了系统断电或系统崩溃，只有一部分写是成功的，这就是 partial page write（部分页写入）问题。这时会出现数据不完整的问题。
  
• 这时是无法通过 redo log 恢复的，因为 redo log 记录的是对页的物理修改，如果页本身已经损坏，重做日志也无能为力。
  
• doublewrite 就是用来解决该问题的。

• 在应用重做日志前，用户需要一个页的副本，当写入失效发生时，先通过页的副本来还原该页，再进行重做，这就是 dubbowrite
• doublewrite 由两部分组成，一部分为内存中的 doublewrite buffer，其大小为 2MB，另一部分是磁盘上共享表空间中连续的128个页，即2个区(extent)，大小也是2M。
• 流程如下图所示
• 

• 为了解决 partial page write 问题，当 MySQL 将脏数据刷新到磁盘的时候，会进行以下操作：

• 1）先将脏数据复制到内存中的 doublewrite buffer
  
• 2）之后通过 doublewrite buffer 再分2次，每次1MB写入到共享表空间的磁盘上（顺序写，性能很高）
  
• 3）完成第二步之后，马上调用 fsync 函数，将doublewrite buffer中的脏页数据写入实际的各个表空间文件（离散写）。
  

• 如果操作系统在将页写入磁盘的过程中发生崩溃，InnoDB 再次启动后，发现了一个 page 数据已经损坏，InnoDB 存储引擎可以从共享表空间的 doublewrite 中找到该页的一个最近的副本，用于进行数据恢复了。
  

2.5.3、自适应哈希索引(adaptive hash index）

• 哈希（hash）是一种非常快的查找方法，一般情况下查找的时间复杂度为 O(1)。但是由于不支持范围查询等条件的限制，InnoDB 并没有采用 hash 索引，但是如果能在一些特殊场景下使用 hash 索引，则可能是一个不错的补充，而 InnoDB 正是这么做的。
  
• 具体的，InnoDB 会监控对表上索引的查找，如果观察到某些索引被频繁访问，索引成为热数据，建立哈希索引可以带来速度的提升，则建立哈希索引，所以称之为自适应（adaptive）的。自适应哈希索引通过缓冲池的 B+ 树构造而来，因此建立的速度很快。而且不需要将整个表都建哈希索引，InnoDB 会自动根据访问的频率和模式来为某些页建立哈希索引。
  

2.5.4、预读（read ahead）

• InnoDB 在 I/O 的优化上有个比较重要的特性为预读，当 InnoDB 预计某些 page 可能很快就会需要用到时，它会异步地将这些 page 提前读取到缓冲池（buffer pool）中，这其实有点像空间局部性的概念。
  
• 空间局部性（spatial locality）：如果一个数据项被访问，那么与他地址相邻的数据项也可能很快被访问。
  
• InnoDB使用两种预读算法来提高I/O性能：线性预读（linear read-ahead）和随机预读（randomread-ahead）。
  
• 其中，线性预读以 extent（块，1个 extent 等于64个 page）为单位，而随机预读放到以 extent 中的 page 为单位。线性预读着眼于将下一个extent 提前读取到 buffer pool 中，而随机预读着眼于将当前 extent 中的剩余的 page 提前读取到 buffer pool 中。
  
• 线性预读（Linear read-ahead）

• 线性预读方式有一个很重要的变量 innodb_read_ahead_threshold，可以控制 Innodb 执行预读操作的触发阈值。如果一个 extent 中的被顺序读取的 page 超过或者等于该参数变量时，Innodb将会异步的将下一个 extent 读取到 buffer pool中，innodb_read_ahead_threshold 可以设置为0-64（一个 extend 上限就是64页）的任何值，默认值为56，值越高，访问模式检查越严格。

• 随机预读（Random read-ahead）:

• 随机预读方式则是表示当同一个 extent 中的一些 page 在 buffer pool 中发现时，Innodb 会将该 extent 中的剩余 page 一并读到 buffer pool中，由于随机预读方式给 Innodb code 带来了一些不必要的复杂性，同时在性能也存在不稳定性，在5.5中已经将这种预读方式废弃。要启用此功能，请将配置变量设置 innodb_random_read_ahead 为ON。

3、索引维护

3.1、使用自增字段作主键优化查询

有没有什么场景适合用业务字段直接做主键的呢？

• 只有一个索引；
• 该索引必须是唯一索引。

3.2、使用覆盖索引优化查询？

从辅助索引(普通索引)中查询得到记录，而不需要通过聚族索引查询获得，MySQL 中将其称为覆盖索引。

• 当索引上包含了查询语句中的所有列时，我们无需进行回表查询就能拿到所有的请求数据，因此速度会很快。
• 当explain的输出结果Extra字段为Using index时，则代表触发覆盖索引。如下图所示
• 辅助索引不包含整行记录的所有信息，故其大小要远小于聚集索引，因此可以减少大量的IO操作。 使用场景| 需求| 解法
  –|–|–
  1、查询部分字段 |例如：需求是在商品表中查询商品的名称、价格信息。 |我们可以建立一个组合索引，即商品编码、名称、价格作为一个组合索引。如果索引中存在这些数据，查询将不会再次检索主键索引，从而避免回表。 CREATE IDX_code_name_price (code,name,price);
  2、统计数据| -|辅助索引，则会通过查询辅助索引来统计行数，减少 I/O 操作 SELECT COUNT(*)

使用关键字 force index 强制使用某个索引

select * from orderDetails force index(orderID) where orderId > 10000 and orderId <102000;

3.3、前缀索引优化

使用某个字段中字符串的前几个字符建立索引

3.4、执行计划

什么是执行计划：在执行一条 SQL 语句时，要想知道这个 SQL 先后查询了哪些表，是否使用了索引，这些数据从哪里获取到，获取到数据遍历了多少行数据等等，可以通过 EXPLAIN 命令来查看这些执行信息。

• （属性表）EXPLAIN SELECT * FROM parana_properties where status = 1 and value_type = 1 and attr_vals_json is not null
  

3.4.1、执行计划分析

• id：标识符
• select_type 表示 SELECT 查询类型

• 常见的有 SIMPLE（普通查询，即没有联合查询、子查询）
• PRIMARY（主查询）
• UNION（UNION 中后面的查询）
• SUBQUERY（子查询）等。

• table 当前执行计划查询的表，如果给表起别名了，则显示别名信息。
• partitions 访问的分区表信息
• type 表示从表中查询到行所执行的方式，查询方式是 SQL 优化中一个很重要的指标，结果值从好到差依次是：system > const > eq_ref > ref > range > index > ALL。

• system/const：表中只有一行数据匹配，此时根据索引查询一次就能找到对应的数据；
• eq_ref：使用唯一索引扫描，常见于多表连接中使用主键和唯一索引作为关联条件；
• ref：非唯一索引扫描，还可见于唯一索引最左原则匹配扫描；
• range：索引范围扫描，比如，<，>，between, in 等操作；
• index：索引全表扫描，此时遍历整个索引树；
• ALL：表示全表扫描，需要遍历全表来找到对应的行。

• possible_keys 可能使用到的索引key 实际使用到的索引;
• key_len 当前使用的索引的长度;
• ref 关联 id 等信息;
• rows 查找到记录所扫描的行数;
• filtered 查找到所需记录占总扫描记录数的比例;
• Extra 额外的信息;

3.4.2、explain 主要关注哪些字段？

• 主要关注 type、key、row、extra 等字段。主要是看是否使用了索引，是否扫描了过多的行数，是否出现 Using temporary、Using filesort 等一些影响性能的主要指标。

3.4.3、索引除了可以用于加速搜索外，还可以在排序时发挥作用，你能通过 EXPLAIN 来证明吗？你知道，针对排序在什么情况下，索引会失效吗？

排序使用到索引，在执行计划中的体现就是 key 这一列。如果没有用到索引，会在 Extra 中看到 Using filesort，代表使用了内存或磁盘进行排序。而具体走内存还是磁盘，是由sort_buffer_size 和排序数据大小决定的。

排序无法使用到索引的情况有：

• 对于使用联合索引进行排序的场景，多个字段排序 ASC 和 DESC 混用；
• a+b 作为联合索引，按照 a 范围查询后按照 b 排序；
• 排序列涉及到的多个字段不属于同一个联合索引；
• 排序列使用了表达式。

3.4.4、我们通过 EXPLAIN 命令看到了索引覆盖和回表的两种情况。你能用 optimizer trace 来分析一下这两种情况的成本差异吗？

如下代码所示，打开 optimizer_trace 后，再执行 SQL 就可以查询 information_schema.OPTIMIZER_TRACE 表查看执行计划了，最后可以关闭 optimizer_trace 功能：

SET optimizer_trace="enabled=on";
SELECT * FROM person WHERE NAME >'name84059' AND create_time>'2020-01-24 05:00:00';
SELECT * FROM information_schema.OPTIMIZER_TRACE;
SET optimizer_trace="enabled=off";

假设我们为表 person 的 NAME 和 SCORE 列建了联合索引，那么下面第二条语句应该可以走索引覆盖，而第一条语句需要回表：

explain select * from person where NAME='name1';
explain select NAME,SCORE from person where NAME='name1';

通过观察 OPTIMIZER_TRACE 的输出可以看到，索引覆盖（index_only=true）的成本是 1.21 而回表查询（index_only=false）的是 2.21，也就是索引覆盖节省了回表的成本 1。

索引覆盖：

analyzing_range_alternatives": {
  "range_scan_alternatives": [
  {
    "index": "name_score",
    "ranges": [
      "name1 <= name <= name1"
    ] /* ranges */,
    "index_dives_for_eq_ranges": true,
    "rowid_ordered": false,
    "using_mrr": false,
    "index_only": true,
    "rows": 1,
    "cost": 1.21,
    "chosen": true
  }
]

回表：

"range_scan_alternatives": [
  {
    "index": "name_score",
    "ranges": [
      "name1 <= name <= name1"
    ] /* ranges */,
    "index_dives_for_eq_ranges": true,
    "rowid_ordered": false,
    "using_mrr": false,
    "index_only": false,
    "rows": 1,
    "cost": 2.21,
    "chosen": true
  }
]

总结：

1. 默认使用 InnoDB 作为表存储引擎，创建的索引默认为 B+ 树数据结构，如果是主键索引，则属于聚族索引，非主键索引则属于辅助索引。基于主键查询可以直接获取到行信息，而基于辅助索引作为查询条件，则需要进行回表，然后再通过主键索引获取到数据；
2. 如果只是查询一列或少部分列的信息，我们可以基于覆盖索引来避免回表。覆盖索引只需要读取索引，且由于索引是顺序存储，对于范围或排序查询来说，可以极大地极少磁盘 I/O 操作；
3. 注意索引失效的情况发生，养成查看sql执行计划的习惯。

Action1: “N叉树”的N值在MySQL中是可以被人工调整的么？

• N相当于一页(16K)中存储节点的数量，是可以被调整的

Action2、MySQL的联合索引是怎么储存的？

• 联合索引(col1, col2,col3)也是一棵B+Tree，其非叶子节点存储的是第一个关键字的索引，而叶节点存储的则是三个关键字col1、col2、col3三个关键字的数据，且按照col1、col2、col3的顺序进行排序

Action3：商品中心-SQL like使用场景梳理及治理

• 背景：

• 0806早上7:40左右，慢sql 导致标准库CPU 100%持续数分钟。

/* Traceid: b119a98d7092953d8c244444dba42241 */ /* Brand.countListBySearchCriteria */ select count(1) from parana_brands WHERE status in ( 1 ) and `full_name` LIKE CONCAT('%', '多友益', '%');

• 品牌表 总数据量9.7w。QPS=17 并不算大，但是慢sql 引发了标准库CPU 持续100% ，引发一系列连锁反应（商品详情查询接口超时等等)
  

• 
  
• 
  
• 应急解决方案：加了联合索引ALTER TABLE db_item_standard.parana_brands ADD INDEX idx_status_fullname (status, full_name);

• 后期根治方案：走ES或缓存。（数据量如果过大，有极大隐患）

• 
  
• 存量业务梳理
  

Action4：MySQL冗余索引治理

Action5：如何将数据表时间加1，从而触发下游业务联动，例如：dump逻辑

• 脚本如下：将品牌表的更新时间加1s，可以触发es中品牌表的自动dump

UPDATE  db_item_standard.parana_brands 
set  `updated_at` = DATE_ADD(`updated_at`, INTERVAL 1 second) 
where `status` != -3;

Action6：通过阿里云监控查看MySQL慢查询

• 线上慢SQL

EXPLAIN SELECT config_id,brand_id,specification
FROM zcy_item_mark_detail
WHERE update_at >= '2022-08-26 00:00:00' and update_at <= '2022-08-29 00:00:00' and auth_invalid_date >= '2022-08-29 00:00:00';

• 问题：没有用上索引
• 解决方法：给更新时间字段和授权失效时间字段加索引

• 通过阿里云监控查看MySQL慢查询
  
• 
  

栉风沐雨，砥砺前进 --刘超