索引

背景

要学习索引,首先要明白为什么要引入索引

磁盘

关于磁盘

局部性原理与磁盘预读

  • 局部性原理

在OS的学习中,我们学习了局部性原理的相关知识;

简单的来说就是:当一个数据被用到时,其附近的数据也通常会马上被使用

  • 预读

基于这个理论,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存

而由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。

  • 预读细节

预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。

所以IO一次就是读一页的大小

  • Mysql预读

这个道理适用于Mysql的数据处理:MySQL 在读取的时候,并不是每条每条读取,而是每次读取一页,一页通常包含好多条。

B+Tree(Balance - Plus - Tree)

面试官:对于MySQL,你对他索引原理了解吗?
我:了解
面试官:MySQL的索引是用什么数据机构的?
我:B+树
面试官:为什么要用B+树,而不是B树?
我:…
面试官:用B+树作为MySql的索引结构,用什么好处?

我:…

二叉搜索树

  • 二叉搜索树中每个节点的特点
    • 比保存在左子树的任何键值都要大
    • 比保存在右子树的任何键值都要小

上图为在有序数组中查找元素【27】的二叉搜索树搜索过程

平衡二叉查找树

对于要查找元素 6 的情况:

下图左边是二叉搜索树,时间复杂度为0(n);而右边是经过调整(旋转)后的平衡二叉搜索树,此时树的高度减少了一半,查找效率变为O(log2n)

二叉搜索树对比

  • 平衡树旋转保持平衡性

平衡二叉搜索树旋转

B-树(Balance-Tree)

概述

B树,又称多路查找树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树

B树中所有结点的孩子个数的最大值称为B树的,通常表示为一颗m阶树空树

B-tree算法减少定位记录时所经历的中间过程,从而加快存取速度。普遍运用在数据库文件系统

img

存储结构
1
2
3
4
5
6
struct B_TNode{
int numOfKey;//关键字个数 - 文件数
B_TNode *parent;//指向父结点的指针
B_TNode **childPtr;//指向子树的指针,childPtr[0]...childPtr[numOfKey]
int *key;//指向关键字数组的指针
};
特点

B树

  1. 每个节点最多有m 个孩子(m>=2)。
  2. 每个非叶节点(根除外)至少有 ⌈ m /2⌉ (向上取整)个子节点。
  3. 如果根不是叶节点,则根至少有两个子节点。
  4. 一个有k 个孩子的非叶节点包含k − 1 个键,即孩子树为3的话,关键字个数为2,前者为4的话,后者为3,以此类推。
  5. 所有叶子都出现在同一层,不携带任何信息。
B-树的查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Data* BTreeSearch(Root *node, Key key)
{
Data* data;

if(root == NULL)
return NULL;
data = BinarySearch(node);
if(data->key == key)
{
return data;
}else{
node = ReadDisk(data->next);
BTreeSearch(node, key);
}
}
  • 查找过程

img

下面,咱们来模拟下查找文件29的过程:

  1. 根据根结点指针找到文件目录的根磁盘块1,将其中的信息导入内存。【磁盘IO操作 1次】
  2. 此时内存中有两个文件名17、35和三个存储其他磁盘页面地址的数据。根据算法我们发现:17<29<35,因此我们找到指针p2。
  3. 根据p2指针,我们定位到磁盘块3,并将其中的信息导入内存。【磁盘IO操作 2次】
  4. 此时内存中有两个文件名26,30和三个存储其他磁盘页面地址的数据。根据算法我们发现:26<29<30,因此我们找到指针p2。
  5. 根据p2指针,我们定位到磁盘块8,并将其中的信息导入内存。【磁盘IO操作 3次】
  6. 此时内存中有两个文件名28,29。根据算法我们查找到文件名29,并定位了该文件内存的磁盘地址。

B+树

  1. 有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。
  2. 所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。(链表)
  3. 所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。
  4. B+树查找时是从上到下查找;B-树则是从下往上查找(中序遍历)

B+树

  • B+树的优势

1.单一节点存储更多的元素(这样该节点下分支变多了,树变矮胖了),使得查询的IO次数更少。

