Table of Contents generated with DocToc (opens new window)

• 思维导图
• 索引结构相关
  • 树的种类
  • MySQL索引要解决的问题
  • AVL树(平衡二叉树的一种)
  • B-Tree(Balance Tree)
  • 介绍
    • 特点(m阶的B-Tree)
    • 3阶B-Tree示意图
  • B+Tree
    • 特点
    • 查找过程
  • B树和B+树的区别
  • B+树比B树更适合应用于数据库索引
• 事务相关
  • ACID原则
  • 隔离级别
  • 隔离级别导致的问题
  • 如何解决隔离级别导致的各个问题
  • MVCC机制
    • 介绍
    • 当前读
    • 快照读
    • 三者关系
    • undo log
    • ReadView
    • 不同隔离级别生成ReadView的策略
    • 查询时的步骤
  • 各种锁
    • 属性锁
      • 共享锁(Share Lock)
      • 排它锁(eXclusive Lock)
    • 粒度锁
      • 表锁
      • 行锁(Record Lock)
      • 记录锁
      • 间隙锁(Gap Lock)
      • 临键锁(Next-Key Lock)
    • 状态锁
      • 意向锁
      • 意向共享锁
      • 意向排它锁
      • 举例：
• 索引类别原理相关
  • 索引类别
    • 哈希索引
    • 有序数组
    • B+树索引(InnoDB)
    • 联合索引
    • 最左前缀原则
    • 覆盖索引
    • 索引下推

---

思维导图

索引结构相关

树的种类

按有序性

无序树：树中任意结点的子节点之间没有顺序关系

有序树：树中任意结点的子节点之间有顺序关系

按结点包含子树个数

• 二叉树：每个节点最多含有两个子树的树称为二叉树;

• 满二叉树：除最后一层的节点外，其他所有结点都有两个子节点的二叉树

• 完全二叉树：除去最后一层，为满二叉树；最后一个层的结点，优先从左到右(连续集中在左边)

• 霍夫曼树：带权路径最短的二叉树。

• 红黑树：红黑树是一颗特殊的二叉查找树，每个节点都是黑色或者红色，根节点、叶子节点是黑色。如果一个节点是红色的，则它的子节点必须是黑色的。

• 二叉查找树：首先它是一颗二叉树，若左子树不空，则左子树上所有结点的值均小于它的根结点的值;若右子树不空，则右子树上所有结点的值均大于它的根结点的值;左、右子树也分别为二叉排序树;

  最好情况下查找效率为O(logN)，但是当二叉树只向一边堆积形成一条链表时，效率就是O(N)了。所以有了AVL树

• 平衡二叉树(AVL)：可以是空树；不是空树的时候，它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

MySQL索引要解决的问题

减小耗时更多的磁盘IO次数，用高速的内存查找去替换

AVL树(平衡二叉树的一种)

我们对二叉查找树做个限制，限制必须满足任何节点的两个子树的最大差为 1，也是AVL 树的定义，这样我们的查找效率就有了一定的保障。

AVL 树 是一种自平衡二叉查找树(self-balancing binary search tree)。

当然，维护AVL 树也是需要一定开销的，即当树插入/更新/删除新的数据时假设破坏了树的平衡性，那么需要通过左旋和右旋来维护树的平衡。

当数据量很多时，同样也会出现二叉树过高的情况。

我们知道AVL 树的查找效率为 O(logN)，也就是说，当树过高时，查找效率会下降。

AVL树不适合作索引

另外由于我们的索引文件并不小，所以是存储在磁盘上的。

文件系统需要从磁盘读取数据时，一般以页为单位进行读取，假设一个页内的数据过少， 那么操作系统就需要读取更多的页，涉及磁盘随机 I/O 访问的次数就更多。

将数据从磁盘读入内存涉及随机 I/O 的访问，是数据库里面成本最高的操作之一。

因而这种树高会随数据量增多急剧增加，每次更新数据又需要通过左旋和右旋维护平衡的二叉树，不太适合用于存储在磁盘上的索引文件

注意，我们说的平衡二叉树结构，指的是逻辑结构上的平衡二叉树，其物理实现是数组。然后由于在逻辑结构上相近的节点在物理结构上可能会差很远。因此，每次读取的磁盘页的数据中有许多是用不上的。因此，查找过程中要进行许多次的磁盘读取操作。

而适合作为索引的结构应该是尽可能少的执行磁盘IO操作，因为执行磁盘IO操作非常的耗时。因此，平衡二叉树并不适合作为索引结构。

B-Tree(Balance Tree)

介绍

B树属于多叉树，又名平衡多路查找树。它能够保证数据有序，还保证了在查找、插入、删除等操作时性能都能保持在O(logN)，为大块数据的读写操作做了优化。一般描述一颗B树时需要指定它的阶数，阶数表示一个结点最多可以有多少个孩子结点，当阶数为2时，即常见的二叉搜索树。

