窥探MySQL索引与事务

一、MySQL索引

1.1、概念

索引是一种特殊的文件，包含着对数据表里所有记录的引用指针。可以对表中的一列或多列创建索引， 并指定索引的类型，各类索引有各自的数据结构实现。

索引是关系数据库中对某一列或多个列的值进行预排序的数据结构，在 MySQL 中也被称为 Key。通过使用索引，可以让数据库系统不必扫描整个表，而是直接定位到符合条件的记录，这样就大大加快了查询速度。

注意事项：有序性是因为一切二分法查找法都要求数据已经是排好顺序的。如果把索引看做 key（虽然 key 数据也是来自于表单中一行记录的某些字段值），那么 value 在 MyISAM 中就是记录的在存储文件中的地址，而在 InnoDB 中 value 直接就是对应的一行数据。

假设我们有一张数据表 workers(员工表)，该表有三个字段（列）,分别是name、age 和address。假设表works有上万行数据，现在需要从这个表中查找出所有名字是‘ZhangSan’的雇员信息，你会快速的写出SQL语句：

select name,age,address from workers where name='ZhangSan'

如果数据库还没有索引这个东西，一旦我们运行这个SQL查询，查找名字为ZhangSan的雇员的过程中，究竟会发生什么？数据库不得不在workes表中的每一行查找并确定雇员的名字（name）是否为‘ZhangSan’。

由于我们想要得到每一个名字为ZhangSan的雇员信息，在查询到第一个符合条件的行后，不能停止查询，因为可能还有其他符合条件的行，所以必须一行一行的查找直到最后一行——这就意味数据库不得不检查上万行数据才能找到所有名字为ZhangSan的雇员。这就是所谓的全表扫描，显然这种模式效率太慢。

使用索引的全部意义就是：通过缩小一张表中需要查询的记录/行的数目来加快搜索的速度。

在关系型数据库中，索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单（定义真特么拗口）。大白话意思是索引的作用相当于图书的目录，可以根据目录中的页码快速找到所需的内容。

一个索引是存储的表中一个特定列的值数据结构。索引是在表的列上创建。要记住的关键点是索引包含一个表中列的值，并且这些值存储在一个数据结构中。请牢记这一点：索引是一种数据结构。

1.2、作用

数据库中的表、数据、索引之间的关系，类似于书架上的图书、书籍内容和书籍目录的关系。

索引所起的作用类似书籍目录，可用于快速定位、检索数据。

索引对于提高数据库的性能有很大的帮助。

1.3、使用场景

索引的本质实际上还是存储在磁盘上的数据结构，它可以有的存储结构：

• 二叉搜索树；
• 红黑树；
• Hash 表；
• B-Tree；

其中 MySQL 的 InnoDB 支持 B+Tree 以及 Hash 表，下面会具体分析各个数据结构的区别。

①哈希索引

哈希索引(hash index)基于哈希表实现，只有精确匹配索引所有列的查询才有效生。对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码(hash code)，哈希码是一个较小的值，并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。

在 MySQL 中，只有 Memory 引擎显式支持哈希索引。这也是 Memory 引擎表的默认索引类型，Memory 引擎同时也支持 B-Tree 索引。值得一提的是，Memory 引擎是支持非唯一哈希索引的，这在数据库世界里面是比较与众不同的。如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中。

下面来看一个例子。假设有如下表：

create table tes(
 fname VARCHAR(50) NOT NULL,
  lname VARCHAR(50) NOT NULL,
  KEY USING HASH(fname)
) ENGINE = MEMORY;

然后再填入相关数据后，表格有如下数据：

假设索引使用假想的哈希函数

f()

，它返回下面的值(都是示例数据，非真实数据) :

• f(‘a’) = 23
• f(‘b’) = 74
• f(‘p’) = 87
• f(‘v’) = 24

则哈希索引的数据结构如下：
槽（Slot）值（Value）23指向第 1 行的指针24指向第 4 行的指针74指向第 2 行的指针87指向第 3 行的指针

注意每个槽的编号是顺序的，但是数据行不是。

下面使用 hash 索引字段进行查询，有：

select lname from tes where fname = 'p';

其分为如下的步骤：

• MSQL 先计算 ‘p’ 的哈希值；
• 根据哈希值进行寻找对应的地址指针，意味 hash 槽是有序的，因此查询效率很高；
• 读取对应指针上的数据是否为 ‘p’，是则返回

