从数据结构到MySQL的InnoDb存储引擎

发表于 | 分类于

一、索引的本质

索引是为了加速对表中数据行的检索而创建的一种分散存储的数据结构。简单来讲，索引本身是一种或多种数据结构，目的是为了加速表中数据行的检索。
在RDBMS系统中数据的索引都是硬盘级索引。

二、索引的数据结构

二叉树

定义

二叉树是每个结点最多有两个子树的树结构，也称之为二路查找树。可以用于实现二叉查找树和二叉堆）。二叉树图示如下：
二叉树

缺点

  1. 树的高度太高，不是硬盘级别索引。每个结点存储数据和指向磁盘的指针，没有利用好磁盘级别索引的特性，磁盘利用率过低。
  2. 没有利用好操作系统跟磁盘交互的特性，没有利用好磁盘IO的预读能力（空间局部性），带来频繁IO。

B树

定义

阶的概念

对于一棵m阶的B树，每个结点最多有m个子节点。如下图，这个B树最多的结点有三个子结点，所以它的阶数为3。

度的概念

度指的是树的高度，也就是树的层数。 下图这个B树高为3，那么也就是说它的度为3。
B树

B树的定义

  1. 树中每个结点至多有m棵子树（m为树的阶）
  2. 根结点不是不是叶子节点，至少有两棵子树
  3. 除根结点之外所有非叶子结点至少有p个子结点（m/2（向上取整） ≤ p ≤ m）
  4. 所有的非叶子节点都包含以下数据（n,A0,K1,A1,K2,…,Kn,An）,其中n为关键字个数，Ai为指向叶子结点的指针，Ki为关键字（实际存储的数据），且Ki<Ki+1.
  5. 所有的叶子结点都出现在同一层次上，即所有的叶子结点具有相同的深度，等于树高度，并且不带信息。

多路平衡查找数，平衡的意思是左右两边分布均匀；多路是相对于二叉树而言，二叉树就是二路查找树，查找的时候只有两条路，而B树有多条路，父节点有多个子节点。每个结点可以抽象认为是一个磁盘块，包含数据区和指向子结点的指针。根据B树的定义，我们可以画出实际磁盘数据存储过程中的结构图，如下：
B树
在此图中我们可以这么理解，假设寻找X，

  1. x<17，命中P1指针
  2. x=17，直接命中
  3. 17<x<35，命中P2指针
  4. x=35，直接命中
  5. x>35，命中P3指针

缺点

由图可以看出，B树作为索引的数据结构，是不适用于范围查询的。因为关键字保存在每个非叶子结点上，每个非叶子结点都可以认为一个磁盘块，范围查询如果跨叶子结点，意味着跨磁盘块。这也就是为什么B树不适合作为索引。

B+树

B+树也是B树的一种，由B树演进而来，主要是为了适配基于磁盘的索引条件。它是如何适配基于磁盘的索引的呢？首先我们需要了解一下B+的定义以及它的优点。

定义

  1. 左闭右开区间。
  2. 有k个子结点必然有k个关键码。
  3. 非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。

B树
记录数据相关的信息存储在叶结点中，树的所有叶结点构成一个有序链表，按照关键码排序的次序遍历全部记录。
B+树与B树不同点在于以上两点，关键字个数和子结点个数，以及非叶子结点的数据存储。

优点

  1. 符合InnoDB存储引擎的硬盘级索引方式。IO能力强。
  2. 基于索引的扫库、扫表能力强于B树。
  3. 范围查询，天然有序。
  4. 查询能力较为稳定。

三、Innodb支持的索引

目前InnoDB存储引擎支持以下方式索引：

  1. B+tree
  2. 自适应hash索引

除了上文提到的B+树索引，InnoDB还支持hash索引。这个hash索引指的是自适应hash索引。引擎会监控对表上各索引页的查询。如果观察到建立哈希索引可以带来速度提升，则建立哈希索引，称之为自适应哈希索引(Adaptive Hash Index, AHI)。AHI是通过缓冲池的B+树页构造而来，因此建立的速度很快，而且不需要对整张表构建哈希索引。Innodb存储引擎会监控对表上二级索引的查找，如果发现某二级索引被频繁访问，二级索引成为热数据，经常访问的二级索引数据会自动被生成到hash索引里面去，自适应哈希索引通过缓冲池的B+树构造而来（B+树的索引，可以称之为索引中的索引），因此建立的速度很快。hash索引的原理过程如下图：

hash索引

四、索引的内容

MyISAM索引保存指针地址，主键索引和辅助索引一致。如下图：
hash索引
InnoDB索引主键索引保存实际数据（聚簇索引），辅助索引保存主键索引的值（非聚簇索引）。为什么辅助索引不保存主键索引的实际地址？因为随着数据的CUD操作，主键索引的地址也会发生变化。
InnoDB索引数据存储如下：
hash索引
辅助索引与主键索引的关系如下：
hash索引
上文提到InnoDB支持的索引，每种数据结构存储的数据内容不一样。

  1. B+树索引，非叶子结点存储关键字和指针信息（指向子结点）；叶子结点存储了数据信息和指向下一个叶子结点的指针。
  2. hash索引存储了二级索引信息和指向实际数据磁盘区块的指针。它是索引中的索引。

五、索引的形式

联合索引

所谓联合索引，就是由数据库表多个关键字联合起来形成的索引，此类索引是有顺序的（ABC和CBA是两个完全不同的联合索引，本质上是两个不同的B+树）。单列索引可以认为是特殊的联合索引。由于联合索引数据结构也是B+树，所以在使用联合索引进行查询的时候，从左到右、从小到大依次匹配，也就是我们常说的最左前缀原则。

覆盖索引

覆盖索引是指查询列可以通过索引结点中的关键字直接返回。由此可以推断出，主键索引是覆盖索引，因为主键所在的物理磁盘上存储了主键所在行的所有信息。
覆盖索引可减少数据库IO。

覆盖索引

五、InndoDB锁机制

InnoDB存储引擎当中，参数autocommit=true，自动提交为true，意味着每一条sql就是一个单独的事物。显示开启需要指定begin/start transaction，显示提交commit。

InnoDB行锁如何实现

  1. 通过给索引上的索引项加锁实现的。
  2. 通过索引进行数据检索，InnoDB才会使用行级锁，否则使用表锁（锁住索引的所有记录）。

六、行锁算法

临键锁

当sql执行按照索引进行数据检索时，查询条件为范围查找（between and、<、>等）且有数据命中时，该sql语句加上的行锁为next-key locks。具体实现：锁住命中区间+下一个区间（左开右闭）

间隙锁

当sql执行按照索引进行数据检索时，且查询条件的数据不存在时，这是sql语句加上的锁即为Gap locks。具体实现：锁住数据不存在的区间（左开右开）。这也就说明了，记录不存在临键锁退化为间隙锁。

记录锁

唯一性索引（主键索引、唯一键索引），条件为精准命中，退化为记录锁（Record lock）。

为什么InnoDB可重复读能解决幻读问题？

  1. 临键锁机制。如上文提到，临键锁有效的锁住了相应的区间 ，避免的不同事物之间对数据的影响。
  2. MVCC机制。多版本并发控制，通过版本号等概念，实现了不同事物不同版本的逻辑视图。详细可见MySQL事物隔离级别以及MVCC
坚持原创分享