同二叉搜索树类似，B树的每个结点储存了多个key和子树(指向下一磁盘块的地址指针)，子树与key按顺序排列

B树在保留二叉树预划分范围从而提升查询效率的思想的前提下，做了以下优化：

二叉树变成 m 叉树，这个 m 的大小可以根据单个页的大小做对应调整，从而使得一个页可以存储更多的数据，从磁盘中读取一个页可以读到的数据就更多，随机 IO 次数变少，大大提升效率。

但是我们看到，我们只能通过中序遍历查询全表，当进行范围查询时，可能会需要中序回溯

特点(m阶的B-Tree)

1. 根节点最少可以只有一个关键字
2. 除根节点外，每个节点最多有m-1个关键字，最少有Math.ceil(m/2)-1个关键字 TIP：Math.ceil()表示向上取整，例如ceil(2.5)=3
3. 每个节点中的关键字都按照从小到大的顺序排列，每个关键字左指针指向的子树中的所有关键字都小于它，而右指针指向的子树中的所有关键字都大于它
4. 所有叶子节点的都位于同一层，或者说根节点到每个叶子节点的长度都相同

3阶B-Tree示意图

1. x.n = 2 有俩个关键字 分别为 x.key1 = 8 x.key2 = 12 且 8<12
2. 含有3个指向它孩子的指针P1 P2 P3
3. 关键字x.key1=8 它的左边指针P1 对 子树 3 5 分割 满足 3和5都小于8 关键字x.key1=8 它的右边指针P2 对 子树 9 10 分割 满足 9和10都大于8（同为12的左指针） 关键字x.key2=12 它的右边指针P3 对 子树 13 15 分割 满足 13和15都大于12

在实际应用中的B树的阶数m都非常大（通常大于100），所以即使存储大量的数据，B树的高度仍然比较小。每个结点中存储了关键字（key）和关键字对应的数据（data），以及孩子结点的指针。我们将一个key和其对应的data称为一个记录。此时B树中的key就表示键，而data表示了这个键对应的条目在硬盘上的逻辑地址。

B+Tree

特点

B+树在B树的基础上加了以下优化：

1.叶子结点增加了指针进行连接，即叶子结点间形成了链表；

2.非叶子结点只存关键字 key，不再存储数据，只在叶子结点存储数据；

说明：叶子之间用双向链表连接比单向链表连接多出的好处是通过链表中任一结点都可以通过往前或者往后遍历找到链表中指定的其他结点。

这样做的好处是：

范围查询时可以通过访问叶子节点的链表进行有序遍历，而不再需要中序回溯访问结点。

非叶子结点只存储关键字key，一方面这种结构相当于划分出了更多的范围，加快了查询速度，另一方面相当于单个索引值大小变小，同一个页可以存储更多的关键字，读取单个页就可以得到更多的关键字，可检索的范围变大了，相对 IO 读写次数就降低了。

查找过程

通过主键id查询的过程

按主键id=15查询，首先判断到15在1-18之间，所以来到第二层的(1,16,12)数据块继续查找，二分判断到15>12，所以来到这个结点的最右子节点数据块(12,15,17)查找，它是个链式结构，最后找到id为15的数据，经过三次I/O操作。

通过非主键(辅助索引)查询

会先检索辅助索引构成的B+Tree的商品编号，找到对应的叶子结点，获取主键值，然后再通过主键索引中的B+Tree查询到对应的叶子结点，获取整行数据。这个过程叫回表

B树和B+树的区别

区别

1. B 树非叶子结点和叶子结点都存储数据,因此查询数据时，时间复杂度最好为 O(1),最坏为 O(log n)。

   而B+ 树只在叶子结点存储数据，非叶子结点存储关键字，且不同非叶子结点的关键字可能重复，因此查询数据时，时间复杂度固定为 O(log n)。

2. B+ 树叶子结点之间用链表相互连接，因而只需扫描叶子结点的链表就可以完成一次遍历操作，B树只能通过中序遍历。

B+树比B树更适合应用于数据库索引

Why?

1. B+ 树更加适应磁盘的特性，相比 B 树减少了 I/O 读写的次数。由于索引文件很大因此索引文件存储在磁盘上，B+ 树的非叶子结点只存关键字不存数据，因而单个页可以存储更多的关键字，即一次性读入内存的需要查找的关键字也就越多，磁盘的随机 I/O 读取次数相对就减少了。
2. B+ 树的查询效率相比B树更加稳定，由于数据只存在在叶子结点上，所以查找效率固定为 O(log n)。
3. B+ 树叶子结点之间用双链表有序连接，所以扫描全部数据只需扫描一遍叶子结点，利于扫库和范围查询；B 树由于非叶子结点也存数据，所以只能通过中序遍历按序来扫。也就是说，对于范围查询和有序遍历而言，B+ 树的效率更高。

事务相关

ACID原则

笔记

