MySQL 索引和锁

一、索引

  索引是帮助 MySQL 高速获取数据的排好序的数据结构。索引的出现是为了提高查询效率，但是实现索引的方式却有很多种。可以用于提高读写效率的数据结构很多，这里介绍三种常见、也比较简单的数据结构，它们分别是哈希表、有序数组和搜索树。

1、索引结构

（1）哈希表

  哈希表是一种以键-值（key-value）存储数据的结构，输入待查找的值（key），就可以找到其对应的值即 value。哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。多个 key 值经过哈希函数的换算，会出现同一个值的情况。处理这种情况的一种方法是，拉出一个链表。

  因为哈希表不是有序的，所以哈希索引做区间查询时的速度是很慢的，需要把区间中所有的 key 查找一遍。哈希表这种结构适用于只有等值查询的场景。

（2）有序数组

  有序数组在等值查询和范围查询场景中的性能就都非常优秀，查询指定元素只需要 O(log(N))。如果仅仅看查询效率，有序数组就是最好的数据结构了。但是，在需要更新数据的时候就麻烦了，你往中间插入一个记录就必须得挪动后面所有的记录，成本太高。所以，有序数组索引只适用于静态存储引擎。

（3）二叉搜索树

  二叉搜索树的特点是：每个节点的左儿子小于父节点，父节点又小于右儿子。为了维持 O(log(N)) 的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是 O(log(N))。

  树可以有二叉，也可以有多叉。多叉树就是每个节点有多个儿子，儿子之间的大小保证从左到右递增。二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上。

  一棵 100 万节点的平衡二叉树，树高 20。一次查询可能需要访问 20 个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要 10 ms左右的寻址时间。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 20 个 10 ms的时间，这个查询可真够慢的。为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。那么，我们就不应该使用二叉树，而是要使用“N叉”树。这里，“N叉”树中的“N”取决于数据块的大小。

（4）B 树

B-Tree

• 叶节点具有相同的深度，叶节点的指针为空；
• 所有索引元素不重复；
• 节点中的数据索引从左到右递增排序。

B+Tree

• 非叶子节点不存储 data，只存储索引（冗余），可以放更多索引；
• 叶子节点包含所有索引字段；
• 叶子节点用指针连接，提高区间访问性能。

2、InnoDB 的索引模型

  在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。它使用了 B+ 树索引模型。

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

• 主键索引也被称为聚簇索引（clustered index）。聚集索引的顺序就是数据的物理存储顺序，因为数据在物理存放时只能有一种排列方式，所以一个表只能有一个聚集索引。
• 非主键索引也被称为二级索引（secondary index）和非聚簇索引。

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

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

  非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。

3、索引的优化

（1）索引维护

  B+树为了维护索引有序性，在插入新值的时候需要做必要的维护。如果插入所在的数据页已经满了，根据B+树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能自然会受影响。除了性能外，页分裂操作还影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约50%。

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

（2）自增主键

  自增主键是指自增列上定义的主键。插入新记录的时候可以不指定ID的值，系统会获取当前ID最大值加1作为下一条记录的ID值。也就是说，自增主键的插入数据模式，正符合了我们前面提到的递增插入的场景。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。

  除了考虑性能外，我们还可以从存储空间的角度来看。假设你的表中确实有一个唯一字段，比如字符串类型的身份证号，那应该用身份证号做主键，还是用自增字段做主键呢？由于每个非主键索引的叶子节点上都是主键的值。如果用身份证号做主键，那么每个二级索引的叶子节点占用约20个字节，而如果用整型做主键，则只要4个字节，如果是长整型（bigint）则是8个字节。**显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。**所以，从性能和存储空间方面考量，自增主键往往是更合理的选择。

  **有没有什么场景适合用业务字段直接做主键的呢？**有些业务的场景需求是这样的：只有一个索引；该索引必须是唯一索引。由于没有其他索引，所以也就不用考虑其他索引的叶子节点大小的问题。这时我们要优先考虑“尽量使用主键查询”原则，直接将这个索引设置为主键，可以避免每次查询需要搜索两棵树。

