MySql-03-索引

2021-07-26 MySql MySql 0 Comments

索引是一种为了提升查询效率的数据结构，B+树索引并不能找到一个给定键值的具体行。只能找到数据行所在的页，然后数据库通过把页读到内存中进行查找。每个数据页都通过一个双向链表来进行链接

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

索引模型

哈希表：O(1)的时间复杂度，适用于等值查询，不支持范围查询

有序数组：lgN的时间复杂度(二分查找)，支持等值查询和范围查询，但插入效率低，适用于静态存储引擎(数据不再变化)

搜索树：InnoDB使用B+树结构建立索引，父节点左子树所有节点的值小于父节点的值，右子树所有节点的值大于父节点的值。

InnoDB的为N叉树，差不多为1200

MySql默认一个节点的长度为16K，整数(bigint)字段索引长度为 8B，每个索引还跟着6B的指向其子树的指针；所以16K/14B ≈ 1170

在 InnoDB 中，每一张表其实就是多个 B+ 树，即一个主键索引树和多个非主键索引树。
执行查询的效率，使用主键索引 > 使用非主键索引 > 不使用索引

为什么主键比非主键快(主键索引和非主键索引)？

主键索引的b+树的叶子节点存储的是具体的行数据，非叶子节点存储的是主键的值。叶子节点之间通过链表连接，也称为 聚簇索引

非主键索引的叶子节点存储的是主键的值，所以通过非主键索引查询数据时，先找到主键，再去主键索引上根据主键找到具体的行数据，也称 二级索引。这个过程叫做回表

如果不使用索引进行查询，则从主索引 B+ 树的叶子节点进行遍历

例如：存在下列这样一个表

mysql> create table T(
	id int primary key, 
	k int not null, 
	name varchar(16),
index (k))engine=InnoDB;

R1~R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6) 则

主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引(clustered index)

非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引(secondary index)

联合索引

联合索引(Composite Index)是指同时包含多个列的索引。

最左匹配原则：指的就是如果你的 SQL 语句中用到了联合索引中的最左边的索引，那么这条 SQL 语句就可以利用这个联合索引去进行匹配，当遇到范围查询(>、<、between、like)就会停止匹配

假设对(a,b)字段建立一个索引

如果条件为下面是可以匹配索引的
1
2
a = 1
a = 1 and b = 2
如果条件为下面也是可以匹配索引的，因为优化器会优化语句
1
b = 2 and a =1
如果条件为下面就不能匹配索引
1
b = 2
如果使用对(a,b,c,d)建立索引，条件为下面内容，那么，a,b,c三个字段能用到索引，而d就匹配不到
1
a = 1 and b = 2 and c > 3 and d = 4

看一下几个联合问题就懂了

如果sql为 SELECT * FROM table WHERE a = 1 and b = 2 and c = 3; 那么如何建立索引

答：(a,b,c)或者(c,b,a)或者(b,a,c)都可以，重点要的是将区分度高的字段放在前面，区分度低的字段放后面。像性别、状态这种字段区分度就很低
如果sql为 SELECT * FROM table WHERE a > 1 and b = 2; 那么如何建立索引

答：对(b,a)建立索引。如果建立的是(a,b)索引，那么只有a字段能用得上索引，毕竟最左匹配原则遇到范围查询就停止匹配。
如果对(b,a)建立索引那么两个字段都能用上，优化器会调整where后a,b的顺序，让语句用上索引
如果sql为 SELECT * FROM table WHERE a > 1 and b = 2 and c > 3; 那么如何建立索引

答: (b,a)或者(b,c)都可以
如果sql为 SELECT * FROM table WHERE a = 1 and b = 2 and c > 3; 那么如何建立索引

答：(b,a,c)或者(a,b,c)都可以
如果sql为 SELECT * FROM table WHERE a = 1 ORDER BY b;那么如何建立索引

答：对(a,b)建索引，当a = 1的时候，b相对有序，可以避免再次排序！
如果sql为 SELECT * FROM table WHERE a > 1 ORDER BY b;那么如何建立索引

