前言

MySQL 在我的心中一直是个一个存储数据的大盒子，我并不知道大家为什么都用 MySQL，而不选择使用 Oracle、SQLServer 等其他数据库（因为其他公司都用 MySQL？MySQL开源？）。网络上有大量的文章来说明 MySQL 的各种好，我没有切身体会（Oracle、SQLServer 在工作中用的很少，大部分项目都是 MySQL。）无法形成自我判断。对各种数据库也只是停留在增删改查，工作中大部分时间也没有接触到大数据高并发。所以也就一直这样得过切过、随波逐流的浅显的使用者MySQL。数据库中索引、存储过程等更是我知道又不敢触碰的东西,总感觉它是一个玄之又玄的东西,在工作中更多的是照猫画虎，能用就完事了。但是随着项目的数据量的增加，我不得不面对一件事：“百万级、千万级的数据量下如何保证 MySQL 的高性能？”

最后的挣扎下（主要的不知道怎么处理这类工作），我鼓起勇气去面对我心里的“老虎”。查看了大量的 MySQL 的视频、网络文章和书籍,发现 MySQL 也没有那么的“吓人”，对 MySQL 的有了一点浅显的认知,甚至我觉得 MySQL 的很多知识让我觉得它很有趣。接下来我将把我对 MySQL 的认识做一个记录，如有不正确的地方,我也不会当回事~

至少要知道什么是索引

1 索引是什么

MySQL 作为互联网中非常热门的 RDBMS(Relational Database Management System：关系数据库管理系统)，其底层的存储引擎和数据检索引擎的设计非常重要，尤其是 MySQL 数据的存储形式以及索引的设计，决定了 Mysql 整体的数据检索性能。

了解索引对我们以后玩转数据库变动至关重要。

百度百科对索引的描述（片段）：

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

简单来说:索引是对数据库表中一列或多列的值进行排序的一种结构，使用索引可快速访问数据库表中的特定信息。

我们需要知道索引是一种数据结构，并且它是有序的。

2 磁盘 IO 与预读

建立索引会占用磁盘空间的索引文件。在了解索引之前我们就需要知道磁盘读取数据的简易运行原理（这儿描述的是机械磁盘，固态磁盘原理类似具体的实现不一样，感兴趣的自行度娘）。

磁盘读取数据靠的是机械运动，每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分，

寻道时间指的是磁臂移动到指定磁道所需要的时间，主流磁盘一般在 5ms 以下；

旋转延迟就是我们经常听说的磁盘转速，比如一个磁盘 7200 转，表示每分钟能转 7200 次，也就是说 1 秒钟能转 120 次，旋转延迟(磁盘旋转一周所需时间的一半)就是 1/120/2 = 4.17ms；

传输时间指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计。

那么访问一次磁盘的时间，即一次磁盘 IO 的时间约等于 5+4.17 = 9ms 左右，听起来还挺不错的，假如一台机器每秒可以执行 5 亿条指令，因为指令依靠的是电的性质，换句话说执行一次 IO 的时间可以执行 40 万条指令，数据库动辄十万百万乃至千万级数据，每次 9 毫秒的时间，显然是个灾难。

3 索引存在哪儿

和数据一样，索引以文件形式储存在硬盘上，在 MyISAM 储存引擎中，数据和索引文件试试分开储存的。

• .frm（frame）存储数据结构
• .MYD（myData）存储数据
• .MYI（myIndex）存储数据索引

在 InnoDB 中，数据和索引文件是合起来储存的（.ibd 文件）。

明白这几棵树，很重要

1 索引的数据结构

每次查找数据时把磁盘 IO 次数控制在一个很小的数量级，最好是常数数量级。那么我们就想到如果一个高度可控的多路搜索树。

B+树索引是 B+树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B+树中的 B 代表平衡（balance），而不是二叉（binary），因为 B+树是从最早的平衡二叉树演化而来的。

在讲 B+树之前必须先了解二叉查找树、平衡二叉树（AVLTree）、红黑树和平衡多路查找树（B-Tree），B+树即由这些树逐步优化而来。