（3）覆盖索引

  如果执行的语句是 select ID from T where k between 3 and 5，这时只需要查 ID 的值，而 ID 的值已经在 k 索引树上了，因此可以直接提供查询结果，不需要回表。也就是说，在这个查询里面，索引 k 已经“覆盖了”我们的查询需求，我们称为覆盖索引。**由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。**当然，索引字段的维护总是有代价的。因此，在建立冗余索引来支持覆盖索引时就需要权衡考虑了。

（4）最左前缀原则

  B+ 树这种索引结构，可以利用索引的“最左前缀”，来定位记录。不只是索引的全部定义，只要满足最左前缀，就可以利用索引来加速检索。这个最左前缀可以是联合索引的最左N个字段，也可以是字符串索引的最左M个字符。

  基于上面对最左前缀索引的说明，需要注意：在建立联合索引的时候，如何安排索引内的字段顺序。

  这里我们的评估标准是，索引的复用能力。因为可以支持最左前缀，所以当已经有了（a,b）这个联合索引后，一般就不需要单独在 a 上建立索引了。因此，第一原则是，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。

  查询条件里面只有 b 的语句，是无法使用（a,b）这个联合索引的，这时候你不得不维护另外一个索引。这时候，我们要考虑的原则就是空间了。name字段是比age字段大的 ，那建议创建一个（name,age）的联合索引和一个（age）的单字段索引。

（5）索引下推

  上一段说到满足最左前缀原则的时候，最左前缀可以用于在索引中定位记录。这时，你可能要问，那些不符合最左前缀的部分，会怎么样呢？

  以联合索引（name, age）为例。如果现在有一个需求：检索出表中“名字第一个字是张，而且年龄是10岁的所有男孩”。那么，SQL语句是这么写的：

select * from tuser where name like '张%' and age=10 and ismale=1;

  用前缀索引规则，所以这个语句在搜索索引树的时候，只能用“张”，找到满足条件的记录。当然，这还不错，总比全表扫描要好。

• 在 MySQL 5.6 之前，只能将查找到的数据开始一个个回表。到主键索引上找出数据行，再对比字段值。
• 而 MySQL 5.6 引入的索引下推优化（index condition pushdown)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

（6）索引重建

  为什么要重建索引？索引可能因为删除，或者页分裂等原因，导致数据页有空洞，重建索引的过程会创建一个新的索引，把数据按顺序插入，这样页面的利用率最高，也就是索引更紧凑、更省空间。

4、实战

  有这么一个表，表结构定义类似这样的：

CREATE TABLE `geek` (
  `a` int(11) NOT NULL,
  `b` int(11) NOT NULL,
  `c` int(11) NOT NULL,
  `d` int(11) NOT NULL,
  PRIMARY KEY (`a`,`b`),
  KEY `c` (`c`),
  KEY `ca` (`c`,`a`),
  KEY `cb` (`c`,`b`)
) ENGINE=InnoDB;

  由于历史原因，这个表需要 a、b 做联合主键。，既然主键包含了 a、b 这两个字段，那意味着单独在字段 c 上创建一个索引，就已经包含了三个字段了呀，为什么要创建 "ca"、"cb" 这两个索引？因为他们的业务里面有这样的两种语句：

select * from geek where c=N order by a limit 1;
select * from geek where c=N order by b limit 1;

  为了这两个查询模式，这两个索引是否都是必须的？为什么呢？

  主键 a，b 的聚簇索引组织顺序相当于 order by a,b ，也就是先按 a 排序，再按 b 排序，c 无序。索引 ca 的组织是先按 c 排序，再按 a 排序，同时记录主键 b（这个跟索引 c 的数据是一模一样的）。cb 的组织是先按 c 排序，在按 b 排序，同时记录主键。所以，结论是ca可以去掉，cb需要保留。

二、锁

  数据库锁设计的初衷是处理并发问题。作为多用户共享的资源，当出现并发访问的时候，数据库需要合理地控制资源的访问规则。而锁就是用来实现这些访问规则的重要数据结构。根据加锁的范围，MySQL里面的锁大致可以分成全局锁、表级锁和行锁三类。

1、全局锁

  全局锁就是对整个数据库实例加锁。MySQL 提供了一个加全局读锁的方法，命令是 Flush tables with read lock (FTWRL)。当你需要让整个库处于只读状态的时候，可以使用这个命令，之后其他线程的以下语句会被阻塞：数据更新语句（数据的增删改）、数据定义语句（包括建表、修改表结构等）和更新类事务的提交语句。

  全局锁的典型使用场景是，做全库逻辑备份。也就是把整库每个表都select出来存成文本。但是让整库都只读，听上去就很危险：