2.所有查询都要查找到叶子节点,查询性能稳定

3.所有叶子节点成有序链表,便于范围查询

  • 为什么说B+树比B 树更适合实际应用中操作系统的文件索引和数据库索引?
  1. B+树更适合外部存储。由于内结点不存放真正的数据(只是存放其子树的最大或最小的关键字,作为索引),一个结点可以存储更多的关键字,每个结点能索引的范围更大更精确,也意味着B+树单次磁盘IO的信息量大于B树,I/O的次数相对减少。
  2. MySQL是一种关系型数据库,区间访问是常见的一种情况,B+树叶结点增加的链指针,加强了区间访问性,可使用在区间查询的场景(即B+树只要遍历叶子节点就可以实现整棵树的遍历);而使用B树则无法进行区间查找。

聚簇索引 与 非聚簇索引

在《数据库原理》里面,

  • 对聚簇索引的解释是:聚簇索引的顺序就是数据的物理存储顺序
  • 对非聚簇索引的解释是:索引顺序与数据物理排列顺序无关。

所以一个表最多只能有一个聚簇索引。

引言的描述非常抽象,我们可以理解成:聚簇索引的叶结点就是数据结点;而非聚簇索引的叶结点仍然是索引节点(包含一个指向数据库的指针)

聚簇索引

聚簇索引。表数据按照索引的顺序来存储的,也就是说索引项的顺序与表中记录的物理顺序一致。对于聚集索引,叶子结点即存储了真实的数据行,不再有另外单独的数据页。

在一张表上最多只能创建一个聚集索引,因为真实数据的物理顺序只能有一种。

由于上述这个特性,该在哪一列上建立聚簇索引将严重影响查询速度!(默认是主键ID,但可以后期修改)

即 :聚集索引是一种稀疏索引,数据页上一级的索引页存储的是页指针,而不是行指针(直接指向数据,不用拐弯抹角再通过指针去找页中找数据)

聚簇索引

  • 特点
  1. 一个索引项直接对应实际数据记录的存储页,可谓“直达”
  2. 主键缺省使用它
  3. 索引项的排序和数据行的存储排序完全一致,利用这一点,想修改数据的存储顺序,可以通过改变主键的方法(撤销原有主键,另找也能满足主键要求的一个字段或一组字段,重建主键)
  4. 一个表只能有一个聚簇索引(理由:数据一旦存储,顺序只能有一种)

非聚簇索引

非聚簇索引。表数据存储顺序与索引顺序无关。对于非聚集索引,叶结点包含索引字段值及指向数据页数据行的逻辑指针,其行数量与数据表行数据量一致。

即:非聚簇索引,则是密集索引,在数据页的上一级索引页它为每一个数据行存储一条索引记录。(需要通过索引指针,进一步在数据页中找数据)

非聚簇索引

  • 特点
  1. 不能“直达”,可能链式地访问多级页表后,才能定位到数据页
  2. 一个表可以有多个非聚簇索引

聚簇索引建立在哪?

理解

  • 聚簇索引

    其实,我们的汉语字典的正文本身就是一个聚集索引。比如,我们要查”安”字,就会很自然地翻开字典的前几页,因为”安”的拼音是”an”,而按照拼音排序 汉字的字典是以英文字母”a”开头并以”z”结尾的,那么”安”字就自然地排在字典的前部。如果您翻完了所有以”a”开头的部分仍然找不到这个字,那么就 说明您的字典中没有这个字;同样的,如果查”张”字,那您也会将您的字典翻到最后部分,因为”张”的拼音是”zhang”。也就是说,字典的正文部分本身 就是一个目录,您不需要再去查其他目录来找到您需要找的内容。

我们把这种正文内容本身就是一种按照一定规则排列的目录称为”聚集索引”

  • 非聚簇索引