• 原子性：事务满足原子性，所有操作要么都执行成功，要么都不执行
• 一致性：事物开始和完成时，数据都必须保持一致状。比如：如果从A账户转账到B账户，不可能A账户扣了钱，而B账户没有加钱
• 隔离性：并发环境中，各事务之间的执行不被其它事务干扰，即不同的并发事务操作相同的数据时，每个事务都有自己的完整数据空间
• 持久性：事务对数据库的操作是写入磁盘，哪怕宕机重新运行也是事务结束后的状态

隔离级别

MySQL的InnoDB引擎的默认隔离级别是 可重复读

笔记

• 读未提交：其它事务可以看到别的事务未提交但已修改的数据
• 读已提交：其它事务只能看到别的事务已提交的数据
• 可重复读：一个事务在执行过程中看到的数据，总是和这个事务启动时看到的数据一致，未提交变更对其他事务也是不可见的。
• 串行化：让所有事务排队执行，解决了所有问题，但是也不能并发了

隔离级别导致的问题

笔记

1. 脏读：主要是读未提交这个级别导致的，可以读到别的事务的未提交的数据
2. 幻读：一个事务执行两次查询，发现两次结果不同(倾向于别的事务新增了数据)
3. 不可重复读：一个事务执行两次查询，发现两次结果不同(倾向于同一条数据被修改)

事务隔离级别	脏读	不可重复读	幻读
读未提交（read-uncommitted）	是	是	是
读已提交（read-committed）	否	是	是
可重复读（repeatable-read）	否	否	是
串行化（serializable）	否	否	否

如何解决隔离级别导致的各个问题

注意

1. 在可重复读的隔离级别下，innodb解决了不可重复读问题，只能读取提交事务的数据，在MySQL数据库中读取的是事务版本号比自己小的数据
2. 读已提交的隔离级别下，innodb解决了脏读
3. 可重复读级别下，运用间隙锁，可以解决幻读问题

MVCC机制

介绍

​ MVCC（Multi-Version Concurrency Control）多版本并发控制，是用来在数据库中控制并发的方法，实现对数据库的并发访问用的。在MySQL中，MVCC只在读已提交（Read Committed）和可重复读（Repeatable Read） 两个事务级别下有效。其是通过undo log日志中的版本链和ReadView一致性视图来实现的。MVCC就是在多个事务同时存在时，SELECT语句找寻到具体是版本链上的哪个版本，然后在找到的版本上返回其中所记录的数据的过程。

首先需要知道的是，在MySQL中，会默认为我们的表后面添加三个隐藏字段：

• DB_ROW_ID：行ID，MySQL的B+树索引特性要求每个表必须要有一个主键。如果没有设置的话，会自动寻找第一个不包含NULL的唯一索引列作为主键。如果还是找不到，就会在这个DB_ROW_ID上自动生成一个唯一值，以此来当作主键（该列和MVCC的关系不大）；
• DB_TRX_ID：事务ID，记录的是当前事务在做INSERT或UPDATE语句操作时的事务ID（DELETE语句被当做是UPDATE语句的特殊情况，后面会进行说明）；
• DB_ROLL_PTR：回滚指针，通过它可以将不同的版本串联起来，形成版本链。相当于链表的next指针。每次对哪条聚簇索引记录有修改的时候，都会把老版本写入undo日志中。这个DB_ROLL_PTR 就是存了一个指针，它指向这条聚簇索引记录的上一个版本的位置，通过它来获得上一个版本的记录信息。(注意插入操作的undo日志没有这个属性，因为它没有老版本)

（注意，添加的隐藏字段并不是很多人认为的创建时间和删除时间，同时在MySQL中MVCC的实现也不是通过什么快照来实现的。之所以有这种说法可能是源自于《高性能MySQL》一书中对MySQL中MVCC的错误结论，然后就人云亦云传开了（注意，这里一直强调的是MySQL中MVCC的实现，是因为在不同的数据库中可能会有不同的实现），所以说看源码和看官方文档才是最权威的解释）

MVCC最大的优势：读不加锁，读写不冲突。在读多写少的场景下极大的增加了系统的并发性能

总结

MVCC指的就是在使用READ COMMITTD 、REPEATABLE READ 这两种隔离级别的事务在执行普通的SEELCT 操作时访问记录的版本链的过程，这样子可以使不同事务的读-写、写-读操作并发执行，从而提升系统性能。

当前读

说明

像select lock in share mode(共享锁)；select for update、insert、update、delete(这些都是加上排它锁)这些操作都是一种当前读，因为读取的是记录的最新版本，读取时还要保证其他并发事务不能修改当前记录，会对读取的记录进行加锁

快照读

说明

像不加锁的select操作就是快照读，即不加锁的非阻塞读；快照读的前提是隔离级别不是串行级别，因为串行级别下的快照读会退化为当前读；之所以出现快照读的情况，是基于提高并发性能的考虑。快照读的实现就是基于多版本并发控制(MVCC)，可以认为MVCC是行锁的一个变种，但它在很多情况下，避免了加锁操作，降低了开销；既然是基于多版本，即快照读可能读到的并不一定是数据的最新版本，有可能是之前的历史版本