• 如果你在主库上备份，那么在备份期间都不能执行更新，业务基本上就得停摆；
• 如果你在从库上备份，那么备份期间从库不能执行主库同步过来的 binlog，会导致主从延迟。

  不加锁的话，备份系统备份的得到的库不是一个逻辑时间点，这个视图是逻辑不一致的。说到视图，在前面讲事务隔离的时候，其实是有一个方法能够拿到一致性视图的。就是在可重复读隔离级别下开启一个事务。

  官方自带的逻辑备份工具是 mysqldump。当 mysqldump 使用参数 –single-transaction 的时候，导数据之前就会启动一个事务，来确保拿到一致性视图。而由于 MVCC 的支持，这个过程中数据是可以正常更新的。single-transaction 方法只适用于所有的表使用事务引擎的库。如果有的表使用了不支持事务的引擎，那么备份就只能通过 FTWRL 方法。

  既然要全库只读，为什么不使用set global readonly=true的方式呢？确实readonly方式也可以让全库进入只读状态，但建议用 FTWRL 方式，主要有两个原因：

• 在有些系统中，readonly 的值会被用来做其他逻辑，比如：用来判断一个库是主库还是备库。因此，修改 global 变量的方式影响面更大，所有不建议使用。
• 在异常处理机制上有差异。如果执行 FTWRL 命令之后由于客户端发生异常断开，那么 MySQL 会自动释放这个全局锁，整个库回到可以正常更新的状态。而将整个库设置为 readonly 之后，如果客户端发生异常，则数据库就会一直保持 readonly 状态，这样会导致整个库长时间处于不可写状态，风险较高。

2、表级锁

  MySQL 里面表级别的锁有两种：一种是表锁，一种是元数据锁（meta data lock，MDL)。

  表锁的语法是 lock tables … read/write。与 FTWRL 类似，可以用 unlock tables 主动释放锁，也可以在客户端断开的时候自动释放。需要注意，lock tables 语法除了会限制别的线程的读写外，也限定了本线程接下来的操作对象。

  如果在某个线程A中执行 lock tables t1 read, t2 write; 这个语句，则其他线程写 t1、读写 t2 的语句都会被阻塞。同时，线程 A 在执行 unlock tables 之前，也只能执行读 t1、读写 t2 的操作。连写 t1 都不允许，自然也不能访问其他表。

  在还没有出现更细粒度的锁的时候，表锁是最常用的处理并发的方式。而对于InnoDB这种支持行锁的引擎，一般不使用 lock tables 命令来控制并发，毕竟锁住整个表的影响面还是太大。

  另一类表级的锁是 MDL（metadata lock)。MDL 不需要显式使用，在访问一个表的时候会被自动加上。MDL的作用是，保证读写的正确性。在 MySQL 5.5 版本中引入了 MDL，当对一个表做增删改查操作的时候，加 MDL 读锁；当要对表做结构变更操作的时候，加 MDL 写锁。

• 读锁之间不互斥，因此你可以有多个线程同时对一张表增删改查。
• 读写锁之间、写锁之间是互斥的，用来保证变更表结构操作的安全性。因此，如果有两个线程要同时给一个表加字段，其中一个要等另一个执行完才能开始执行。

  事务中的 MDL 锁，在语句执行开始时申请，但是语句结束后并不会马上释放，而会等到整个事务提交后再释放。

3、行锁

  MySQL 的行锁是在引擎层由各个引擎自己实现的。但并不是所有的引擎都支持行锁，比如 MyISAM 引擎就不支持行锁。

两阶段锁

  在下面的操作序列中，事务 B 的 update 语句执行时会是什么现象呢？假设字段 id 是表 t 的主键。

  实际上事务 B 的 update 语句会被阻塞，直到事务 A 执行 commit 之后，事务 B 才能继续执行。事务 A 持有的两个记录的行锁，都是在 commit 的时候才释放的。，在InnoDB事务中，行锁是在需要的时候才加上的，但并不是不需要了就立刻释放，而是要等到事务结束时才释放。这个就是两阶段锁协议。

  如果你的事务中需要锁多个行，要把最可能造成锁冲突、最可能影响并发度的锁尽量往后放。

  假设你负责实现一个电影票在线交易业务，顾客 A 要在影院 B 购买电影票。我们简化一点，这个业务需要涉及到以下操作：