如果您认识某个字,您可以快速地从自动中查到这个字。但您也可能会遇到您不认识的字,不知道它的发音,这时候,您就不能按照刚才的方法找到您要查的字,而 需要去根据”偏旁部首”查到您要找的字,然后根据这个字后的页码直接翻到某页来找到您要找的字。但您结合”部首目录”和”检字表”而查到的字的排序并不是 真正的正文的排序方法,比如您查”张”字,我们可以看到在查部首之后的检字表中”张”的页码是672页,检字表中”张”的上面是”驰”字,但页码却是63 页,”张”的下面是”弩”字,页面是390页。很显然,这些字并不是真正的分别位于”张”字的上下方,现在您看到的连续的”驰、张、弩”三字实际上就是他 们在非聚集索引中的排序,是字典正文中的字在非聚集索引中的映射。我们可以通过这种方式来找到您所需要的字,但它需要两个过程,先找到目录中的结果,然后 再翻到您所需要的页码。

我们把这种目录纯粹是目录,正文纯粹是正文的排序方式称为”非聚集索引”。

总结:

  1. 对于经常要搜索范围值的列,应该使用建立聚簇索引
  2. 从表中检索出来数据,后期要进行排序时,应该建立索引聚簇,避免后期排序,节省成本

建立聚簇索引的思想/原则

  1. 大多数表都应该有聚簇索引或使用分区来降低对表尾页的竞争,在一个高事务的环境中,对最后一页的封锁严重影响系统的吞吐量。
  2. 在聚簇索引下,数据在物理上按顺序排在数据页上,重复值也排在一起,因而在那些包含范围检查 (between、<、<=、>、>=)或使用group by或orderby的查询时,一旦找到具有范围中第一个键值的行,具有后续索引值的行保证物理上毗连在一起而不必进一步搜索,避免了大范围扫描,可以大 大提高查询速度。
  3. 在一个频繁发生插入操作的表上建立聚簇索引时,不要建在具有单调上升值的列(如IDENTITY)上,否则会经常引起封锁冲突。
  4. 在聚簇索引中不要包含经常修改的列,因为码值修改后,数据行必须移动到新的位置。
  5. 选择聚簇索引应基于where子句和连接操作的类型。

建立索引的要求

根据表的大小创建索引

虽然给表创建索引,可以提高查询的效率。但是需要注意的是,索引也需要一定的开销的。为此并不是说给所有的表都创建索引,那么就可以提高数据库的性能。这个认识是错误的。给所有的表都创建了索引,那么其反而会给数据库的性能造成负面的影响。因为此时滥用索引的开销可能已经远远大于由此带来的性能方面的收益。

一般来说,不需要为比较小的表创建索引。因为即使建立了索引,其性能也不会得到很大的改善。相反索引建立的开销,如维护成本等等,要比这个要大。也就是说,付出的要比得到的多,显然违反常理。

另外,就是对于超大的表,也不一定要建立索引。有些表虽然比较大,记录数量非常的多。但是此时为这个表建立索引并一定的合适。对于一些超大的表,建立索引有时候往往不能够达到预计的效果。而且在大表上建立索引,其索引的开销要比普通的表大的多

那么到底是否给大表建立索引呢?主要是看两个方面的内容。首先是需要关注一下,在这张大表中经常需要查询的记录数量。一般来说,如果经常需要查询的数据不超过10%到15%的话,那就没有必要为其建立索引的必要。因为此时建立索引的开销可能要比性能的改善大的多。如果数据库管理员需要得出一个比较精确的结论,那么就需要进行测试分析。

总结:

  1. 过小的表不需要创建索引,因为性能不会得到很高提升,维护索引的性能反而会增大许多
  2. 过大的表也【不一定】要创建索引,如果查询数据并不是很多,则没有必要创建索引,因为创建索引开销可能比优化查询带来的开销更大
根据列的特征创建索引

列的特点不同,索引创建的效果也不同。需要了解为哪些列创建索引可以起到事半功倍的效果。同时也需要了解为哪些列创建索引反而起到的是事倍功半的效果。

在一个表上创建多少索引合适

通常来说,表的索引越多,其查询的速度也就越快。但是,表的更新速度则会降低。这主要是因为表的更新同时也是索引的更新。

