前面我们说了undo日志在insert，update，delete存储的日志格式，delete存储的type是trx_undo_del_mark_rec里面有个参数old roll_pointer会指向insert的地址值，恢复需要的数据。Select是没有undo日志的，因为select不需要回滚事务。

通用链表结构

在写入undo日志的过程会使用到多个链表，很多链表都有同样的节点结构，

List node结构示意图(一共12个字节)：

Prev Node page number(4个字节)：

Prev node offset（2个字节）：这两个字段相当于指向前一个节点的指针。

Next node page number(4个字节)：

Next node offset（2个字节）：这两个字段相当于指向后一个节点的指针。

在某个表空间内，我们可以通过一个页的页号和在页内的偏移量来定位一个节点的位置，这两个信息也就是相当于指向这个节点的指。所以：

Prev node page number和prev node offset就是指向前一个节点的指针。

Next node page number 和next node offset就是指向后一个节点的指针。

整个list node占用12个字节的存储空间。

为了更好管理链表，设计innoDB的大叔还提出一个基节点的结构， 里面存储着这个链表的头节点、尾节点以及链表长度信息，基节点的结构示意图：

List base node 结构示意图（一共16个字节）：

List length：（4个字节）

First node page number：（4个字节）

First node offset：（2个字节）这两个字段指向链接头节点的指针。

Last node page number：（4个字节）

Last node offset：（2个字节）这两个字段指向链接尾节点的指针。

其中list lenth代表有多少个节点。

而list base node结构有一个start和end，这个就是指向list node这个结构的start节点和end节点。

File_page_undo_log页面

前面唠嗑表空间的时候，其实有许许多多的页面构成，其中默认大小为16kb。比如fil_page_index的页面用于存储聚簇索引和二级索引，类型为fil_page_type_fsp_hdr的页面用于存储表空间头部信息，还有其他各种类型的页面，其中有一种是file_page_undo_log类型的页面专门用来存储undo日志的，默认16kb，他的结构如下：

File header：38个字节。

Undo page header：18个字节。

File body：这里都是真实存放undo日志的地方。

File trailder：8个字节。

File header 和file trailder都类似，就不介绍了，里面大致有lsn值，用于效验文件是否完整，header有组成双向链表的字段，prev和next等。

这里介绍一下undo page header：

TRX_UNDO_PAGE_TYPE：2个字节，本页面准备存储什么种类的undo日志。

我们介绍了好几种undo日志，大致分为两大类：

Trx_undo_insert（使用十进制1表示）：类型是trx_undo_insert_rec的undo日志属于这个类， 一般insert语句产生，其中update语句更新主键的时候也会产生。

Trx_undo_update（使用十进制2表示）：除了trx_undo_insert_rec的undo日志外，其他undo日志都属于此类，一般是update 和 delete产生的。

所以如果存储着trx_undo_insert的类，就只能存放trx_undo_insert_rec的undo日志。为什么要分为两大类呢，因为trx_undo_insert_rec可以直接删除，而其他类型的删除是delete mark，还需要为其他事物服务，这就是MVCC,后面会详细介绍。

Trx_undo_page_start：表示在当前页面从什么位置开始存储undo日志的，或者说表示条undo日志在页面中起始偏移量。

Trx_undo_page_free：与上面的start对应，存入后一个undo日志的偏移量，可以继续存入undo日志的地址值。（当然，在初一条undo日志未写入的时候，两个字段是相同的）

Trx_undo_page_node：代表一个list node结构（链表的普通节点）。

UNDO页面链表

单个事务中的undo页面链表

一个事务可能包含多个sql语句，而一个sql语句可能对多条记录进行改动，而每条记录的改动，都可能会记录1条或者2条undo日志，所以在一个事务里会产生很多undo日志，可能一个页面放不下需要放入多个页面，通过TRX_undo_page_node属性连接成了链表

我们吧undo页面个称为first undo page，其余的undo页面称为normal undo page，这是因为first undo page 中除了记录undo page header外，还会记录一些管理信息。

在一个事务中，可能混着执行insert update delete，意味着产生不同的undo日志，但我们前面说过，同一个undo要么存在trx_undo_insert或者存在trx_undo_update，反正不能混着存，所以一个事务里就需要两个undo链表，一个称为insert undo链表，另一个称为update undo链表。

另外有规定，普通表和临时表的链表要分开存储，所以就有了四个链表。

当然不是事务开启的时候就分配这四个链表，当对普通表或者临时表操作的时候，才会分配相对应的链表。总之按需分配，啥时候执行了update 或者 insert，delete就分配，如果没有执行，就不分配。