因为索引自身只需存储对应的哈希值，所以索引的结构十分紧凑，这也让哈希索引查找的速度非常快。然而，哈希索引也有它的限制：

• 哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行。不过，访问内存中的行的速度很快，所以大部分情况下这一点对性能的影响并不明显。
• 哈希索引数据并不是按照索引值顺序存储的，所以也就无法用于排序。
• 哈希索引不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。例如，在数据列 (A,B) 上建立哈希索引，如果查询只有数据列 A，则无法使用该索引。
• 哈希索引只支持等值比较查询，包括 =、IN()、<=>；不支持任何范围查询，例如 WHERE price>100。
• 访问哈希索引的数据非常快，除非有很多哈希冲突(不同的索引列值却有相同的哈希值)。当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。
• 如果哈希冲突很多的话，一些索引维护操作的代价也会很高。例如，如果在某个选择性很低(哈希冲突很多)的列上建立哈希索引，那么当从表中删除一行时，存储引擎需要遍历对应哈希值的链表中的每一行，找到并删除对应行的引用，冲突越多，代价越大。

②TREE

要考虑对数据库表的某列或某几列创建索引，需要考虑以下几点：

数据量较大，且经常对这些列进行条件查询。

该数据库表的插入操作，及对这些列的修改操作频率较低。

索引会占用额外的磁盘空间。

在没有GUI工具的情况下，可以使用以下命令查看索引：

上述ad_article表中有两个索引，Key_name中有显示:

-PRIMARY主键索引，Seq_in_index索引序号为1，从1开始，Collation为“A”表示升序（或NULL无分类），对应字段是id

-idx_cid是自建索引，由cid、available、id三个字段组成，分别对应序号1,2,3

Index_type=BTREE这块内容很多人不懂其意思，其实通过GUI工具创建索引时也会有BTREE 的显示，先着重了解一下。

在计算机数据结构（不懂数据结构的自行充电）体系中，为了加速查找的速度，常见的数据结构有两种：

-Hash哈希结构，例如Java中的HashMap，这种数据组织结构可以让查询/插入/修改/删除的平均时间复杂度都为O(1);

-Tree 树 结构 ， 这种数据组织结构可以让查询/插入/修改/删除的平均时间复杂度都为O(log(n));

不管读还是写，Hash这种类型比Tree树这种类型都要更快一些，那为什么MySQL的开发者既使用Hash类型做为索引，又使用了BTREE呢？

确实用HASH索引更快，因为每次都只查询一条信息（重名的雇员姓名也才几条而已），但实际上业务对于SQL的应用场景是：

-orderby 需要排个序

-groupby 还要分个组

-还要比较大小 大于或小于等等

这种情况下如果继续用HASH类型做索引结构，其时间复杂度会从O(1)直接退化为O(n)，相当于全表扫描了，而Tree的特性保证了不管是哪种操作，依然能够保持O(log(n))的高效率。

那MySQL中的BTREE和TREE又有啥联系与区别呢？先来看看传统的二叉树：

二叉树是大家熟知的一种树，用它来做索引行不行，可以是可以，但有几个问题：

-如果索引数据很多，树的层次会很高（只有左右两个子节点），数据量大时查询还是会慢

-二叉树每个节点只存储一个记录，一次查询在树上找的时候花费磁盘IO次数较多

所以它并不适合直接拿来做索引存储，算法设计人员在二叉树的基础之上进行了变种，引入了

③BTREE

如上图可知BTREE有以下特点：

-不再是二叉搜索，而是N叉搜索，树的高度会降低，查询快

-叶子节点，非叶子节点，都可以存储数据，且可以存储多个数据

-通过中序遍历，可以访问树上所有节点

BTREE被作为实现索引的数据结构被创造出来，是因为它能够完美的利用“局部性原理”，其设计逻辑是这样的：

-内存读写快，磁盘读写慢，而且慢很多

-磁盘预读：磁盘读写并不是按需读取，而是按页预读，一次会读一页的数据，每次加载一些看起来是冗余的数据，如果未来要读取的数据就在这一页中，可以避免未来的磁盘读写，提高效率（通常，一页数据是4K）

-局部性原理：软件设计要尽量遵循“数据读取集中”与“使用到一个数据，大概率会使用其附近的数据”，这样磁盘预读能充分提高磁盘IO效能

④****B+TREE