1. 从顾客 A 账户余额中扣除电影票价；
2. 给影院 B 的账户余额增加这张电影票价；
3. 记录一条交易日志。

  完成这个操作，需要两条 update 和一条 insert 语句。为保证交易完整性，该如何安排语句顺序？根据两阶段锁协议，不论你怎样安排语句顺序，所有的操作需要的行锁都是在事务提交的时候才释放的。所以，如果把语句 2 安排在最后，比如：按照3、1、2这样的顺序，那么影院账户余额这一行的锁时间就最少。这就最大程度地减少了事务之间的锁等待，提升了并发度。

4、死锁和死锁检测

  当并发系统中不同线程出现循环资源依赖，涉及的线程都在等待别的线程释放资源时，就会导致这几个线程都进入无限等待的状态，称为死锁。用行锁举例：

  这时候，事务 A 在等待事务 B 释放 id=2 的行锁，而事务 B 在等待事务 A 释放 id=1 的行锁。 事务 A 和事务 B 在互相等待对方的资源释放，就是进入了死锁状态。当出现死锁以后，有两种策略：

（1）策略一

  直接进入等待，直到超时。这个超时时间可以通过参数 innodb_lock_wait_timeout 来设置。

  在 InnoDB 中，innodb_lock_wait_timeout 的默认值是 50s，意味着如果采用第一个策略，当出现死锁以后，第一个被锁住的线程要过 50s 才会超时退出，然后其他线程才有可能继续执行。对于在线服务来说，这个等待时间往往是无法接受的。但超时时间设置太短的话，会出现很多误伤。

（2）策略二

  发起死锁检测，发现死锁后，主动回滚死锁链条中的某一个事务，让其他事务得以继续执行。将参数 innodb_deadlock_detect 设置为 on，表示开启这个逻辑。

  正常情况下我们还是要采用第二种策略，即：主动死锁检测，而且 innodb_deadlock_detect 的默认值本身就是 on。主动死锁检测在发生死锁的时候，是能够快速发现并进行处理的，但是它也是有额外负担的。每当一个事务被锁的时候，就要看看它所依赖的线程有没有被别人锁住，如此循环，最后判断是否出现了循环等待，也就是死锁。

如果所有事务都要更新同一行的场景呢？

  每个新来的被堵住的线程，都要判断会不会由于自己的加入导致了死锁，这是一个时间复杂度是 O(n) 的操作。假设有 1000 个并发线程要同时更新同一行，那么死锁检测操作就是 100万 这个量级的。虽然最终检测的结果是没有死锁，但是这期间要消耗大量的 CPU 资源。因此，你就会看到 CPU 利用率很高，但是每秒却执行不了几个事务。

  怎么解决由这种热点行更新导致的性能问题呢？

  如果你能确保这个业务一定不会出现死锁，可以临时把死锁检测关掉。业务设计的时候一般不会把死锁当做一个严重错误，毕竟出现死锁了，就回滚，然后通过业务重试一般就没问题了，这是业务无损的。而关掉死锁检测意味着可能会出现大量的超时，这是业务有损的。

  控制并发度要做在数据库服务端。如果你有中间件，可以考虑在中间件实现；对于相同行的更新，在进入引擎之前排队。这样在 InnoDB 内部就不会有大量的死锁检测工作了。

如果你要删除一个表里面的前10000行数据，有以下三种方法可以做到：

• 第一种，直接执行 delete from T limit 10000;
• 第二种，在一个连接中循环执行20次 delete from T limit 500;
• 第三种，在20个连接中同时执行delete from T limit 500。

  第二种方式是相对较好的

• 第一种方式，单个语句占用时间长，锁的时间也比较长；而且大事务还会导致主从延迟。
• 第三种方式：会人为造成锁冲突。