三者关系

1. MVCC 多版本并发控制是(维持一个数据的多个版本，使得读写操作没有冲突) 的概念，只是一个抽象概念，并非实现
2. 因为 MVCC 只是一个抽象概念，要实现这么一个概念，MySQL 就需要提供具体的功能去实现它，(快照读就是 MySQL 实现 MVCC 理想模型的其中一个非阻塞读功能)。而相对而言，当前读就是悲观锁的具体功能实现
3. 要说的再细致一些，快照读本身也是一个抽象概念，再深入研究。MVCC 模型在 MySQL 中的具体实现则是由 3 个隐式字段，undo 日志 ，Read View 等去完成的

undo log

undo log：回滚日志，保存了事务发生之前的数据的一个版本，不同事务或者相同事务的对同一记录的修改，会导致该记录的undo log成为一条记录版本的链表，undo log 的链首就是最新的旧记录，链尾就是最早的旧记录

作用：

1. 可以用于回滚
2. 同时可以提供多版本并发控制下的读（MVCC），也即非锁定读。
3. 事务开始之前，将当前事务版本生成 undo log，undo log 也会产生 redo log 来保证 undo log 的可靠性。
4. 当事务提交之后，undo log 并不能立马被删除，而是放入待清理的链表。
5. 由 purge 线程判断是否有其它事务在使用 undo 段中表的上一个事务之前的版本信息，从而决定是否可以清理 undo log 的日志空间。

ReadView

概念

​ Read View 就是事务进行快照读操作的时候生产的读视图 (Read View)，在该事务执行的快照读的那一刻，会生成数据库系统当前的一个快照，记录并维护系统当前活跃事务的 ID (当每个事务开启时，都会被分配一个 ID , 这个 ID 是递增的，所以最新的事务，ID 值越大)

​ 所以我们知道 Read View 主要是用来做可见性判断的, 即当我们某个事务执行快照读的时候，对该记录创建一个 Read View 读视图，把它比作条件用来判断当前事务能够看到哪个版本的数据，既可能是当前最新的数据，也有可能是该行记录的undo log里面的某个版本的数据。

​ ReadView一致性视图主要是由两部分组成：所有未提交事务的ID数组和已经创建的最大事务ID组成（实际上ReadView还有其他的字段，但不影响这里对MVCC的讲解）。比如：[100,200],300。事务100和200是当前未提交的事务，而事务300是当前创建的最大事务（已经提交了）。

Read View遵循一个可见性算法，主要是将要被修改的数据的最新记录中的 DB_TRX_ID（即当前事务 ID）取出来，与系统当前其他活跃事务的 ID 去对比（由 Read View 维护），如果 DB_TRX_ID 跟 Read View 的属性做了某些比较，不符合可见性，那就通过 DB_ROLL_PTR 回滚指针去取出 Undo Log 中的 DB_TRX_ID 再比较，即遍历链表的 DB_TRX_ID（从链首到链尾，即从最近的一次修改查起），直到找到满足特定条件的 DB_TRX_ID , 那么这个 DB_TRX_ID 所在的旧记录就是当前事务能看见的最新老版本

不同隔离级别生成ReadView的策略

当执行SELECT语句的时候会创建ReadView，但是在读取已提交和可重复读两个事务级别下，生成ReadView的策略是不一样的：

1. 读取已提交级别是每执行一次SELECT语句就会重新生成一份ReadView，因此每次查询前都可以获得当前已提交事务的数据和自己修改的最新数据
2. 而可重复读级别是只会在事务第一次SELECT语句执行的时候生成一份，后续的SELECT语句会沿用之前生成的ReadView（即使后面有更新语句的话，也会继续沿用，直到事务结束）

查询时的步骤

笔记

因为ReadView维护了当前正在活跃的未提交的事务的id数组、未提交事务id数组中的最小的id：min_id(在这个id之前的事务，都是已提交了的)、已创建的最大的事务id：max_id。

1. 当前事务去查询的是，如果查询的那条记录的被最近的一次被操作的事务满足id<min_id，或者id等于当前执行查询的事务的id，证明该条记录是早已提交的(或是当前事务自己修改的)，所以在读已提交和可重复读的隔离级别中对于当前事务是可见的；
2. 如果最近一次被操作的事务id满足min_id<=id<=max_id，就要看当前未提交的事务id数组里面有没有这个最近一次操作的事务id，如果有，证明该版本的记录操作未提交，所以对当前这个执行查询的事务是不可见的；如果没有在数组中，表示查到的这次记录操作已经提交了，对当前这个执行查询的事务是可见的。
3. 如果最近一次被操作的事务id满足id>max_id，证明这次操作由将来启动(此时未启动)的事务执行并提交的，所以对当前这个执行查询的事务是不可见的。
4. 最后，还要确保满足以上要求的可访问版本的数据的delete_flag不为true，否则查询到的就会是删除的数据。
5. 以上四步执行完后，如果结果是不可见，那么就通过DB_ROLL_PTR回滚指针继续查询undo log里这条记录的版本链中的下一个版本并重复以上步骤(因为一开始肯定是查询的最近版本，就是链表头结点)，直到找到可见的记录或者将版本链查询完。

