MySQL基础篇-索引

深入浅出索引

索引的出现其实就是为了提高数据查询的效率，就像书的目录一样。

索引的常见模型

索引的出现是为了提高查询效率，但是实现索引的方式却是有很多钟，所以这里也就引入了索引模型的概念。可以用于提高读写效率的数据结构很多，常见也比较简单的数据结构，它们分别是哈希表、有序数组和搜索树

哈希表

是一种以键-值（key-value）存储数据的结构，我们只要输入待查找的值即key，就可以找到其对应的值Value。

这种数据结构的弊端：

• key经过hash换算，会出现同一个值的情况。需要使用链表来维护
• 哈希表这种结构适合用户只有等值查询的场景—-NoSQL引擎。

有序数组

有序数组在等值查询和范围查询场景中的性能就都非常优秀

这种数据结构的弊端：

• 查询方便但是更新数据的时候就麻烦了，在中间插入的时候就必须挪动后面所有的记录，成本很高。
• 有序数组索引只适用于静态存储引擎。

二叉搜索树

特点：每个节点的左儿子小于父节点，父节点又小于右儿子。时间复杂度O(log(N))

为了维持O(log(N))的查询复杂度，你就需要保持这颗树是平衡二叉树。为了做这个保证，更新的时间复杂度也是O(log(N))

平衡二叉树：其中每一个节点的左子树和右子树的高度差至多等于1

二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不知存在内存中，还要写在磁盘上。

N叉树由于在读写上的性能又带你，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。

在MySQL中，索引是在存储引擎层实现的，所以并没有统一的索引标准，即不同存储引擎的索引的工作方式并不一样。而即使多个存储引擎支持同一种类型的索引，其底层的实现也可能不同。由于InnoDB存储引擎在MySQL数据库中使用最为广泛。

InnoDB的索引模型

InnoDB使用了B+树索引模型，所以数据都是存储在B+树中的。

每个索引在InnoDB里面对应一颗B+树。

假设，我们有一个主键列为ID的表，表中有字段K，并且存在k上有索引

建表语句：

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).

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

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

也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，在应用中应该尽量使用主键查询。

索引维护

B+树为了维护索引有序性，在插入新值的时候需要做必要的维护，如果插入新的行ID值为700，则需要在R5的记录后面插入一个新记录。如果新插入的ID值为400，就相对麻烦了，需要逻辑上挪动后面的数据，空出位置。

更糟糕的情况是，如果R5所在的数据页已经满了，根据B+树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页的分裂。在这种情况下，性能自然会受到影响。

除了性能外，页分裂操作还影响数据页的利用率，原本放在一个页的数据，现在分到两个页中，整体空间利用率降低了50%。

当然有分裂就有合并。当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是的分裂过程的逆过程。

在一些建表规范中见到过类似的描述，要求建表语句里一定要有自增主键。当然事无绝对，接下来分析一下哪些场景应该使用自增主键，而哪些场景下不应该。

自增主键是指自增列上定义的主键，在建表语句中一般是这么定义的：NOT NULL PRIMARY KEY AUTO_INCREMENT.

插入新纪录的时候可以不指定ID的值，系统会获取当前ID最大值加1作为下一条 记录的ID值。

也就是说，自增主键的插入数据模式，正符合了我们前面提到的递增插入的场景。每次插入一条新纪录，都是追加操作，都不涉及到挪动其他的记录，也不会触发叶子节点的分裂。

而有业务逻辑的字段做主键，则往往不容易保证有序插入，这样写数据成本对象较高。

除了考虑性能外，我们还从存储空间的角度来看。假设你的表中确实有一个唯一字段，比如字符串类型的身份证号，那应该用身份证做主键，还是用自增字段做主键呢？

由于每个非主键索引的叶子节点上都是主键的值。如果用身份证好做主键，那么每个耳机索引的叶子节点占用约20个字符，而如果用整型做主键，则只要4个字符，如果是长整型(bigint)则是8个字符.

显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小

只有一个索引，该索引必须是唯一索引。这种情况下可以用业务字段直接做主键。

类似KV场景。

SQL语句重建索引

alter table T drop index k;
alter table T add index(k);

alter table T drop primary key;
alter table T add primary key(id);

重建主键是不合理的，不论是删除主键还是创建主键，都会将整个表重建。

可以用一句话代替

alter table T engine = InnoDB

MySQL索引有关概念

我们要执行select * from T where K between 3 and 5，需要执行几次树的搜索操作，会扫描多少行？

mysql> create table T (
ID int primary key,
k int NOT NULL DEFAULT 0, 
s varchar(16) NOT NULL DEFAULT '',
index k(k))
engine=InnoDB;

insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

这条SQL查询语句的执行流程：

1. 在k索引树上找到k=3的记录，取得ID=300；
2. 再到ID搜索树查找到ID=300对应的R3；
3. 在k索引树取下一个值k=5，取得ID=500；
4. 再回到ID索引树查找到ID=500对应的R4；
5. 在k索引树取下一个值k=6，不满主条件；
6. 循环结束。

在这个过程中，回到主键索引树搜索的过程，我们称为回表。（在实际生产中如何避免回表呢？）

覆盖索引

如果执行的语句是select ID from T where k between 3 and 5，这时只需要查询ID的值，而ID的值已经在k索引树上了，因此可以直接提供查询结果，不需要回表。也就是说，在这个查询里面，索引k已经覆盖了我们的查询需求，我们称为覆盖索引

由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。

在引擎内部使用覆盖索引在索引k上其实读了三个记录，R3～R5(对应的索引k上的记录项)，但是对于MySQL的server层来说，它就是找引擎拿到两条记录，因此MySQL认为扫描行数是2.

在一个市民信息表上，是否有必要将身份证号和名字建立联合索引？

CREATE TABLE `tuser` (
  `id` int(11) NOT NULL,
  `id_card` varchar(32) DEFAULT NULL,
  `name` varchar(32) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `ismale` tinyint(1) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `id_card` (`id_card`),
  KEY `name_age` (`name`,`age`)
) ENGINE=InnoDB

我们知道，身份证是使命的唯一标识。也就是说，如果根据身份证号查询市民信息的需求，我们只要身份证号字段上建立索引就够了。而在建立一个（身份证号、姓名）的联合索引，是不是浪费空间呢？

如果现在有一个高频请求，要根据市民身份证号码查询他的姓名，这个联合索引就有意义了。它可以在这个高频请求上用到覆盖索引，不再需要回表查整行记录，减少语句的执行时间。

最左前缀原则

B+树这种索引结构，可以利用索引的“最左前缀”，来定位记录。

为了直观地说明这个概念，我们用（name，age）这个联合索引来分析。

可以看到，索引项是按照索引定义里面出现的字段顺序排序的。

当逻辑需求是查到所有名字是“张三“的人时，可以快速定位到ID4，然后向后便利得到所有需要的结果。

如果你要查的所有名字第一个字是”张“的人，你的SQL语句的条件是where name like ‘张%’。这时，你也能够用上这个索引，查找到第一个符合条件的记录是ID3，然后向后遍历，直到不满足条件为止。

基于最左前缀索引的说明：

• 第一原则，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。
• 联合索引，如果查询条件只有b的语句，是无法使用（a，b）这个联合索引的。
• 需要考虑的原则就是空间了。是否设置单字段索引b

索引下推

满足最左前缀原则的情况下的查询，如果后面的查询条件中还有包含的联合索引的其他的值，则会利用联合索引进行索引下推去判断，而不会直接回表。

问题思考

当备库用-single-transaction做逻辑备份的时候，如果从主库的binlog传来一个DDL语句会怎么样？

Q1:SET SESSION TRANSACTION ISOLATION LEVEL REPEATABLE READ;
Q2:START TRANSACTION  WITH CONSISTENT SNAPSHOT；
/* other tables */
Q3:SAVEPOINT sp;
/* 时刻 1 */
Q4:show create table `t1`;
/* 时刻 2 */
Q5:SELECT * FROM `t1`;
/* 时刻 3 */
Q6:ROLLBACK TO SAVEPOINT sp;
/* 时刻 4 */
/* other tables */

• 在备份开始的时候，为了确保RR隔离级别，在设置一次RR隔离级别(Q1)

• 启动事务，这里用with consistent snapshot确保这个语句执行完就可以得到一个一致性视图(Q2)

• 设置一个保存点，这个很重要(Q3)

• show create 是为了拿到表结构(Q4),然后正式导数据(Q5),回滚导savepoint sp，在这里的作用是释放t1的MDL锁(Q6)。

DDL从主库传递过来的时间按照效果不通，假设四个时刻。

1. 如果在Q4语句执行之前就到达，现象：没有影响，备份拿到的是DDL之后的表结构。
2. 如果在“时刻2”到达，则表结果被改过，Q5执行的时候，报Table definition has changed，please retry transaction，现象：mysqldump终止；
3. 如果在“时刻2”和“时刻3”之间到达的，mysqldump占着t1的MDL读锁，binlog被阻塞，现象：主从延迟，直到Q6执行完成。
4. 从“时刻4”开始，mysqldump释放了MDL读锁，现象：没有影响，备份拿到的是DDL前的表结构。