5、事务到底是隔离的还是不隔离的

  可重复读隔离级别，事务 T 启动的时候会创建一个视图 read-view，之后事务 T 执行期间，即使有其他事务修改了数据，事务 T 看到的仍然跟在启动时看到的一样。一个事务要更新一行，如果刚好有另外一个事务拥有这一行的行锁，它又不能这么超然了，会被锁住，进入等待状态。问题是，既然进入了等待状态，那么等到这个事务自己获取到行锁要更新数据的时候，它读到的值又是什么呢？（更新后的值）

  在 MySQL 里，有两个“视图”的概念：

• 一个是 view。它是一个用查询语句定义的虚拟表，在调用的时候执行查询语句并生成结果。创建视图的语法是 create view ... ，而它的查询方法与表一样。
• 另一个是 InnoDB 在实现 MVCC 时用到的一致性读视图，即 consistent read view，用于支持RC（Read Committed，读提交）和 RR（Repeatable Read，可重复读）隔离级别的实现。

  它没有物理结构，作用是事务执行期间用来定义“我能看到什么数据”。

“快照”在MVCC里是怎么工作的？

  在可重复读隔离级别下，事务在启动的时候就“拍了个快照”。注意，这个快照是基于整库的。实际上，我们并不需要拷贝出整个库。我们先来看看这个快照是怎么实现的。

  InnoDB 里面每个事务有一个唯一的事务 ID，叫作 transaction id。它是在事务开始的时候向 InnoDB 的事务系统申请的，是按申请顺序严格递增的。而每行数据也都是有多个版本的。每次事务更新数据的时候，都会生成一个新的数据版本，并且把 transaction id 赋值给这个数据版本的事务 ID，记为 row trx_id。同时，旧的数据版本要保留，并且在新的数据版本中，能够有信息可以直接拿到它。也就是说，数据表中的一行记录，其实可能有多个版本(row)，每个版本有自己的 row trx_id。多个版本(row)就是通过 undo log（回滚日志）来实现的。

事务的可重复读的能力是怎么实现的？

  按照可重复读的定义，一个事务启动的时候，能够看到所有已经提交的事务结果。但是之后，这个事务执行期间，其他事务的更新对它不可见。

  在实现上， InnoDB 为每个事务构造了一个数组，用来保存这个事务启动瞬间，当前正在“活跃”的所有事务 ID。“活跃”指的就是，启动了但还没提交。数组里面事务 ID 的最小值记为低水位，当前系统里面已经创建过的事务 ID 的最大值加 1 记为高水位。这个视图数组和高水位，就组成了当前事务的一致性视图（read-view）。而数据版本的可见性规则，就是基于数据的 row trx_id 和这个一致性视图的对比结果得到的。

  这样，对于当前事务的启动瞬间来说，一个数据版本的 row trx_id，有以下几种可能：

• 如果落在绿色部分，表示这个版本是已提交的事务或者是当前事务自己生成的，这个数据是可见的；
• 如果落在红色部分，表示这个版本是由将来启动的事务生成的，是肯定不可见的；
• 如果落在黄色部分，那就包括两种情况
  • 若 row trx_id 在数组中，表示这个版本是由还没提交的事务生成的，不可见；
  • 若 row trx_id 不在数组中，表示这个版本是已经提交了的事务生成的，可见。

InnoDB利用了“所有数据都有多个版本”的这个特性，实现了“秒级创建快照”的能力。

  可重复读的核心就是一致性读（consistent read）；而事务更新数据的时候，只能用当前读。如果当前的记录的行锁被其他事务占用的话，就需要进入锁等待。

  而读提交的逻辑和可重复读的逻辑类似，它们最主要的区别是：

• 在可重复读隔离级别下，只需要在事务开始的时候创建一致性视图，之后事务里的其他查询都共用这个一致性视图；
• 在读提交隔离级别下，每一个语句执行前都会重新算出一个新的视图。

  InnoDB 的行数据有多个版本，每个数据版本有自己的 row trx_id，每个事务或者语句有自己的一致性视图。普通查询语句是一致性读，一致性读会根据 row trx_id 和一致性视图确定数据版本的可见性。

• 对于可重复读，查询只承认在事务启动前就已经提交完成的数据；虽然查询不到已经提交完成的数据，但是在使用修改语句的判断中，还是根据已经提交完成的数据来进行判断的。（对于未提交的数据，进行同行操作，会进行行锁等待）
• 对于读提交，查询只承认在语句启动前就已经提交完成的数据；
• 而当前读，总是读取已经提交完成的最新版本。