多个事务中的undo页面链表

为了提高undo日志分配效率，可以不同事务同事运行，不同事务运行的情况下，会给不同的事务分配不同的链表。

列子：

Trx1：运行了update了普通表，insert了临时表

则会有在trx1里分配临时表的trx_undo_insert链表和普通表的trx_undo_update链表。

Trx2：运行了insert普通表

则会有在trx里分配普通表的trx_undo_insert链表

如果有更多的事务，意味着有更多的链表。

Undo日志具体写入过程

段（segment）的概念

前面段的概念介绍过，一个索引会有内节点和叶子节点，所以有两个段，段是由零散的页和完整的区组成。每个段都对应inode entry结构，这个inode entry里面有各种信息，比如段的id，段内各种链表基节点，零散页面有哪些信号等，我们前面说了inode entry有一个segment header：

他的大小是10个字节，

Space id of the inode entry：所在的表空间id。

Page number of the inode entry：inode entry 结构所在的页面页号

Byte offset of the inode entry：inode entry结构在页面中的偏移量。

知道了表空间，页号以及偏移量，就可以找到他对应的inode entry地址了。

Undo log segment header

innoDB规定每undo页面都对应一个段，称为undo log segment。也就是链表里的页面都是从这个段里申请的，也就是first undo page中设计了一个称为undo log segment header 的部分：

file heard：38个字节。

Undo page header：18个字节。

Undo log segment header：30个字节。

Body：存放真正的undo日志及其其他东西。

File trailer：8个字节。

可以看到这个undo链表比其他普通页面多了undo log segment header：

Trx_undo_state：本undo页面链表处在的状态。

一个undo log segment处在的状态包括：

Trx_undo_active:活跃状态，也就是一个活跃的事务也在往这个段里写undo日志。

Trx_undo_cache:被缓存的状态。处在该状态的undo页面链表等待着之后被其他事务重用。

Trx_undo_to_free：对于insert undo链表来说，如果他对应的事务提交后，该链表不能被重用，那么久处于这种状态。

Trx_undo_prepared：包含处在prepare阶段的事务产生的undo日志。

注意：prepared阶段是在分布式事务中才出现的。

Trx_undo_last_log：本undo页面链表中后一个undo log header 位置。

Trx_undo_fseg_header：本undo页面链表对应的段segment_header信息（就是前面说的10个字节的结构，可以找到对应的inode entry）。

Trx_undo_page_list：undo页面链表的基节点。

我们前面说了undo页面的undo page header部分有一个12字节大小的trx_undo_page_node的属性，这个代表list node结构。每一个undo页面都包含undo page header 结构，可以连接成一个链表。Trx_undo_page_list就是基节点，当然这个只存在个页面，first undo page。

Undo log header

事务往undo页面写入undo日志是直接往里面怼，各个日志亲密无间。写完一个undo页面后，再从段里申请新的页面，然后把这个页面插入undo页面链表中，继续往这个新申请的页面中写。innoDB认为同一个事务向一个链表插入的undo日志为一组，比如trx1事务里有两组，trx2事务里有三组。在每组写入undo日志时，都会记录一些这个组的属性，存储这些属性的地方称为undo log header。所以在真正写入undo日志之前，其实需要填充undo page header、undo log segment header，undo log header。

它的具体结构：

Trx_undo_trx_id：生成本组的undo日志事务id。

Trx_undo_trx_no：事务提交后生成一个需要的序号，使用此序号来标记事务提交顺序。（先提交小的后提交大的）

Trx_undo_del_marks：标记本组undo日志中是否包含delete mark操作的undo日志。

Tra_undo_log_start：本组undo日志中条undo日志在页面中的偏移量。

Trx_undo_xid_exists：本组undo日志是否包含xid。

Trx_undo_dict_trans：标记本组undo日志是不是由DDL语句产生的。

Trx_undo_table_id：如果trx_undo_dict_trans为真，那么本属性表示DDL语句操作的表table id。

Trx_undo_next_log：下一组undo日志在页面的偏移量。

Trx_undo_prev_log：上一组undo日志在页面的偏移量。

Trx_undo_history_node：一个12个字节的list node 结构，代表一个称为history链表的节点。

综上，对于没有重用的undo链表来说，也就是个first undo page在真正写入undo日志之前，会填充undo page header、undo log segment header，undo log header这三个部分才开始正式写入undo日志。对于剩余的其他normal_undo_page来说，真正写入之前，会先填充undo page header。链表的list base node存在first undo page的undo log segment header部分，list node会存放在每一个undo页面的undo page header部分。