答：对(a)建立索引，因为a的值是一个范围，这个范围内b值是无序的，没有必要对(a,b)建立索引
如果sql为 SELECT * FROM table WHERE a = 1 AND b = 2 AND c > 3 ORDER BY c;那么如何建立索引

答：对(a，b)建立索引，此时c排序是用不到索引的
如果sql为 SELECT * FROM table WHERE a IN (1,2,3) and b > 1; 那么如何建立索引

答：对(a，b)建立索引，因为IN在这里可以视为等值引用，不会中止索引匹配，所以还是(a,b)!
如果sql为 SELECT * FROM table WHERE a = 1 AND b IN (1,2,3) AND c > 3 ORDER BY c;那么如何建立索引

答：对(a，b)建立索引，此时c排序是用不到索引的。

它的结构与单列索引（单列的非聚簇索引）有一些不同。以下是联合索引的一般结构：

排序顺序：联合索引按照索引键的排序顺序组织数据。联合索引的键由多个列组成，并且按照从左到右的顺序进行排序。
索引键值：联合索引的叶子节点存储了联合索引键的值。这些索引键值是根据多个列的值生成的，用于定位到相应的行数据。
主键引用：为了获取具体的行数据，联合索引的叶子节点通常会包含指向主键的引用。这个主键引用可以是主键的值，或者是指向包含主键值的位置的指针。通过主键引用，可以从联合索引快速地定位到相应的行数据。
覆盖索引：如果联合索引包含了查询所需的所有列，称为覆盖索引（Covering Index）。在这种情况下，可以直接从联合索引中获取所需的数据，而无需回表操作，提高查询性能。

索引失效的情况：

失效指的是，条件中如果有or，只要其中一个条件没有索引，其他字段有索引也不会使用

索引维护

在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上，由各叶子节点进行连接

默认使用升序排序，在升序排序中，索引键的值按照从小到大的顺序进行排序。对于数字类型的列，从小到大表示较小的值排在前面；对于字符串类型的列，按照字典顺序排序，即按照字符的ASCII码进行比较

B+树的插入操作

Leaf Page 满	Index Page 满	操作
No	No	1. 直接将数据插入叶子节点
Yes	No	1. 拆分叶子节点 2. 将中间的额节点存放入 Index Page中 3. 小于中间节点的记录放左边 4. 大于或等于中间节点的记录方右边
Yes	Yes	1. 拆分叶子节点 2. 小于中间接待你的记录方左边 3. 大于或等于中间节点的记录放右边 4. 拆分Index Page 5. 小于中间节点的记录放左边 6. 大于中间节点的记录放右边 7. 中间节点放入上一层 Index Page

旋转发生在Leaf Page已经满了，但是其左右兄弟节点并没有满的情况下。B+树并不会急于拆分页的操作，而是将记录移动所在页的兄弟节点上。通常情况下，左兄弟会被首先检查用来做旋转操作

B+树的删除操作

叶子节点小于填充因子	中间节点小于填充因子	操作
No	No	1. 直接将记录从叶子节点删除，如果该节点还是Index Page的节点，用该节点的右节点代替
Yes	No	1. 合并叶子节点和它的兄弟节点，同时更新Index Page
Yes	Yes	1. 合并叶子节点和它的兄弟节点 2. 更新Index Page 3. 合并Index Page 和它的兄弟节点

最好使用自增主键做为主索引，如上图所示：参见 B+树的插入与删除

如果插入新的行 ID 值为 700，则只需要在 R5 的记录后面插入一个新记录。
如果新插入的 ID 值为 400，需要逻辑上挪动后面的数据，空出位置。而更糟的情况是：
- 如果 R5 所在数据页满了，则申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂，影响性能
- 原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约 50%。当然有分裂就有合并。当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程，影响空间利用率

所以在主键选择的时候：

主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小
在KV场景下只有一个索引，且必须是唯一索引，在直接使用业务字段做主键

索引要根据表中的每一行的记录值来创建，所以需要全表扫描

加字段或修改字段，也要修改每一行记录中的对应列的数据，所以也要全表扫描

查询过程

执行查询语句 select id from T where id = 5 id为普通索引，查询过程为：

先通过 B+ 树从树根开始，按层搜索到叶子节点及数据页
然后在数据页内部通过二分法来定位记录