各种锁

属性锁

共享锁(Share Lock)

共享锁又称读锁，简称S锁。当一个事务对数据加上读锁之后，其他事务只能对该数据加读锁，而无法对数据加写锁，要直到所有读锁释放之后其他事务才能对其加写锁。加了共享锁之后，无法再加排它锁，这就可以避免读取数据时数据被其他事务修改，从而导致不可重复读问题

排它锁(eXclusive Lock)

排他锁又称写锁，简称X锁；当一个事务对数据加上写锁之后，其他事务将不能再为数据加任何锁，直到该锁释放之后，其他事务才能对数据进行加锁。加了排他锁之后，其它事务就无法再对加了锁的数据进行读取和修改，所以也就不会出现脏写和脏读的问题。

粒度锁

表锁

表锁是指上锁的时候锁住的是整个表，当下一个事务访问该表的时候，必须等前一个事务释放了锁才能进行对表进行访问；

特点： 粒度大，加锁简单，容易冲突

行锁(Record Lock)

行锁是对所有行级别锁的一个统称，比如下面说的记录锁、间隙锁、临键锁都是属于行锁， 行锁是指加锁的时候锁住的是表的某一行或多行记录，多个事务访问同一张表时，只有被锁住的记录不能访问，其他的记录可正常访问；

特点：粒度小，加锁比表锁麻烦，不容易冲突，相比表锁支持的并发要高

记录锁

记录锁属于行锁中的一种，记录锁的范围只是表中的某一条记录，记录锁是说事务在加锁后锁住的只是表的某一条记录

触发条件：精准条件命中，并且命中索引

记录锁的作用：加了记录锁之后数据可以避免数据在查询的时候被修改的重复读问题，也避免了在修改的事务未提交前被其他事务读取的脏读问题

记录锁是加在索引上的!

间隙锁(Gap Lock)

间隙锁属于行锁中的一种，间隙锁是在事务加锁后其锁住的是表记录的某一个区间，当表的相邻ID之间出现空隙则会形成一个区间，遵循左开右闭原则。

例如：

select * from user where id > 5 and id < 8
#这里id是主键索引，如果数据表中并没有5<id<8的数据，sql查不到记录，就会使用间隙锁将id满足查询的所有数据都锁起来，
#且不管id在这区间的是否存在数据，这样会使得如果没有数据，但是要插入一个id=6的数据，会被阻塞

间隙锁是加在索引之间的!

间隙锁作用：防止幻读问题。事务并发的时候，如果没有间隙锁，别的事务就能插入间隙之间的数据，造成幻读问题，比如上例中插入id=6的数据

临键锁(Next-Key Lock)

临键锁也属于行锁的一种，并且它是Innodb引擎的行锁默认方式(所以仅在默认隔离级别，可重复读RR中存在，如果改为读已提交RC，会失效)，总的来说它就是记录锁和间隙锁的组合。每个数据行上的非唯一索引列上都会存在一把临键锁，当某个事务持有该数据行的临键锁时，会锁住一段左开右闭区间的数据。

临键锁只与非唯一索引列有关，在唯一索引列（包括主键列）上不存在临键锁。

加锁规则：

笔记

1. 加锁的基本单位是 next-key lock，是前开后闭区间

2. 查找过程中访问到的对象才会加锁

3. 唯一索引上的等值查询，给唯一索引加锁的时候，next-key lock 升级为行锁，只锁定值的那一行数据

4. 普通索引上的等值查询，向右遍历时一直走到最后一个值不满足等值条件的时候，next-key lock 退化为间隙锁；

5. 唯一索引上的范围查询会访问到不满足条件的第一个值为止

结论：

注意

1. 当使用唯一索引，进行等值查询时，如果数据存在，则不产生间隙锁，而是记录锁
2. 当使用唯一索引，进行等值查询，如果数据不存在，则产生间隙锁，间隙是这个查询的数据左右第一个值构成的间隙，根据检索条件向下寻找最靠近检索条件的记录值A作为左区间，向上寻找最靠近检索条件的记录值B作为右区间，即锁定的间隙为（A，B] 左开右闭
3. 当使用唯一索引，进行范围查询，对于满足查询条件但不存在的数据产生间隙锁，如果查询存在的记录就会产生记录锁，加在一起形成了临键锁
4. 当使用普通索引，不管是锁住单条还是多条(等值还是范围)，都会产生间隙锁
5. 如果没有使用索引，不管是锁住单条还是多条记录，都会产生表锁