到底在表中创建多少索引合适,就需要在这个更新速度与查询速度之间取得一个均衡点。如对于一些数据仓库或者决策型数据库系统,其主要用来进行查询。相关的记录往往是在数据库初始化的时候导入。此时,设置的索引多一点,可以提高数据库的查询性能。同时因为记录不怎么更新,所以索引比较多的情况下,也不会影响到更新的速度。相反,如果那些表中经常需要更新记录,如一些事务型的应用系统,数据更新操作是家常便饭的事情。此时如果在一张表中建立过多的索引,则会影响到更新的速度。由于更新操作比较频繁,所以对其的负面影响,要比查询效率提升要大的多。此时就需要限制索引的数量,只在一些必要的字段上建立索引。

总结:

  1. 如果数据库经常进行查询操作,那么设置多点索引可以提高数据库查询性能
  2. 如果数据库经常进行更新操作,由于插入删除操作十分繁琐,就会导致数据库性能下降许多

两种索引的本质区别

设:一个记录在磁盘上占用1000字节;一个页在磁盘上占用8000字节;

  • 非聚簇索引

假设有一8000条记录的表,表中每条记录在磁盘上占用1000字节,如果在一个10字节长的字段上建立非聚簇索引主键,需要二叉树节点16000个(这16000个节点中有8000个叶节点,每个页节点都指向一个数据记录),这样数据将占用8000条×1000字节/8K字节=1000个页面;

索引将占用16000个节点×10字节/8K字节=20个页面,共计1020个页面。

  • 聚簇索引

同样一张表,如果我们在对应字段上建立聚簇索引主键,由于聚簇索引的页节点就是数据节点,则所以索引节点仅有8000个,占用10个页面,数据仍然占有1000(8000条数据 × 1000字节 / 8K字节 = 1000)个页面,共计1010个页面

假设现在进行【插入操作】,主键约束要求主键不能出现重复,如何保证不出现重复?进行检索

  • 非聚簇索引:只需要检索索引,因为索引包含了所有主键值(检索20个页面)
  • 聚簇索引:检索8000个索引以及索引对应的8000条数据(检索10个页面+1000个页面 = 1010个页面)

得出结论:聚簇索引主键的插入速度要比非聚簇索引主键的插入速度慢很多

假设现在进行【检索操作】(假设要查的数据在最后一项)

  • 非聚簇索引:20个索引页面 + 1000个数据页 = 1020页
  • 聚簇索引:10个索引页面 + 1000个数据页 = 1010页

得出结论:在极端情况,这两种索引查询速度相似。但这种极端情况毕竟是少数,一般来说聚簇索引的查询速度都要快很多,因为一旦具有第一个索引值的纪录被找到,具有连续索引值的记录也一定物理的紧跟其后,从而缩小了搜索范围

InnoDB 逻辑存储结构

事务

四个基本特性 - ACID

Atomicity(原子性),Consistency(一致性),Isolation(隔离性),Durablity(持久性)

  • Atomicity(原子性):事务是一个不可分割的整体,事务内所有操作要么全部提交成功,要么全部失败回滚。
  • Consistency(一致性):事务执行前后,数据从一个状态到另一个状态必须是一致的(A向B转账,不能出现A扣了钱,B却没收到)。
  • Isolation(隔离性):多个并发事务之间相互隔离,不能互相干扰。或者说一个事务所做的修改在最终提交以前,对其他事务是不可见的。
  • Durablity(持久性):事务完成后,对数据库的更改是永久保存的,不能回滚。

并发事务带来的问题

更新丢失

  • 发生场景

T1 和 T2 两个事务都对一个数据进行修改,T1 先修改,T2 随后修改,T2 的修改覆盖了 T1 的修改 。

  • 解决方案

一个线程提交该事务之前,其他线程不能访问这个数据。

脏读

  • 发生场景

T1 修改一个数据,T2 随后读取这个数据。如果 T1 撤销了这次修改,那么 T2 读取的数据是脏数据 。

  • 提交方案

把数据库的事务隔离级别调整到 READ_COMMITTED

不可重复读

  • 发生场景

T2 读取一个数据,T1 对该数据做了修改。如果 T2 再次读取这个数据,此时读取的结果和第一次读取的结果不同 。

  • 提交方案