早先的MySQL就是使用的BTREE做为索引的数据结构，随着时间推移，B树发生了较多的变种，其中最常见的就是B+TREE变种，现在MySQL用的就是这种，示意如下：

B+TREE改进点及优势所在：

-仍然是N叉树，层级小，非叶子节点不再存储数据，数据只存储在同一层的叶子节点上，B+树从根到每一个节点的路径长度一样，而B树不是这样

-叶子之间，增加了链表(图中红色箭头指向)，获取所有节点，不再需要中序遍历，使用链表的next节点就可以快速访问到

-范围查找方面，当定位min与max之后，中间叶子节点，就是结果集，不用中序回溯（范围查询在SQL中用得很多，这是B+树比B树最大的优势）

-叶子节点存储实际记录行，记录行相对比较紧密的存储，适合大数据量磁盘存储；非叶子节点存储记录的PK，用于查询加速，适合内存存储

-非叶子节点，不存储实际记录，而只存储记录的KEY的话，那么在相同内存的情况下，B+树能够存储更多索引

可以来初步计算一下：假设key、子树节点指针均占用4B，则B树一个节点占用4 + 4 = 8B，一页页面大小4KB，则N = 4 * 1024 / 8B = 512，一个512叉的B树，1000w的数据，深度最大 log(512/2)(10^7) 约等于4。对比二叉树如AVL的深度为log(2)(10^7) 约为24，相差了5倍以上。

假如一个节点大小是4KB，一个KEY有8字节，一页可以存4000/8=500个KEY，根据N叉树特点,就算一层500叉节点，则：

第一层树：1个节点，1*500KEY , 大小4K

第二层树：500节点 500500=25万个KEY，5004K=2M

第三层树：500 * 500节点 500500500=1.2亿KEY，5005004K=1G

如果没算错，1G空间，只用三层树结构，可以存1.2亿行数据的KEY。

所以B+TREE索引只用占用很少的内存空间，却大大提升了查询效率（不论是单个查询、范围查询还是有序性查询），并且还减少了磁盘读写，所以好的算法与数据结构是可以省钱的。

1.4、使用

创建主键约束（PRIMARY KEY）、唯一约束（UNIQUE）、外键约束（FOREIGN KEY）时，会自动创建对应列的索引。

①查看索引

show index from 表名;

案例：查看学生表已有的索引

show index from student;

②创建索引

对于非主键、非唯一约束、非外键的字段，可以创建普通索引

create index 索引名 on 表名(字段名);

案例：创建班级表中，name字段的索引

create index idx_classes_name on classes(name);

创建主键索引

主键索引的定义：InnoDB 中的表单数据本身就要创建为一棵 B+ 树，而这棵排序节点用到的索引就被称为主键索引。

只要有主键，那么主键索引根据的就是主键，我们在创建表和后续修改时都能够通过指定主键来确定主键索引，如下：

创建表同时设置主键

create table teacher(
id int(10) auto_increment,
name varchar(20),
age int(10),
phone varchar(11),
primary key (id));--主键设置

单独设置主键

alter table teacher add primary key (id);

创建唯一索引

create table teacher(
id int(10) auto_increment,
name varchar(20),
age int(10),
phone varchar(11),
primary key (id),
unique index idx_phone(phone(11)));--唯一索引

--单独建唯一索引
create unique index idx_phone on teacher(phone(11));
--删除唯一索引
drop index idexName on tableName;
--修改建唯一索引
alter table teacher add unique idx_phone (phone(11));

** 创建普通索引**

create table teacher(
id int(10) auto_increment,
name varchar(20),
age int(10),
phone varchar(11),
primary key (id),
index idx_phone(phone(11)));
--单独建普通索引
create index idx_phone on teacher(phone(11));
--修改普通索引
alter table teacher add index idx_phone (phone(11));

创建联合索引

create table teacher(
id int(10) auto_increment,
name varchar(20),
phone varchar(11),
primary key (id),
index idx_name_phone (name(20),phone(11)));
--单独建组合索引
create index idx_name_phone on teacher (name(20),phone(11));
--修改组合索引
alter table teacher add index idx_name_phone (name(20),phone(11));

③删除索引

drop index 索引名 on 表名;

案例：删除班级表中name字段的索引

drop index idx_classes_name on classes;

1.5、MySQL面试 6 问

①索引是什么？

索引是一种特殊的文件(InnoDB数据表上的索引是表空间的一个组成部分)，它们包含着对数据表里所有记录的引用指针。