2 二叉树

二叉树具有以下性质：左子树的键值小于根的键值，右子树的键值大于根的键值。

如下图所示就是一棵二叉查找树:

二叉查找树可以任意地构造，同样是 2,3,5,6,7,8 这六个数字，也可以按照下图的方式来构造：

但是这棵二叉树的查询效率就低了。因此若想二叉树的查询效率尽可能高，需要这棵二叉树是平衡的，从而引出新的定义——平衡二叉树，或称 AVL 树。

3 平衡二叉树（AVL树）

平衡二叉树（AVL 树）在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最大差为 1。

下面的两张图片，左边是 AVL 树，它的任何节点的两个子树的高度差<=1；右边的不是 AVL 树，其根节点的左子树高度为 3，而右子树高度为 1；

平衡二叉树的 4 种失衡状态

如果在 AVL 树中进行插入或删除节点，可能导致 AVL 树失去平衡，这种失去平衡的二叉树可以概括为四种姿态：LL（左左）、RR（右右）、LR（左右）、RL（右左）。它们的示意图如下：

发现者：即第一个发现这个结点两边的高度之差大于1(我们也叫做最小不平衡结点或最小失衡子树根结点 : 距离插入节点最近的不平衡节点)。

这四种失去平衡的姿态都有各自的定义：

LL：LeftLeft，也称“左左”。插入或删除一个节点后，根节点的左孩子（Left Child）的左孩子（Left Child）还有非空节点，导致根节点的左子树高度比右子树高度高 2，AVL 树失去平衡。

LL 失去平衡的情况下，可以通过一次旋转让 AVL 树恢复平衡(左单旋)。步骤如下：

1. 将根节点的左孩子作为新根节点。

2. 将新根节点的右孩子作为原根节点的左孩子。

3. 将原根节点作为新根节点的右孩子。

RR：RightRight，也称“右右”。插入或删除一个节点后，根节点的右孩子（Right Child）的右孩子（Right Child）还有非空节点，导致根节点的右子树高度比左子树高度高 2，AVL 树失去平衡。

RR 失去平衡的情况下，旋转方法与 LL 旋转对称(右单旋)，步骤如下：

1. 将根节点的右孩子作为新根节点。

2. 将新根节点的左孩子作为原根节点的右孩子。

3. 将原根节点作为新根节点的左孩子。

LR：LeftRight，也称“左右”。插入或删除一个节点后，根节点的左孩子（Left Child）的右孩子（Right Child）还有非空节点，导致根节点的左子树高度比右子树高度高 2，AVL 树失去平衡。

LR 失去平衡的情况下，需要进行两次旋转(右左双旋)，步骤如下：

1. 围绕根节点的左孩子进行 RR 旋转。

2. 围绕根节点进行 LL 旋转。

RL：RightLeft，也称“右左”。插入或删除一个节点后，根节点的右孩子（Right Child）的左孩子（Left Child）还有非空节点，导致根节点的右子树高度比左子树高度高 2，AVL 树失去平衡。

RL 失去平衡的情况下也需要进行两次旋转，旋转方法与 LR 旋转对称(左右双旋)，步骤如下：

1. 围绕根节点的右孩子进行 LL 旋转。

2. 围绕根节点进行 RR 旋转。

AVL 树是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，左右子树高度差不超过 1，和红黑树相比，AVL 树是严格的平衡二叉树，平衡条件必须满足(所有结点的左右子树高度差不超过 1)。

不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保存平衡，而因为旋转非常耗时，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。由此我们可以知道 AVL 树适合用于插入与删除次数比较少，但查找较多的情况使用。

红黑树

通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因此，红黑树是一种弱平衡二叉树(由于是弱平衡，可以看到，在相同的节点情况下，AVL 树的高度低于红黑树)，相对于要求严格的 AVL 树来说，它的旋转次数少，插入最多两次旋转，删除最多三次旋转，所以对于搜索，插入，删除操作较多的情况下，我们就用红黑树。

红黑树的性质：