如果只有在修改事务完全提交之后才可以读取数据,则可以避免该问题。把数据库的事务隔离级别调整到 REPEATABLE_READ

幻读

  • 发生场景

T1 读取某个范围的数据,T2 在这个范围内【插入】新的数据,T1 再次读取这个范围的数据,此时读取的结果和和第一次读取的结果不同。

  • 解决方案

    如果在操作事务完成数据处理之前,任何其他事务都不可以添加新数据,则可避免该问题。把数据库的事务隔离级别调整到 SERIALIZABLE_READ

事务隔离级别

并发事务带来的问题,就需要设置事务隔离级别去解决,总的来说有四种事务隔离级别

以下四个顺序是按照【隔离级别严格程度】从低到高排序的,级别越严格,并发副作用越小,但也会付出更大的代价,因为事务隔离实质上就是事务在一定程度上“串行化”进行,这显然与“并发”是矛盾的。

  1. 未提交度
  2. 提交读
  3. 可重复读
  4. 可串行化

这四种隔离级别能解决的问题如下图所示,有个大概印象(√代表会出现,X代表解决了)

img

Read Uncommitted(未提交读)

最低的隔离等级, 允许其他事务看到没有提交的数据 ,会导致脏读,不可重复读,幻读(即一个问题都没办法解决)

Read Committed(提交读/读已提交)

Read Committed(提交读) 是 SQL Server 默认事务隔离级别。

设立了这种隔离级别后:一个事务只能够看见已经提交事务所做的改变。换句话来说,一个事务从开始直到提交之前,所做的任何修改对于其他的事务来说都是不可见的。

为什么说种隔离级别没有实现可重复读呢?

假设一个事务中进行两次查询,两次查询期间另一个事务进行了数据更新,就导致两次查询结果不一致,没有实现可重复读。

其本质原因在于,读已提交会在每次select的时候生成一次read view,查询结果是根据read view进行一定规则判断得到的。

(具体细节在后面MVCC讲)

Repeatable Read(可重复读)

Repeatable Read(可重复读) 是 MySQL 默认事务隔离级别

设立了这种隔离级别后:所有被 Select 获取的数据都不能被修改,这样就可以避免一个事务前后读取数据不一致的情况 ,解决了脏读问题。

但是却没有办法控制幻读,因为这个时候其他事务不能更改所选的数据,但是可以增加数据,即前一个事务有读锁但是没有范围锁,为什么叫做可重复读级别呢?

那是因为该等级解决了下面的不可重复读问题。(引申:现在主流数据库都使用 MVCC 并发控制,使用之后 RR(可重复读)隔离级别下是不会出现幻读的现象。)

ps:其能解决读已提交问题的本质是由于其生成read view逻辑不一样,之前是每次select生成一次read view,而在RR隔离级别中,每个事务生成一次read view,由于是固定的一份read view,那么一开始read view是什么样,后面就是什么样。所以说就算一个事务有1000句select,查询到的结果都还是一样。这样就解决了不可重复读这个问题。

  • MVCC - 快照读 - 解决幻读:由于select只会生成一次read view,新增数据对read view没影响,因此能解决幻读
  • MVCC - 当前读+间隙锁 - 解决幻读: 间隙锁能把一段范围内数据上锁,不允许写数据(新增数据),因此能解决幻读

简单来说,多版本解决了不可重复读问题,而多版本并发控制(多版本 + 间隙锁)才解决了幻读

Serializable(可串行化)

设立了这种隔离级别后:通过强制事务排序,强制事务【串行】执行,使之不可能发生相互冲突,解决了最后一个幻读问题。

其本质是通过在每个读的数据行上加上了共享锁/S锁

对于基于锁来实现并发控制的数据库来说,串行化要求在执行范围查询的时候,需要获取范围锁,如果不是基于锁实现并发控制的数据库,则检查到有违反串行操作的事务时,需回滚该事务。

这个级别中,可能会导致大量的超时现象和锁竞争,只有非常需要确保数据一致,且可以接受无并发的情况才会考虑该级别。