索引是一种数据结构。数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。索引的实现通常使用B树及其变种B+树。更通俗的说，索引就相当于目录。为了方便查找书中的内容，通过对内容建立索引形成目录。而且索引是一个文件，它是要占据物理空间的。

MySQL索引的建立对于MySQL的高效运行是很重要的，索引可以大大提高MySQL的检索速度。比如我们在查字典的时候，前面都有检索的拼音和偏旁、笔画等，然后找到对应字典页码，这样然后就打开字典的页数就可以知道我们要搜索的某一个key的全部值的信息了。

②索引有哪些优缺点？

索引的优点

• 可以大大加快数据的检索速度，这也是创建索引的最主要的原因。
• 通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

索引的缺点

• 时间方面：创建索引和维护索引要耗费时间，具体地，当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，会降低增/改/删的执行效率；
• 空间方面：索引需要占物理空间。

③说一说索引的底层实现？

Hash索引

基于哈希表实现，只有精确匹配索引所有列的查询才有效，对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（hash code），并且Hash索引将所有的哈希码存储在索引中，同时在索引表中保存指向每个数据行的指针。

B-Tree索引（MySQL使用B+Tree）

B-Tree能加快数据的访问速度，因为存储引擎不再需要进行全表扫描来获取数据，数据分布在各个节点之中。

B+Tree索引

是B-Tree的改进版本，同时也是数据库索引索引所采用的存储结构。数据都在叶子节点上，并且增加了顺序访问指针，每个叶子节点都指向相邻的叶子节点的地址。相比B-Tree来说，进行范围查找时只需要查找两个节点，进行遍历即可。而B-Tree需要获取所有节点，相比之下B+Tree效率更高。

B+tree性质：

• n棵子tree的节点包含n个关键字，不用来保存数据而是保存数据的索引。
• 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
• 所有的非终端结点可以看成是索引部分，结点中仅含其子树中的最大（或最小）关键字。
• B+ 树中，数据对象的插入和删除仅在叶节点上进行。
• B+树有2个头指针，一个是树的根节点，一个是最小关键码的叶节点。

④为什么索引结构默认使用B+Tree，而不是B-Tree，Hash，二叉树，红黑树？

B-tree：从两个方面来回答

• B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B(B-)树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。
• 由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。

Hash：

• 虽然可以快速定位，但是没有顺序，IO复杂度高；

• 基于Hash表实现，只有Memory存储引擎显式支持哈希索引 ；

• 适合等值查询，如=、in()、<=>，不支持范围查询 ；

• 因为不是按照索引值顺序存储的，就不能像B+Tree索引一样利用索引完成排序 ；

• Hash索引在查询等值时非常快 ；

• 因为Hash索引始终索引的所有列的全部内容，所以不支持部分索引列的匹配查找 ；

• 如果有大量重复键值得情况下，哈希索引的效率会很低，因为存在哈希碰撞问题 。

二叉树：树的高度不均匀，不能自平衡，查找效率跟数据有关（树的高度），并且IO代价高。

红黑树：树的高度随着数据量增加而增加，IO代价高。

⑤如何创建索引？

1、 在执行CREATE TABLE时创建索引

CREATE TABLE user_index2 (
 id INT auto_increment PRIMARY KEY,
 first_name VARCHAR (16),
 last_name VARCHAR (16),
 id_card VARCHAR (18),
 information text,
 KEY name (first_name, last_name),
 FULLTEXT KEY (information),
 UNIQUE KEY (id_card)
);

2、 使用ALTER TABLE命令去增加索引。

ALTER TABLE table_name ADD INDEX index_name (column_list);

3、 使用CREATE INDEX命令创建。

CREATE INDEX index_name ON table_name (column_list);

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

• 非空字段：应该指定列为NOT NULL，除非你想存储NULL。在mysql中，含有空值的列很难进行查询优化，因为它们使得索引、索引的统计信息以及比较运算更加复杂。你应该用0、一个特殊的值或者一个空串代替空值；
• 取值离散大的字段：（变量各个取值之间的差异程度）的列放到联合索引的前面，可以通过count()函数查看字段的差异值，返回值越大说明字段的唯一值越多字段的离散程度高；
• 索引字段越小越好：数据库的数据存储以页为单位一页存储的数据越多一次IO操作获取的数据越大效率越高。

二、事务

2.1、什么是事务？