对于普通索引来说，查找到满足条件的第一个记录 (5,500) 后，需要查找下一个记录，直到碰到第一个不满足 k=5 条件的记录。

对于唯一索引来说，由于索引定义了唯一性，查找到第一个满足条件的记录后，就会停止继续检索

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

更新过程

redo log是物理日志，记录的是数据页的修改，但是如果数据页不在内存中怎么办呢？都没有去修改数据页，redo log中记什么？所以这时候change buffer登场了，如果修改的不是唯一索引，而是普通索引，不用再去磁盘随机IO了，直接将这个修改记录在change buffer中。也就是说

如果数据页在内存，那就修改数据页，写redo log，
如果数据页不在内存，修改的也不是唯一索引，而是普通索引，那就写change buffer。并把这个change buffer写入到redo log，防止更新丢失。

比如在表中插入一条数据

1	mysql> insert into t(id,k) values(id1,k1),(id2,k2);

假设当前 k 索引树的状态，查找到位置后，k1 所在的数据页在内存 (InnoDB buffer pool) 中，k2 所在的数据页不在内存中。如图 2 所示是带 change buffer 的更新状态图

数据表空间：就是一个个的表数据文件，对应的磁盘文件就是“表名.ibd”；

系统表空间：用来放系统信息，如数据字典等，对应的磁盘文件是“ibdata1”

更新语句的操作如下：

Page 1在内存中，直接更新内存
Page 2 不在内存中，就在内存的 change buffer 区域，记录下“我要往 Page 2 插入一行”这个信息
将上述两个动作记入 redo log 中

做完上面这些，事务就可以完成了。所以，你会看到，执行这条更新语句的成本很低，就是写了两处内存，然后写了一处磁盘（两次操作合在一起写了一次磁盘），而且还是顺序写的。同时写入 change buffer 和数据表空间都是后台空间，不影响更新的响应时间

然后执行查询语句，如果读语句发生在更新语句后不久，内存中的数据都还在，那么此时的这两个读操作就与系统表空间（ibdata1）和 redo log（ib_log_fileX）无关了

1	select * from t where k in (k1, k2)

读 Page 1 的时候，直接从内存返回。

WAL 之后如果读数据，是不是一定要读盘，是不是一定要从 redo log 里面把数据更新以后才可以返回？其实是不用的。你可以看一下图 3 的这个状态，虽然磁盘上还是之前的数据，但是这里直接从内存返回结果，结果是正确的。
要读 Page 2 的时候，需要把 Page 2 从磁盘读入内存中，然后应用 change buffer 里面的操作日志，生成一个正确的版本并返回结果。可以看到，直到需要读 Page 2 的时候，这个数据页才会被读入内存

redo log 主要节省的是随机写磁盘的 IO 消耗（转成顺序写），而 change buffer 主要节省的则是随机读磁盘的 IO 消耗

change buffer记录索引页的变化；但是change buffer本身也是要持久化的，而它持久化的工作和其他页一样，交给了redo日志来帮忙完成；

redo log 记录的是change buffer页的变化。

change buffer持久化文件是 ibdata1，索引页持久化文件是 t.ibd

change buffer 一开始是写内存的，那么如果这个时候机器掉电重启，会不会导致 change buffer 丢失呢？

change buffer有一部分在内存有一部分在ibdata. 做purge操作,应该就会把change buffer里相应的数据持久化到ibdata
redo log里记录了数据页的修改以及change buffer新写入的信息如果掉电,持久化的change buffer数据已经purge,不用恢复。主要分析没有持久化的数据情况又分为以下几种:
- change buffer写入,redo log虽然做了fsync但未commit,binlog未fsync到磁盘,这部分数据丢失
- change buffer写入,redo log写入但没有commit,binlog以及fsync到磁盘,先从binlog恢复redo log,再从redo log恢复change buffer
- change buffer写入,redo log和binlog都已经fsync.那么直接从redo log里恢复。