总结

  • 读未提交: 一个事务还没提交时,它做的变更就能被别的事务看到 。
  • 读提交: 一个事务提交 之后 ,它做的变更 才 会被其他事务看到。
  • 可重复读 : 一个事务执行过程中看到的数据,总是跟这个事务在启动时看到的数据是一致的 。当然在可重复读隔离级别下,未提交变更对其他事务也是不可见的。
  • 串行化: 顾名思义是对于同一行记录,“写”会加“写锁”,“读”会加“读锁”。当出现读写锁冲突的时候,后访问的事务必须等前一个事务执行完成,才能继续执行。

下图为隔离级别与并发性能之间的关系:

隔离级别与并发性能

MVCC - 多版本并发控制

MVCC就是不加锁,而实现加了【排他锁】的功能

概述

  • 多版本

多版本比较好理解就是有多个版本,那么是指的什么有多个版本,这里指的是【数据行】,mysql中的数据行有多个版本,再看后面的并发控制,即对数据的行的读取和更新要并发控制,并发控制的目的是为了多线程下的数据安全,就像在java环境下的多线程安全,这里并不是指线程安全,而是指多个线程下的数据隔离级别。

  • 作用

MVCC只有在【读已提交】【可重复读】两种隔离级别下才有效。

我们都知道在读已提交隔离级别下解决了脏读,但存在不可重复读及幻读的情况,在可重复读隔离级别下解决了不可重复读和幻读(使用快照解决了部分幻读问题,但不能完全解决,最终使用间隙锁才解决的幻读问题)

当前读 和 快照读

当前读

所有操作都加了锁,并且锁之间除了共享锁都是互斥的,如果想要增、删、改、查时都需要等待锁释放才可以,所以读取的数据都是最新的记录。

给读操作加上共享锁、排它锁,增、删、改操作加上排它锁,这些操作就是当前读。

在MySQL的Innodb存储引擎下,增、删、改操作都会默认加上排它锁,所以增、删、改操作默认就为当前读。

快照读

快照读的出现旨在提高事务并发性

简单来说快照读就是不加锁的非阻塞读,即简单的select操作(select * from user)

非阻塞读 (不加锁) = 快照读

在Innodb存储引擎下执行简单的select操作时,会记录下当前的快照读数据,之后的select会沿用第一次快照读的数据,即使有其它事务提交也不会影响当前的select结果,这就解决了不可重复读问题。

快照读读取的数据虽然是一致的,但有可能不是最新的数据而是历史数据。

演示一下区别

  • 快照读
1
2
-- 不加锁的简单select
select id name user where id = 1;
  • 当前读
1
2
3
4
-- select加上共享锁、排它锁。
select id name from user where id = 1 lock in share mode;

select id name from user where id = 1 for update;

原理

MVCC的实现是通过两个隐式字段、undo log(回滚日志)和 ReadView来实现的

隐式字段

在Innodb存储引擎中,在有聚簇索引的情况下每一行记录中都会隐藏俩个字段,如果没有聚簇索引则还有一个6byte的隐藏主键。

这俩个隐藏列一个记录的是何时被创建的,一个记录的是什么时候被删除。

这里存储的并不是实际的时间值,而是系统版本号/事务ID!每开始一个新的事务,系统版本号都会自动递增。事务开始时刻的系统版本号会作为事务的版本号,用来和查询到的每行记录的版本号进行比较

俩个隐式字段为DB_TRX_ID,DB_ROLL_PTR,没有聚簇索引还会有DB_ROW_ID这个字段。

  • DB_TRX_ID:记录创建这条数据上次修改它的事务 ID (每修改一次,相当于重新被创建一次);
  • DB_ROLL_PTR:回滚指针,指向这条记录的上一个版本(回滚一次,那么回滚前记录会被”删除”)

隐式字段实际还有一个delete flag字段,即记录被更新或删除,这里的删除并不代表真的删除,而是将这条记录的delete flag改为true

undo log - 回滚日志

概念

undo log细分为俩种:

  • insert时产生的undo log
  • update,delete时产生的undo log

为什么要这么分呢?

在Innodb中insert产生的undo log在提交事务之后就会被删除,因为新插入的数据没有历史版本,所以无需维护undo log。