事务是一组原子性的sql语句，或者说是一个独立的工作单元。事务有四个特性，原子性(Atomicity),一致性(Consistency),隔离型(Isolation)以及持久性(Durability)。

2.2、redo log 与 undo log介绍

①redo log

redo log叫做重做日志，用来实现事务的持久性。该日志文件由两部分组成：重做日志缓冲（redo log buffer）以及重做日志文件（redo log）,前者是在内存中，后者在磁盘中。当事务提交之后会把所有修改信息都会存到该日志中。

redo log 有什么作用？

mysql 为了提升性能不会把每次的修改都实时同步到磁盘，而是会先存到Boffer Pool(缓冲池)里头，把这个当作缓存来用。然后使用后台线程去做缓冲池和磁盘之间的同步。

总结：
redo log是用来恢复数据的用于保障，已提交事务的持久化特性

②undo log

undo log 叫做回滚日志，用于记录数据被修改前的信息。他正好跟前面所说的重做日志所记录的相反，重做日志记录数据被修改后的信息。undo log主要记录的是数据的逻辑变化，为了在发生错误时回滚之前的操作，需要将之前的操作都记录下来，然后在发生错误时才可以回滚。

undo log 有什么作用？

undo log 记录事务修改之前版本的数据信息，因此假如由于系统错误或者rollback操作而回滚的话

可以根据undo log的信息来进行回滚到没被修改前的状态。

总结：
undo log是用来回滚数据的用于保障未提交事务的原子性

2.3、事务的实现

①原子性的实现

什么是原子性：

一个事务必须被视为不可分割的最小工作单位，一个事务中的所有操作要么全部成功提交，要么全部失败回滚，对于一个事务来说不可能只执行其中的部分操作，这就是事务的原子性。

undo log 的生成

每条数据变更(insert/update/delete)操作都伴随一条undo log的生成,并且回滚日志必须先于数据持久化到磁盘上
所谓的回滚就是根据回滚日志做逆向操作，比如delete的逆向操作为insert，insert的逆向操作为delete，update的逆向为update等。

根据undo log 进行回滚

回滚操作就是要还原到原来的状态，undo log记录了数据被修改前的信息以及新增和被删除的数据信息，根据undo log生成回滚语句，比如：

(1) 如果在回滚日志里有新增数据记录，则生成删除该条的语句

(2) 如果在回滚日志里有删除数据记录，则生成生成该条的语句

(3) 如果在回滚日志里有修改数据记录，则生成修改到原先数据的语句

②持久性的实现

事务一旦提交，其所作做的修改会永久保存到数据库中，此时即使系统崩溃修改的数据也不会丢失。

MySQL的表数据是存放在磁盘上的，因此想要存取的时候都要经历磁盘IO,然而即使是使用SSD磁

盘IO也是非常消耗性能的。为此，为了提升性能InnoDB提供了缓冲池(Buffer Pool)，Buffer Pool中

包含了磁盘数据页的映射，可以当做缓存来使用：

读数据：会首先从缓冲池中读取，如果缓冲池中没有，则从磁盘读取在放入缓冲池；

写数据：会首先写入缓冲池，缓冲池中的数据会定期同步到磁盘中；

③隔离性实现

隔离性是事务ACID特性里最复杂的一个。在SQL标准里定义了四种隔离级别，每一种级别都规定一个事务中的修改，哪些是事务之间可见的，哪些是不可见的。级别越低的隔离级别可以执行越高的并发，但同时实现复杂度以及开销也越大。

Mysql 隔离级别有以下四种（级别由低到高）：

READ UNCOMMITED (未提交读)

READ COMMITED (提交读)

REPEATABLE READ (可重复读)

SERIALIZABLE (可重复读)

只要彻底理解了隔离级别以及他的实现原理就相当于理解了ACID里的隔离型。前面说过原子性，

隔离性，持久性的目的都是为了要做到一致性，但隔离型跟其他两个有所区别，原子性和持久性是

为了要实现数据的可性保障靠，比如要做到宕机后的恢复，以及错误后的回滚。

实现事务采取了哪些技术以及思想？

2.4、总结

原子性：使用undo log，从而达到回滚

持久性：使用redo log，从而达到故障后恢复

隔离性：使用锁以及MVCC,运用的优化思想有读写分离，读读并行，读写并行

一致性：通过回滚，以及恢复，和在并发环境下的隔离做到一致性。