merge 的执行流程是这样的：从磁盘读入数据页到内存（老版本的数据页）；从 change buffer 里找出这个数据页的 change buffer 记录 (可能有多个），依次应用，得到新版数据页；写 redo log。这个 redo log 包含了数据的变更和 change buffer 的变更。

普通索引和唯一索引的查询性能几乎一样, 但是写性能是普通索引快, 因为可以用到change buffer, 唯一索引会导致内存命中率下降

change buffer 用的是 buffer pool 里的内存，因此不能无限增大。change buffer 的大小，可以通过参数 innodb_change_buffer_max_size 来动态设置。

设置为 50 的时候，表示 change buffer 的大小最多只能占用 buffer pool 的 50%
设置为0 表示关闭change buffer功能

索引选择

在 MySQL 中一张表可以支持多个索引。但写 SQL 语句的时候并没有主动指定使用哪个索引，MySql是怎么决定使用哪个索引的

1	force Index(a) #强制使用指定的索引

使用下面三条SQL语句查看查询过程

1
2
3

set long_query_time=0;
select * from t where a between 10000 and 20000; /*Q1*/
select * from t force index(a) where a between 10000 and 20000;/*Q2*/

将慢查询的日志阀值设置为0，则接下来所有查询操作都记录到慢查询日志中
Q1 使用默认查询语句
Q2 强制使用索引a进行查询

优化器的逻辑

行数
临时表
是否排序

扫描行数是怎么判断的？

MySql在执行语句之前，并不能精确地知道满足这个条件的记录有多少条，而只能根据统计信息来估算记录数。一个索引上不同的值越多，这个索引的区分度就越好。而一个索引上不同的值的个数，我们称之为“基数”（cardinality）。也就是说，这个基数越大，索引的区分度越好
使用 show index 方法，看到一个索引的基数。

如果正确的使用索引

使用强制语句 force index(a)
引导 MySQL 使用我们期望的索引，如 order by b limit 1 改成 order by b,a limit 1

优化器选择使用索引 b，是因为它认为使用索引 b 可以避免排序(b 本身是索引，已经是有序的了，如果选择索引 b 的话，不需要再做排序，只需要遍历)，所以即使扫描行数多，也判定为代价更小。现在 order by b,a 这种写法，要求按照 b,a 排序，就意味着使用这两个索引都需要排序。因此，扫描行数成了影响决策的主要条件，于是此时优化器选了只需要扫描 1000 行的索引 a

索引失效的情况：

不使用索引列进行查询：如果查询条件中没有使用索引列，数据库引擎将无法使用索引进行优化，而是需要进行全表扫描。这种情况下索引将失效，查询性能会下降。
使用函数或表达式对索引列进行操作：当在索引列上应用函数、运算符或表达式时，索引可能无法被利用。数据库引擎无法直接在索引上执行这些操作，而是需要在数据行级别上执行，导致索引失效。
列类型不匹配：如果查询条件中的列类型与索引列的类型不匹配，索引也无法被使用。例如，索引列是字符串类型，但查询条件中使用了数字类型，或者索引列是日期类型，但查询条件中使用了字符串类型。
数据量过小：如果表中的数据量非常小，即使存在索引，数据库引擎可能会选择全表扫描而不是使用索引。这是因为全表扫描的成本较低，使用索引反而增加了查询的开销。
索引列上存在数据类型转换：如果查询条件中的值需要进行数据类型转换才能与索引列进行比较，索引可能会失效。例如，查询条件中的值是字符串类型，而索引列是整数类型，会导致索引失效。
索引列上存在NULL值：某些情况下，如果索引列包含NULL值，查询条件中包含对该列的判断，索引可能无法被使用。
数据分布不均匀：如果索引列的数据分布不均匀，即某些值的出现频率较高，而其他值的出现频率较低，索引的选择性较低，可能导致索引失效。

要避免索引失效，需要根据查询条件、数据类型、数据分布等因素进行索引的设计和优化。同时，使用正确的查询方式，避免对索引列进行函数操作或类型转换，以确保索引能够被有效利用，提高查询性能。

参考链接

《高性能myql》
《InnoDB技术内幕-索引与算法》
https://time.geekbang.org/column/article/70848
https://www.cnblogs.com/rjzheng/p/12557314.html

Yuan Kang

Learn and live