update和delete操作产生的undo log都属于一种类型,在事务回滚时需要,而且在快照读时也需要,则需要维护多个版本信息。只有在快照读和事务回滚不涉及该日志时,对应的日志才会被purge线程统一删除。

purge线程会清理undo log的历史版本,同样也会清理del flag标记的记录。

undo log作用

上面提到了DB_ROLL_PTR(回滚指针),一个个回滚指针串联一个个版本,就能维护成一个【版本链】

undo log就保存着这个版本链。

当数据库执行一个select语句时会产生一致性视图read view,来决定当前事务能看到的是哪个版本的数据。有可能是当前最新版本的数据,也有可能是undo log中某个版本的数据。

所以说undo log在mvcc中的作用就是存储了事务发生之前的数据的一个版本,用于回滚。

由于undo log中有一个记录多个版本,因此可以用于MVCC中对于数据历史版本的查看

底层实现/例子

假设一开始的数据为下图

开始数据

此时执行了一条更新的SQL语句update user set name = 'niuniu' where id = 1,那么undo log的记录就会发生变化

当执行一条更新语句时会把之前的原有数据拷贝到undo log日志中。

同时你可以看见最新的一条记录在末尾处连接了一条线,也就是说DB_ROLL_PTR记录的就是存放在undo log日志的指针地址。

最终有可能需要通过指针来找到历史数据。

undo log变化

ReadView

上面说到:当数据库执行一个【select语句】时会产生一致性视图read view

read view是由以下部分组成:

  1. m_ids:查询时所有未提交事务ID组成的数组

  2. min_trx_id:数组中最小的事务ID

  3. max_trx_id:已创建(提交和未提交)的最大事务ID为max_id,也表示生成read view时系统中应分配给下一个事务的id值

  4. creator_trx_id:生成该read view的事务的事务id

用一句话来说:ReadView的作用就是在版本链中挑选一个记录作为select的版本

版本链对比规则

那么怎么对比呢?

InnoDB为每个事务构造一个数组,保存这个事务启动瞬间,当前正在“活跃”的所有事务ID。

每对该数据进行一DML操作(查询不包含在内),事务ID都 + 1

数组里面事务ID的最小值记为低水位,当前系统里面已经创建过的事务ID的最大值记为高水位。

这视图数组和高水位,就组成为当前事务的一致性视图(read-view)。

而数据版本的可见性规则,就基于数据的row trx_id和这个一致性视图的对比结果得到。

数据版本可见性规则

考虑当前事务的启动瞬间,一个数据版本的trx_id,可能有以下几种情况:

再提醒一次:trx_id 是事务的id(transition_id)

  1. 落在绿色(trx_id<min_id),表明该版本是由已提交的事务或当前事务自己生成的,这个数据更新结果自然是可见的

  2. 落在红色(trx_id>max_id),该版本由将来启动的事务生成,不可见

  3. 落在黄色(min_id<=trx_id<=max_id),包括两种情况

    1. 若trx_id在数组中,表示这个版本是由还没提交的事务生成,不可见,但是当前自己的事务是可见的。

    2. 若trx_id不在数组中,表示这个版本是已经提交了的事务生成,可见

      比方说现在的数组是[1 3 4 5],没有2,说明2是commit的 了,如果trx_id也是2,那就可以访问

若是trx_id == creato_trx_id:那么当前事务就是我自己创建的,那肯定可以读取;

还有一个特殊情况那就是对于已经删除的数据,在之前的undo log日志讲述时说了update和delete是同一种类型的undo log,同样也可以认为delete就是update的特殊情况。

当删除一条数据时会将版本链上最新的数据复制一份,然后将trx_id修改为删除时的trx_id,同时在该记录的头信息中存在一个delete flag标记,将这个标记写上true,用来表示当前记录已经删除。

在查询时按照版本链的规则查询到对应的记录,如果delete flag标记位为true,意味着数据已经被删除,则不返回数据。

感觉文字讲的不是很清楚的话,可以看这个视频:https://www.bilibili.com/video/BV1Vk4y1k7KQ?from=search&seid=7266569325761452601&spm_id_from=333.337.0.0

案例分析

参考资料

博客

工具