例如：

id	name	age
1	a	10
5	b	15
10	c	20
15	d	25

唯一索引情况：

#对唯一索引进行范围查询加锁
begin;
select * from user_info where id>2 and id<13 for update ;

1. 如果命中了数据，锁记录id=5、10的左右间隙：(1,5]、(5,10]，(10,15]
2. 如果没有命中数据，退化为间隙锁，锁id1的左边第一条与id2的右边第一条组成的左开右开区间

#对唯一索引进行等值查询加锁
begin;
select * from user_info where id=6 for update ;

1. 如果id=6的数据不存在，则会锁住6左边第一条数据和右边第一条数据组成的左开右开区间，即：(5,10)这个间隙

2. 如果id=6的数据存在，就是行锁，只锁id=6这一行数据

普通索引情况：

#对非唯一索引进行范围查询加锁(不论有没有查到)
begin;
select * from user_info where age>11 and age<14 for update ;

1. 命中了数据：命中数据被锁掉；每个命中数据的左右间隙(左开右闭，这个闭就是命中的数据)被锁掉
2. 没有命中数据：锁这个范围构成的间隙(左闭右开)->[11,14)

#在对非唯一索引进行锁操作时，InnoDB 会获取该记录行的 `临键锁` ，并同时获取该记录行下一个区间的`间隙锁`。
begin;
select * from user_info where age=14 for update ;

1. 不管age=xx的数据是否存在：都锁这个age所在的间隙，且左闭右开

总结

间隙锁作用于主键索引(或唯一索引)以及普通索引；而临键锁只作用于唯一索引；

两种索引在都被命中时，锁的都是命中数据的左右间隙(左开右闭，这个闭就是命中的数据)

临键锁的作用：结合记录锁和间隙锁的特性，避免了在范围查询时出现脏读、重复读、幻读问题。加了临键锁之后，在范围区间内数据不允许被修改和插入

状态锁

状态锁包括意向共享锁和意向排它锁，把他们区分为状态锁的一个核心逻辑，是因为这两个锁都是都是描述是否可以对某一个表进行加表锁的状态

意向锁

当一个事务试图对整个表进行加锁（共享锁或排它锁）之前，首先需要获得对应类型的意向锁（意向共享锁或意向共享锁）

意向共享锁

当一个事务试图对整个表进行加共享锁之前，首先需要获得这个表的意向共享锁

意向排它锁

当一个事务试图对整个表进行加排它锁之前，首先需要获得这个表的意向排它锁

举例：

update user set name = '李四' where id = 200;

线程1执行上述SQL后，对id=5的记录加锁了

update user set name = '张三'

这时候线程2想要执行上述SQL，要对全表进行修改，即需要对全表进行加锁，因为是加排它锁，所以要对表进行检查，看有没有被其他事务锁住，所以需要遍历每个索引结点，直到找到id=200的结点被锁住了，才停下，否则会全表扫描，过于耗费时间和损耗数据库性能。

所以就有了意向锁的概念：如果事务A加锁成功后就设置一个状态告诉别的事务，我加了个共享锁/排他锁，后面的事务就能够直接知道自己是否能够对表进行加锁，而不用去扫描全表判断表是否已被加锁。

索引类别原理相关

提示

索引对查询速度有至关重要的影响，理解索引也是进行数据库性能调优的起点，索引就是为了提高数据查询的效率。索引可以包含一个或多个列的值，如果索引包含多个列的值，则列的顺序也十分重要，因为MySQL只能高效地使用索引的最左前缀列

索引类别

哈希索引

概念

哈希表是一种以键-值（key-value）的方式存储数据的结构，我们只要输入待查找的值（即key），就可以找到其对应的值（即Value）。哈希的思路很简单，把值放在数组里，用一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置，即index = Hash(key)。如果出现哈希冲突，就采用拉链法解决(还有开放定址法：线性或左右平方跳跃)。

因为哈希表中存放的数据不是有序的，因此不适合做区间查询，适用于只有等值查询的场景

有序数组

概念

有序数组在等值查询和范围查询场景中的性能都非常优秀。用二分法就可以快速找到（时间复杂度为O(logN)）。但是如果要往中间插入一条数据，则必须挪动后面的所有记录，成本较高。因此，有序数组只适用于静态存储引擎，即数据表一旦建立后不再会修改

B+树索引(InnoDB)

简单的说，是因为使用B+树存储数据可以让一个查询尽量少的读磁盘，从而减少查询时磁盘I/O的时间。

在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。又因为前面我们提到的，InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的。每一个索引在 InnoDB 里面对应一棵 B+ 树。

假设，有这样一张表：该表主键为ID，且还有一个字段为k，并在k上有索引。

CREATE TABLE T( id int primary key,    k int not null,    index (k) )engine=InnoDB;

表中有5条记录，分别为R1~R5，(100,1)、(200,2)、(300,3)、(500,5)和(600,6)。则在InnoDB中的索引组织结构是这样的：