1. 每个节点不是红色就是黑色
2. 不可能有连在一起的红色节点
3. 根节点都是黑色
4. 每个红色节点的两个子节点都是黑色。叶子节点都是黑色。（在 Java 中 NIL 节点为 null）

红黑树旋转和颜色变化规则：所有插入的点默认为红色

1. 变色的情况：当前节点的父亲是红色，且它的祖父节点的另一个子节点也是红色。（叔叔节点）：

• 把父节点设置为黑色
• 把叔叔节点也设置为黑色
• 把祖父也就是父亲的父亲设为红色
• 把指针定义到祖父节点设为当前要操作的（重新判断祖父节点是否符合红色树要求）

2. 左旋：当前父节点是红色，叔叔是黑色的时候，且当前的节点是右子树。左旋以父节点作为左旋。
3. 右旋：当前父节点是红色，叔叔是黑色时候，且当前的节点是左子树。右旋

• 把父节点变为黑色
• 把祖父节点变为红色
• 以祖父节点旋转

红黑树的应用很多，其中JDK的集合类TreeMap和TreeSet、Java8中的HashMap都用到了红黑树。

AVL 树和红黑树基本都是存储在内存中才会使用的数据结构。在大规模数据存储的时候，红黑树往往出现由于树的深度过大(读取磁盘次数过多)和读取浪费太多(一次读取16K)而造成磁盘 IO 读写过于频繁，进而导致效率低下。

B-Tree(平衡多路查找树)

B-Tree 是为磁盘等外存储设备设计的一种平衡查找树。我们介绍过AVL树，红黑树，它们都属于二叉树，即每个节点最多只能拥有2个子节点，而B-tree（B树）的每个节点可以拥有2个以上的子节点，所以我们简单概括一下：B-tree就是一颗多路平衡查找树，它广泛应用于数据库索引和文件系统中。

一棵 m 阶的 B-Tree 有如下特性：

1. 节点最多含有 m 颗子树(指针,就是箭头符),m-1 关键字(数据)(m>=2);
2. 除根节点和叶子节点外,其他每个节点至少有 ceil(m/2)个子节点,ceil 为向上取整;
3. 若根节点不是叶子节点,则至少有两颗子树;

B-Tree 有一个非常重要的操作,当一颗树不满足以上性质的时候会进行分裂，分裂的时候从中间分开，分成两个子树。

B+Tree

B+Tree 是在 B-Tree 基础上的一种优化，使其更适合实现外存储索引结构，InnoDB 存储引擎就是用 B+Tree 实现其索引结构。

从上一节中的 B-Tree 结构图中可以看到每个节点中不仅包含数据的 key 值，还有 data 值。而每一个页的存储空间是有限的，如果 data 数据较大时将会导致每个节点（即一个页）能存储的 key 的数量很小，当存储的数据量很大时同样会导致 B-Tree 的深度较大，增大查询时的磁盘 I/O 次数，进而影响查询效率。在 B+Tree 中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储 key 值信息，这样可以大大加大每个节点存储的 key 值数量，降低 B+Tree 的高度。

B+Tree 相对于 B-Tree 有几点不同：

1. 非叶子节点只存储键值信息。

2. 所有叶子节点之间都有一个链指针。

3. 数据记录都存放在叶子节点中。

Hash

哈希索引（Hash Index）基于哈希表实现，只有精确匹配索引所有列的查询才有效。对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（Hash Code），哈希码是一个较小的值，并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。出现哈希值碰撞的话(两个值的哈希值一样,这样的概率很小但无法保证不出现)，索引会以链表的形式存放多个记录指针到同一个哈希条目中。

假设使用假想的哈希函数 f()，生成对应的设想值：

f('Alice') = 2

f('Jim') = 2（哈希碰撞）

f('Tom') = 4

当我们找到 2 的时候先去会找到一个值'Alice',如果'Alice'不符合,则再去找下一个'Jim',类似于数组的循环(或者链表)查找。

Hash 索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位，不像 B-Tree 索引需要从根节点到枝节点，最后才能访问到页节点这样多次的 IO 访问，所以 Hash 索引的查询效率要远高于 B-Tree 索引。

