索引

背景

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

磁盘

关于磁盘

局部性原理与磁盘预读

局部性原理

在 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 算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。

存储结构

struct B_TNode{
    int numOfKey;//关键字个数 - 文件数
    B_TNode *parent;//指向父结点的指针
    B_TNode **childPtr;//指向子树的指针，childPtr[0]...childPtr[numOfKey]
    int *key;//指向关键字数组的指针
};

特点

每个节点最多有m 个孩子（m>=2）。
每个非叶节点（根除外）至少有 ⌈ m /2⌉ （向上取整）个子节点。
如果根不是叶节点，则根至少有两个子节点。
一个有k 个孩子的非叶节点包含k − 1 个键，即孩子树为 3 的话，关键字个数为 2，前者为 4 的话，后者为 3，以此类推。
所有叶子都出现在同一层，不携带任何信息。

B-树的查找

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);
    }
}

查找过程

下面，咱们来模拟下查找文件 29 的过程：

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

B+树

有 k 个子树的中间节点包含有 k 个元素（B 树中是 k-1 个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。（链表）

所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

B+树查找时是从上到下查找；B-树则是从下往上查找（中序遍历）

B+树

B+树的优势

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

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

3.所有叶子节点成有序链表，便于范围查询。
为什么说 B+树比 B 树更适合实际应用中操作系统的文件索引和数据库索引？

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

聚簇索引与非聚簇索引

在《数据库原理》里面，

对聚簇索引的解释是:聚簇索引的顺序就是数据的物理存储顺序

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

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

引言的描述非常抽象，我们可以理解成：聚簇索引的叶结点就是数据结点；而非聚簇索引的叶结点仍然是索引节点（包含一个指向数据库的指针）

聚簇索引

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

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

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

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

聚簇索引

特点

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

非聚簇索引

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

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

非聚簇索引

特点

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

聚簇索引建立在哪？

理解

聚簇索引

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

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

非聚簇索引

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

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

总结：

对于经常要搜索范围值的列，应该使用建立聚簇索引

从表中检索出来数据，后期要进行排序时，应该建立索引聚簇，避免后期排序，节省成本

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

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

建立索引的要求

根据表的大小创建索引

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

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

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

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

总结：

过小的表不需要创建索引，因为性能不会得到很高提升，维护索引的性能反而会增大许多

过大的表也【不一定】要创建索引，如果查询数据并不是很多，则没有必要创建索引，因为创建索引开销可能比优化查询带来的开销更大

根据列的特征创建索引

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

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

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

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

总结：

如果数据库经常进行查询操作，那么设置多点索引可以提高数据库查询性能

如果数据库经常进行更新操作，由于插入删除操作十分繁琐，就会导致数据库性能下降许多

两种索引的本质区别

设：一个记录在磁盘上占用 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。

事务隔离级别

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

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

未提交度
提交读
可重复读
可串行化

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

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;

当前读

-- 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是由以下部分组成：

m_ids：查询时所有未提交事务 ID组成的数组
min_trx_id：数组中最小的事务 ID
max_trx_id：已创建（提交和未提交）的最大事务 ID 为 max_id，也表示生成read view时系统中应分配给下一个事务的 id 值
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）

落在绿色（trx_id<min_id），表明该版本是由已提交的事务或当前事务自己生成的，这个数据更新结果自然是可见的
落在红色（trx_id>max_id），该版本由将来启动的事务生成，不可见
落在黄色（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

案例分析

参考资料

博客

（索引 - 树）https://notes.diguage.com/mysql/#_%E6%A0%91
（b 树和 b+树）https://www.cnblogs.com/ivictor/p/5849061.html
（B 树、B+树学习）https://blog.csdn.net/qq_34533266/article/details/112790436
（B 树和 B+树的区别）https://blog.csdn.net/a519640026/article/details/106940115
（漫画图解 B 树与 B+树）https://blog.csdn.net/qq_35571554/article/details/82759668?utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-1.baidujs&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-1.baidujs
（四种事务隔离级别）http://blog.itpub.net/26736162/viewspace-2638951/
（MVCC）https://www.cnblogs.com/fkaka/p/14708285.html

工具

（二叉搜索时可视化工具）https://www.cs.usfca.edu/~galles/visualization/BST.html

索引

背景

磁盘

局部性原理与磁盘预读

B+Tree（Balance - Plus - Tree）

二叉搜索树

平衡二叉查找树

B-树（Balance-Tree）

概述

存储结构

特点

B-树的查找

B+树

聚簇索引 与 非聚簇索引

聚簇索引

非聚簇索引

聚簇索引建立在哪？

理解

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

建立索引的要求

根据表的大小创建索引

根据列的特征创建索引

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

两种索引的本质区别

InnoDB 逻辑存储结构

事务

四个基本特性 - ACID

并发事务带来的问题

更新丢失

脏读

不可重复读

幻读

事务隔离级别

Read Uncommitted(未提交读)

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

Repeatable Read(可重复读)

Serializable(可串行化)

总结

MVCC - 多版本并发控制

概述

当前读 和 快照读

当前读

快照读

演示一下区别

原理

隐式字段

undo log - 回滚日志

概念

undo log 作用

底层实现/例子

ReadView

版本链对比规则

案例分析

参考资料

博客

工具

聚簇索引与非聚簇索引

当前读和快照读