根据叶子结点的内容，索引类型分为主键索引和非主键索引。

• 主键索引的叶子结点存的是整条记录，主键索引也被称为聚簇索引（clustered index）。

• 非主键索引的叶子结点存的是主键的值，非主键索引也被称为二级索引（secondary index）/普通索引/辅助索引。

那么，基于主键索引和非主键索引的查询有什么区别？

• 如果语句是 select * from T where ID=500，即主键查询，则只需要搜索ID这棵树。

• 如果语句是 select * from T where k=5，即非主键索引查询，则需要先搜索k索引树，得到ID的值为500，再到ID索引树搜索一次。从非主键索引回到主键索引的过程称为回表。

也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。而从存储空间的角度讲，因为非主键索引树的叶结点存放的是主键的值，那么，应该考虑让主键的字段尽量短，这样非主键索引的叶子结点就越小，非主键索引占用的空间也就越小。一般情况下，建议创建一个自增主键，这样非主键索引占用的空间最小

联合索引

联合索引是指对表上的多个列进行索引。下面以一个例子进行说明。假设有下面这样一张表，有这样一个需求，我们需要查询某个用户的购物情况，并按照时间进行排序，取出某用户近几次的购物情况。（注：例子来源于《MySQL技术内幕》）

# 表
CREATE TABLE buylog(    userid int not null,    buy_date DATE )ENGINE=InnoDB; 
# 插入数据 
insert into buylog values(1, '2019-08-13'); insert into buylog values(2, '2019-08-14'); 
insert into buylog values(3, '2019-08-15'); insert into buylog values(1, '2019-08-11'); 
insert into buylog values(3, '2019-08-10'); insert into buylog values(1, '2019-08-12'); 
# 添加索引 
alter table buylog add index(userid); 
alter table buylog add index(userid, buy_date); 
# （或用key关键字也一样的） 
alter table buylog add key(userid); 
alter table buylog add key(userid, buy_date); 

上面的代码建立了两个索引，两个索引都包含了userid字段。

如果只对于userid进行查询，如：

select * from buylog where userid=2;

通过explain查看该语句的执行情况如下：

可以看到，possible_keys有两个索引可选，一个是useridandbuydate_index(两个字段的联合索引)和userid_index(userid的单索引)，MySQL最终选择的是联合索引，貌似是版本优化了，走的联合索引，实际上原来是走的单值索引userid_index

接着要查询userid=1的最近两次的购买记录，执行的情况：

EXPLAIN select * from buylog where userid=1 order by buy_date desc limit 2;

这一次查询优化器选择的索引(userid, buy_date)联合索引，因为因为在这个联合索引中，记录已经分别根据userid和buy_date排好序了，利用这个索引则可以直接取出相应的数据而无需再对buy_date额外做一次排序操作了

如果强制使用userid索引，则它的执行计划如下：

从Extra字段可以看出，该语句的执行需要使用fliesort，也就是需要一次额外的排序操作才能完成查询。显然，这个排序就是对buy_date字段的排序，因为这里仅使用了userid索引，该索引未对buy_date进行排序

最左前缀原则

对于有很多字段的一张表，查询的方式是多样的，难道要为了每一种可能的查询都定义索引吗？这样岂不是很浪费空间，毕竟建索引也是需要一些空间的。事实上，B+ 树这种索引结构，可以利用索引的“最左前缀”原则来定位记录，避免重复定义索引。

提示

假设建立了一个联合索引(name,age)，可以看到，索引项是按照索引定义里面出现的字段顺序排序的，先根据名字排序，名字相同的就根据年龄排序。

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

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

可以看到，不只是索引的全部定义，只要满足最左前缀，就可以利用索引来加速检索。这个最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。

因此，基于最左前缀原则，我们在定义联合索引的时候，考虑如何安排索引内的字段顺序就至关重要了！评估的标准就是索引的复用能力，比如，当已经有了(a,b)字段的索引，一般就不需要再单独在a上建立索引了。这里其实可以映射到上面联合索引的例子，为什么第一条SQL只查userid的时候用的还是联合索引

注意

假设建立的索引顺序是(a,b,c)，查询时如果和abc顺序一样，哪个位置出现了比较查询，索引就在那里失效；

例如：

1. where a=1 and b>2 and c=3;
   

   这个查询语句在b处失效，只会用到a、b两个字段索引

2. 而如果是(a,c,b)索引

   where a=1 and b>2 and c=3;
   

   这条语句三个字段都生效，因为MySQL执行时优化器会自动优化成满足最左匹配原则的执行顺序

引申

对于联合索引(a,b,c)，查询语句SELECT * FROM test WHERE b=2;是否能够触发索引？ 大多数人都会说NO，实际上却是YES。 原因：

EXPLAIN SELECT * FROM test WHERE b=2;
EXPLAIN SELECT * FROM test WHERE a=1;

观察上述两个explain结果中的type字段。查询中分别是：