可能很多人又有疑问了，既然 Hash 索引的效率要比 B-Tree 高很多，为什么大家不都用 Hash 索引而还要使用 B-Tree 索引呢?任何事物都是有两面性的，Hash 索引也一样，虽然 Hash 索引效率高，但是 Hash 索引本身由于其特殊性也带来了很多限制和弊端，主要有以下这些：

1. Hash碰撞。
2. Hash 索引仅仅能满足"=","IN"和"<=>"查询，不能使用范围查询。哈希索引只支持等值比较查询，包括＝、 IN 、<=> (注意<>和＜＝＞是不同的操作）。也不支持任何范围查询，例如 WHERE price > 100。
3. Hash 索引无法被用来避免数据的排序操作。
4. Hash 索引不能利用部分索引键查询。

效率推算

InnoDB 存储引擎中页的大小为 16KB，一般表的主键类型为 INT（占用 4 个字节）或 BIGINT（占用 8 个字节），指针类型也一般为 4 或 8 个字节，也就是说一个页（B+Tree 中的一个节点）中大概存储 16KB/(8B+8B)=1K 个键值（因为是估值，为方便计算，这里的 K 取值为〖10〗^3）。也就是说一个深度为 3 的 B+Tree 索引可以维护 10^3 _ 10^3 _ 10^3 = 10 亿 条记录。

实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree 的高度一般都在 2~4 层。mysql 的 InnoDB 存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要 1~3 次磁盘 I/O 操作。

MySQL 的索引不难

MyISAM 和InnorDB的区别

聚集索引和辅助索引

数据库中的 B+Tree 索引可以分为聚集索引（clustered index）和辅助索引（或者叫二级索引、非聚集索引,secondary index）。

聚集索引就是按照每张表的主键构造一棵B+树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页。聚集索引的这个特性决定了索引组织表中的数据也是索引的一部分。同B+树结构一样，每个数据页都通过一个双向链表进行链接。如果未定义主键，MySQL取第一个唯一索引（unipue)而且只含非空列（not null)作为主键，InnoDB使用它作为聚集索引。如果没有这样的列，InnoDB就自己产生一个这样的ID值，它有六个字节，而且是隐藏的，使其做为聚集索引。

由于实际的数据页只能按照一棵B+树进行排序，因此每张表只能拥有一个聚集索引

InnorDB 索引实现（聚集索引）

辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。

当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。

聚集索引

1. 记录的索引顺序与物理顺序相同 因此更适合 between and 和order by操作
2. 叶子结点直接对应数据 从中间级的索引页的索引行直接对应数据页
3. 每张表只能创建一个聚集索引

MyISAM 索引实现（非聚集索引）

MyISAM 中索引和数据是分开储存的，并且主键索引和辅助索引（二级索引）的储存方式是一样的。

在MyIASM中，主索引和辅助索引在结构上没有任何区别，只要主索引要求key是唯一的，而辅助索引的key可以重复。

非聚集索引

1. 索引顺序与物理顺序无关
2. 叶子结点不直接指向数据页
3. 每张表可以有多个辅助索引，需要更多磁盘和内容 多个索引会影响insert 和update 的速度

联合索引

联合索引是指对表上的多个列进行索引，联合索引也是一棵B+树，不同的是联合索引的键值数量不是1，而是大于等于2。

比较相等时，先比较第一列的值，如果相等，再继续比较第二列，以此类推。

最左前缀原理

使用联合索引时，索引列的定义顺序将会影响到最终查询时索引的使用情况。例如联合索引（a,b,c），mysql 会从最左边的列优先匹配，如果最左边的带头大哥没有使用到，在未使用覆盖索引的情况下，就只能全表扫描。联合底层数据结构思考，mysql 会优先以联合索引第一列匹配，此后才会匹配下一列，如果不指定第一列匹配的值，也就无法得知下一步查询哪个节点。另外还有一种情况，如果遇到 > < between 等这样的范围查询，那 B+树中也就无法对下一列进行等值匹配了。