1. type: index
2. type: ref

index：这种类型表示MySQL会对整个该索引进行扫描。要想用到这种类型的索引，对这个索引并无特别要求，只要是索引，或者某个联合索引的一部分，MySQL都可能会采用index类型的方式扫描。但是呢，缺点是效率不高，MySQL会从索引中的第一个数据一个个的查找到最后一个数据，直到找到符合判断条件的某个索引。所以，上述语句会触发索引。

ref：这种类型表示MySQL会根据特定的算法快速查找到某个符合条件的索引，而不是会对索引中每一个数据都进行一一的扫描判断，也就是所谓我们平常理解的使用索引查询会更快的取出数据。而要想实现这种查找，索引却是有要求的，要实现这种能快速查找的算法，索引就要满足特定的数据结构。简单说，也就是查询时的索引字段的顺序必须是满足最左匹配原则的，才能实现这种类型的查找，利用到索引。

覆盖索引

还是用这张表进行说明

CREATE TABLE T( id int primary key,    k int not null,    index (k) )engine=InnoDB;

如果执行的语句是：

select * from T where k between 3 and 5

则这条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，不满足条件，循环结束。

在这个过程中，回到主键索引树根据ID去查询的过程，称为回表。在这个例子中，由于查询的结果是所有字段，所需要的数据只有主键上才有，所以不得不回表。但如果执行的语句是下面这样的，注意！这里查询的结果只是“ID”（恰好是主键），而不是所有字段了。

select ID from T where k between 3 and 5;

因为k字段的索引是辅助索引(二级索引)，其根节点上存放的是k字段值和主键值，所以主键ID的值已经在字段k的索引树上了，因此可以直接提供查询结果，不会触发回表，也就是说，在这个查询里，索引k已经"覆盖了"我们的查询需求，故称为覆盖索引

除了上面这种情况，针对某些统计问题时，覆盖索引也能发挥用处。还是以上面的例子，执行如下语句来统计表的记录总数（在此我们假设这张表数据量特别特别大，需要多次磁盘IO）：

select count(*) from T;

如果没有对字段k设置索引，那么只能是通过聚簇索引来计算；如果对字段k设置了索引，那么，由于聚簇索引的叶结点存放的是整行记录的所有信息，而辅助索引的叶结点只存放主键，两者相比，对于一页内存，显然辅助索引能够存放的节点更多，意味着辅助索引可以减少IO次数，从而更快的计算出count(*)的值。

测试一下：用buylog表，先把userid的单列索引删掉，联合索引也删掉，不然会走联合索引，然后执行SQL

EXPLAIN select count(*) from buylog;

可以看到，优化器选择主键聚簇索引进行操作

把索引加上后：

可以看到，优化器选择了单值辅助索引进行操作。如果单值没有，则使用联合索引

可见，如果建立了辅助索引，在有些场景下，优化器会自动使用辅助索引从而提升查询效率

总结

覆盖索引就是从辅助索引中就能直接得到查询结果，而不需要回表到聚簇索引中进行再次查询，所以可以减少搜索次数（不需要从辅助索引树回表到聚簇索引树），或者说减少IO操作（通过辅助索引树可以一次性从磁盘载入更多节点），从而提升性能

索引下推

什么是索引下推（Index Condition Pushdown，ICP）呢？

假设有这么个需求，查询表中“名字第一个字是张，性别男，年龄为10岁的所有记录”。那么，查询语句是这么写的：

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

根据前面说的“最左前缀原则”，该语句在搜索索引树的时候，只能匹配到名字第一个字是‘张’的记录（即记录ID3），接下来是怎么处理的呢？当然就是从ID3开始，逐个回表，到主键索引上找出相应的记录，再比对age和ismale这两个字段的值是否符合。

但是！MySQL 5.6引入了索引下推优化，可以在索引遍历过程中，对索引中包含的字段先做判断，过滤掉不符合条件的记录，减少回表次数

下面分别展示这两种情况：

图1：没有索引下推的时候

图2：有索引下推的时候

注意

图 1 中，在 (name,age) 索引里面特意去掉了 age 的值，这个过程 InnoDB 并不会去看 age 的值，只是按顺序把"name 第一个字是'张'"的记录一条条取出来回表。因此，需要回表 4 次。

图 2 跟图 1 的区别是，InnoDB 在 (name,age) 索引内部就判断了 age 是否等于 10，对于不等于 10 的记录，直接判断并跳过。在我们的这个例子中，只需要对 ID4、ID5 这两条记录回表取数据判断，就只需要回表 2 次。

总结

如果没有索引下推优化（或称ICP优化），当进行索引查询时，首先根据索引来查找记录，然后再根据where条件来过滤记录；在支持ICP优化后，MySQL会在取出索引的同时，判断是否可以进行where条件过滤，也就是说提前执行where的部分过滤操作，在某些场景下，可以大大减少回表次数，从而提升整体性能