MySQL InnoDB 引擎現在廣為使用，它提供了事務，行鎖，日志等一系列特性，本文分析下 InnoDB 的內部實現機制，MySQL 版本為 5.7.24，操作系統為 Debian 9。

MySQL InnoDB 的實現非常復雜，本文只是總結了一些皮毛，希望以后能夠研究的更加深入些。

1、InnoDB 架構

Innodb 架構圖

InnoDB 的架構分為兩塊：內存中的結構和磁盤上的結構。InnoDB 使用日志先行策略，將數據修改先在內存中完成，并且將事務記錄成重做日志(Redo Log)，轉換為順序IO高效的提交事務。

這里日志先行，說的是日志記錄到數據庫以后，對應的事務就可以返回給用戶，表示事務完成。但是實際上，這個數據可能還只在內存中修改完，并沒有刷到磁盤上去。內存是易失的，如果在數據落地前，機器掛了，那么這部分數據就丟失了。

InnoDB 通過 redo 日志來保證數據的一致性。如果保存所有的重做日志，顯然可以在系統崩潰時根據日志重建數據。

當然記錄所有的重做日志不太現實，所以 InnoDB 引入了檢查點機制。即定期檢查，保證檢查點之前的日志都已經寫到磁盤，則下次恢復只需要從檢查點開始。

2、InnoDB 內存中的結構

內存中的結構主要包括 Buffer Pool，Change Buffer、Adaptive Hash Index以及 Log Buffer 四部分。

如果從內存上來看，Change Buffer 和 Adaptive Hash Index 占用的內存都屬于 Buffer Pool，Log Buffer占用的內存與 Buffer Pool獨立。

Buffer Pool

緩沖池緩存的數據包括Page Cache、Change Buffer、Data Dictionary Cache等，通常 MySQL 服務器的 80% 的物理內存會分配給 Buffer Pool。

基于效率考慮，InnoDB中數據管理的最小單位為頁，默認每頁大小為16KB，每頁包含若干行數據。

為了提高緩存管理效率，InnoDB的緩存池通過一個頁鏈表實現，很少訪問的頁會通過緩存池的 LRU 算法淘汰出去。

InnoDB 的緩沖池頁鏈表分為兩部分：New sublist(默認占5/8緩存池) 和 Old sublist(默認占3/8緩存池，可以通過 innodb_old_blocks_pct修改，默認值為 37)，其中新讀取的頁會加入到 Old sublist的頭部，而 Old sublist中的頁如果被訪問，則會移到 New sublist的頭部。

緩沖池的使用情況可以通過 show engine innodb status 命令查看。其中一些主要信息如下： 

----------------------  
BUFFER POOL AND MEMORY  
----------------------  
Total large memory allocated 137428992 # 分配給InnoDB緩存池的內存(字節)  
Dictionary memory allocated 102398  # 分配給InnoDB數據字典的內存(字節)  
Buffer pool size   8191 # 緩存池的頁數目  
Free buffers       7893 # 緩存池空閑鏈表的頁數目  
Database pages     298  # 緩存池LRU鏈表的頁數目  
Modified db pages  0    # 修改過的頁數目  
...... 

Change Buffer

通常來說，InnoDB輔助索引不同于聚集索引的順序插入，如果每次修改二級索引都直接寫入磁盤，則會有大量頻繁的隨機IO。Change buffer 的主要目的是將對 非唯一 輔助索引頁的操作緩存下來，以此減少輔助索引的隨機IO，并達到操作合并的效果。它會占用部分Buffer Pool 的內存空間。

在 MySQL5.5 之前 Change Buffer其實叫 Insert Buffer，最初只支持 insert 操作的緩存，隨著支持操作類型的增加，改名為 Change Buffer。

如果輔助索引頁已經在緩沖區了，則直接修改即可；如果不在，則先將修改保存到 Change Buffer。Change Buffer的數據在對應輔助索引頁讀取到緩沖區時合并到真正的輔助索引頁中。Change Buffer 內部實現也是使用的 B+ 樹。

可以通過 innodb_change_buffering 配置是否緩存輔助索引頁的修改，默認為 all，即緩存 insert/delete-mark/purge 操作(注：MySQL 刪除數據通常分為兩步，第一步是delete-mark，即只標記，而purge才是真正的刪除數據)。

查看Change Buffer 信息也可以通過 show engine innodb status 命令。更多信息見 

-------------------------------------  
INSERT BUFFER AND ADAPTIVE HASH INDEX  
-------------------------------------  
Ibuf: size 1, free list len 0, seg size 2, 0 merges  
merged operations:  
 insert 0, delete mark 0, delete 0  
discarded operations:  
 insert 0, delete mark 0, delete 0  
Hash table size 34673, node heap has 0 buffer(s)  
Hash table size 34673, node heap has 0 buffer(s)  
Hash table size 34673, node heap has 0 buffer(s)  
Hash table size 34673, node heap has 0 buffer(s)  
Hash table size 34673, node heap has 0 buffer(s)  
Hash table size 34673, node heap has 0 buffer(s)  
Hash table size 34673, node heap has 0 buffer(s)  
Hash table size 34673, node heap has 0 buffer(s) 

Adaptive Hash Index

自適應哈希索引(AHI)查詢非常快，一般時間復雜度為 O(1)，相比 B+ 樹通常要查詢 3~4次，效率會有很大提升。innodb 通過觀察索引頁上的查詢次數，如果發現建立哈希索引可以提升查詢效率，則會自動建立哈希索引，稱之為自適應哈希索引，不需要人工干預，可以通過 innodb_adaptive_hash_index 開啟，MySQL5.7 默認開啟。

考慮到不同系統的差異，有些系統開啟自適應哈希索引可能會導致性能提升不明顯，而且為監控索引頁查詢次數增加了多余的性能損耗， MySQL5.7 更改了 AHI 實現機制，每個 AHI 都分配了專門分區，通過 innodb_adaptive_hash_index_parts配置分區數目，默認是8個，如前一節命令列出所示。

Log Buffer

Log Buffer是 重做日志在內存中的緩沖區，大小由 innodb_log_buffer_size 定義，默認是 16M。一個大的 Log Buffer可以讓大事務在提交前不必將日志中途刷到磁盤，可以提高效率。如果你的系統有很多修改很多行記錄的大事務，可以增大該值。

配置項 innodb_flush_log_at_trx_commit 用于控制 Log Buffer 如何寫入和刷到磁盤。注意，除了 MySQL 的緩沖區，操作系統本身也有內核緩沖區。

•  默認為1，表示每次事務提交都會將 Log Buffer 寫入操作系統緩存，并調用配置的 “flush” 方法將數據寫到磁盤。

          設置為 1 因為頻繁刷磁盤效率會偏低，但是安全性高，最多丟失 1個 事務數據。

          而設置為 0 和 2 則可能丟失 1秒以上 的事務數據。

•  為 0 則表示每秒才將 Log Buffer 寫入內核緩沖區并調用 “flush” 方法將數據寫到磁盤。
•  為 2 則是每次事務提交都將 Log Buffer寫入內核緩沖區，但是每秒才調用 “flush” 將內核緩沖區的數據刷到磁盤。

配置不同的值效果如下圖所示：

innodb_flush_log_at_timeout 可以配置刷新日志緩存到磁盤的頻率，默認是1秒。注意刷磁盤的頻率并不保證就正好是這個時間，可能因為MySQL的一些操作導致推遲或提前。

而這個 “flush” 方法并不是C標準庫的 fflush 方法(fflush是將C標準庫的緩沖寫到內核緩沖區，并不保證刷到磁盤)，它通過 innodb_flush_method 配置的，默認是 fsync，即日志和數據都通過 fsync 系統調用刷到磁盤。

可以發現，InnoDB 基本每秒都會將 Log buffer落盤。而InnoDB中使用的 redo log 和 undo log，它們是分開存儲的。

redo log在內存中有log buffer，在磁盤對應ib_logfile文件。而undo log是記錄在表空間ibd文件中的，InnoDB為undo log會生成undo頁，對undo log本身的操作（比如向undo log插入一條記錄），也會記錄redo log，因此undo log并不需要馬上落盤。而 redo log 則通常會分配一塊連續的磁盤空間，然后先寫到log buffer，并每秒刷一次磁盤。

redo log 必須在數據落盤前先落盤(Write Ahead Log)，從而保證數據持久性和一致性。而數據本身的修改可以先駐留在內存緩沖池中，再根據特定的策略定期刷到磁盤。

3、InnoDB 磁盤上的結構

•  表空間：

          分為系統表空間(MySQL 目錄的 ibdata1 文件)，臨時表空間，常規表空間，Undo 表空間以及 file-per-table 表空間(MySQL5.7默認打開file_per_table 配置）。

          系統表空間又包括了InnoDB數據字典，雙寫緩沖區(Doublewrite Buffer)，修改緩存(Change Buffer），Undo日志等。

•  Redo日志：

         存儲的就是 Log Buffer 刷到磁盤的數據。

為了后面測試方便，我們先建立一個測試數據庫 test，然后建立一個測試表 t。 

mysql> create database test;  
mysql> use test;  
mysql> create table t (id int auto_increment primary key, ch varchar(5000));  
mysql> insert into t (ch) values('abc');  
mysql> insert into t (ch) values('defgh'); 

建立完成后，可以在 MySQL 目錄中看到 test 數據庫目錄，然后里面有 db.opt， t.frm 和 t.ibd 3個文件。其中 db.opt 保存了數據庫test的默認字符集 utf8mb4 和校驗方法 utf8mb4_general_ci，t.frm 是表的數據字典信息(InnoDB數據字典信息主要是存儲在系統表空間ibdata1文件中，由于歷史原因才在 t.frm 多保留了一份)，t.ibd是表的數據和索引。

3.1 InnoDB 表結構

InnoDB 與 MyISAM 不同，它在系統表空間存儲數據字典信息，因此它的表不能像 MyISAM 那樣直接拷貝數據表文件移動。MySQL5.7 采用的文件格式是 Barracuda，它支持 COMPACT 和 DYNAMIC 這兩種新的行記錄格式。創建表時可以通過 ROW_FORMAT 指定行記錄格式，默認是 DYNAMIC。可以通過命令 SHOW TABLE STATUS 查看表信息，此外，也可使用 SELECT * FROM INFORMATION_SCHEMA.INNODB_SYS_TABLES WHERE NAME='test/t' 查看。 

mysql> SHOW TABLE STATUS FROM test LIKE 't' \G  
*************************** 1. row ***************************  
           Name: t  
         Engine: InnoDB  
        Version: 10  
     Row_format: Dynamic  
           Rows: 2  
 Avg_row_length: 8192  
    Data_length: 16384  
Max_data_length: 0  
   Index_length: 0  
      Data_free: 0  
 Auto_increment: 3  
    Create_time: 2019-01-13 02:24:52  
    Update_time: 2019-01-13 02:28:16  
     Check_time: NULL  
      Collation: utf8mb4_general_ci  
       Checksum: NULL  
 Create_options:   
        Comment:   
1 row in set (0.00 sec) 

InnoDB表使用上有一些限制，如一個表最多只能有64個輔助索引，一行大小不能超過65535等，組合索引不能超過16個字段等，一般應該不會突破限制，詳細見 innodb-restrictions。

3.2 InnoDB 表空間概述

表空間根據類型可以分為系統表空間，File-Per-Table 表空間，常規表空間，Undo表空間，臨時表空間等。本節分析 File-Per-Table 表空間。

•  系統表空間：

          包含內容有數據字典，雙寫緩沖，修改緩沖以及undo日志，以及在系統表空間創建的表的數據和索引。

•  常規表空間：

          類似系統表空間，也是一種共享的表空間，可以通過 CREATE TABLESPACE 創建常規表空間，多個表可共享一個常規表空間，也可以修改表的表空間。

注意：必須刪除常規表空間中的表后才能刪除常規表空間。 

CREATE TABLESPACE `ts1` ADD DATAFILE 'ts1.ibd' Engine=InnoDB;  
CREATE TABLE t1 (c1 INT PRIMARY KEY) TABLESPACE ts1;  
CREATE TABLE t2 (c2 INT PRIMARY KEY) TABLESPACE ts1;  
ALTER TABLE t2 TABLESPACE=innodb_file_per_table;  
DROP TABLE t1;  
DROP TABLESPACE ts1; 

•  File-Per-Table表空間：

          MySQL InnoDB新版本提供了 innodb_file_per_table 選項，每個表可以有單獨的表空間數據文件(.ibd)，而不是全部放到系統表空間數據文件 ibdata1 中。

          在 MySQL5.7 中該選項默認開啟。

•  其他表空間：

          其他表空間中Undo表空間存儲的是Undo日志。

           除了存儲在系統表空間外，Undo日志也可以存儲在單獨的Undo表空間中。

          臨時表空間則是非壓縮的臨時表的存儲空間，默認是數據目錄的 ibtmp1 文件，所有臨時表共享，壓縮的臨時表用的是 File-Per-Table 表空間。

表空間文件結構上分為段、區、頁。

•  段(Segment)分為索引段，數據段，回滾段等。其中索引段就是非葉子結點部分，而數據段就是葉子結點部分，回滾段用于數據的回滾和多版本控制。一個段包含256個區(256M大小)。
•  區是頁的集合，一個區包含64個連續的頁，默認大小為 1MB (64*16K)。
•  頁是 InnoDB 管理的最小單位，常見的有 FSP_HDR，INODE, INDEX 等類型。所有頁的結構都是一樣的，分為文件頭(前38字節)，頁數據和文件尾(后8字節)。頁數據根據頁的類型不同而不一樣。
  
  •   FILE_SPACE_HEADER 頁：用于存儲區的元信息。ibd文件的第一頁 FSP_HDR 頁通常就用于存儲區的元信息，里面的256個 XDES(extent descriptors) 項存儲了256個區的元信息，包括區的使用情況和區里面頁的使用情況。
  •   IBUF_BITMAP 頁：用于記錄 change buffer的使用情況。
  •   INODE 頁：用于記錄文件段(FSEG)的信息，每頁有85個INODE entry，每個INODE entry占用192字節，用于描述一個文件段。每個INODE entry包括文件段ID、屬于該段的區的信息以及碎片頁數組。區信息包括 FREE(完全空閑的區), NOT_FULL(至少使用了一個頁的區), FULL(沒空閑頁的區)三種類型的區的List Base Node(包含鏈表長度和頭尾頁號和偏移的結構體)。碎片頁數組則是不同于分配整個區的單獨分配的32個頁。
  •   INDEX 頁：索引頁的葉子結點的data就是數據，如聚集索引存儲的行數據，輔助索引存儲的主鍵值。

3.3 InnoDB File-Per-Table表空間

采用 File-Per-Table 的優缺點如下：

•  優點：

         可以方便回收刪除表所占的磁盤空間。

         如果使用系統表空間的話，刪除表后空閑空間只能被 InnoDB 數據使用。

         TRUNCATE TABLE 操作會更快。

         可以單獨拷貝表空間數據到其他數據庫(使用 transportable tablespace 特性)，可以更方便的觀測每個表空間數據的大小。

•  缺點：

          fsync 操作需要作用的多個表空間文件，比只對系統表空間這一個文件進行fsync操作會多一些 IO 操作。

         此外，mysqld需要維護更多的文件描述符。

表空間文件結構

InnoDB 表空間文件 .ibd 初始大小為 96K，而InnoDB默認頁大小為 16K，頁大小也可以通過 innodb_page_size 配置為 4K, 8K…64K 等。在ibd文件中，0-16KB偏移量即為0號數據頁，16KB-32KB的為1號數據頁，以此類推。頁的頭尾除了一些元信息外，還有Checksum校驗值，這些校驗值在寫入磁盤前計算得到，當從磁盤中讀取時，重新計算校驗值并與數據頁中存儲的對比，如果發現不同，則會導致 MySQL 崩潰。

ibd文件存儲結構如下所示：

ibd文件存儲結構

InnoDB頁分為INDEX頁、Undo頁、系統頁，IBUF_BITMAP頁, INODE頁等多種。

•  第0頁是 FSP_HDR 頁，主要用于跟蹤表空間，空閑鏈表、碎片頁以及區等信息。
•  第1頁是 IBUF_BITMAP 頁，保存Change Buffer的位圖。
•  第2頁是 INODE 頁，用于存儲區和單獨分配的碎片頁信息，包括FULL、FREE、NOT_FULL 等頁列表的基礎結點信息(基礎結點信息記錄了列表的起始和結束頁號和偏移等)，這些結點指向的是 FSP_HDR 頁中的項，用于記錄頁的使用情況，它們之間關系如下圖所示。
•  第3頁開始是索引頁 INDEX(B-tree node)，從 0xc000(每頁16K) 開始，后面還有些分配的未使用的頁。

可以在 innodb_sys_tables 表中查到表t的表空間ID為28，然后可以在 innodb_buffer_page查到所有頁信息，一共4個頁。分別是 FSP_HDR, IBUF_BITMAP, INODE, INDEX。 

select * from information_schema.innodb_sys_tables where name='test/t';  
select * from information_schema.innodb_buffer_page where SPACE=28; 

索引頁分析

InnoDB引擎索引頁的結構如下圖，可以用 hexdump查看 t.ibd 文件，然后對照InnoDB頁的結構分析下各個頁的字段。

索引頁結構 

# hexdump -C t.ibd  
0000c000  95 45 82 8a 00 00 00 03  ff ff ff ff ff ff ff ff  |.E..............|  
0000c010  00 00 00 00 00 28 85 7c  45 bf 00 00 00 00 00 00  |.....(.|E.......|  
0000c020  00 00 00 00 00 1c 00 02  00 b0 80 04 00 00 00 00  |................|  
0000c030  00 9a 00 02 00 01 00 02  00 00 00 00 00 00 00 00  |................|  
0000c040  00 00 00 00 00 00 00 00  00 2f 00 00 00 1c 00 00  |........./......|  
0000c050  00 02 00 f2 00 00 00 1c  00 00 00 02 00 32 01 00  |.............2..|  
0000c060  02 00 1c 69 6e 66 69 6d  75 6d 00 03 00 0b 00 00  |...infimum......|  
0000c070  73 75 70 72 65 6d 75 6d  03 00 00 00 10 00 1b 80  |supremum........|  
0000c080  00 00 01 00 00 00 00 05  68 d1 00 00 01 54 01 10  |........h....T..|  
0000c090  61 62 63 05 00 00 00 18  ff d6 80 00 00 02 00 00  |abc.............|  
0000c0a0  00 00 05 69 d2 00 00 01  55 01 10 64 65 66 67 68  |...i....U..defgh|  
0000c0b0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|  
*  
0000fff0  00 00 00 00 00 70 00 63  95 45 82 8a 00 28 85 7c  |.....p.c.E...(.||  
00010000  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................| 

•  FIL Header（38字節): 記錄文件頭信息。前4字節 95 45 82 8a 是 checksum，接著 00 00 00 03 是頁偏移值 3，即這是第3頁。接著 4 字節是上一頁偏移值，因為只有一個數據頁，所以這里為 ff ff ff ff，接著 4 字節是下一頁偏移值 ff ff ff ff。然后 8 字節 00 00 00 00 00 28 85 7c 是日志序列號 LSN。隨后的 2 字節45 bf是頁類型，代表是 INDEX 頁。接著 8 字節00 00 00 00 00 00 00 00表示被更新到的LSN，在 File-Per-Table 表空間中都是0。然后 4 字節00 00 00 1c` 表示該數據頁屬于的表t的表空間ID是 0x1c(28)。

•  INDEX Header（36字節): 記錄的是 INDEX 頁的狀態信息。前2字節 00 02 表示頁目錄的 slot 數目為2；接著2字節 00 b0 是頁中第一個記錄的指針。80 04是這頁的格式為DYNAMIC和記錄數4(包括2條System Records我們插入的2條記錄)。接著 00 00是可重用空間首指針，再后面2字節00 00是已刪除記錄數；00 9a是最后插入記錄的位置偏移，即最后插入位置是 0xc09a，即第2條記錄開始地址。00 02 是最后插入的方向，2 表示 PAGE_DIRECTION_RIGHT，即自增長方式插入。00 01 指一個方向連續插入的數量，這里為1。接著的00 02是 INDEX 頁中的真實記錄數，我們只有2條記錄。然后8字節00…00為修改該頁的最大事務ID，這個值只在輔助索引中存在，這里為0。接著2字節00 00為頁在索引樹的層級，0表示葉子結點。最后8個字節 00…2f為索引ID 47(索引ID可以在information_schema.INNODB_SYS_INDEXES 中查詢，可以確認 47 正好是表 t 的主索引)。
•  FSEG Header：這是INDEX頁中的根結點才有的，非根結點的為0。前10字節 00 00 00 1c 00 00 00 02 00 f2 是葉子結點所在段的segment header，分別記錄了葉子結點的表空間ID 0x1c，INODE頁的頁號 2 和 INODE項偏移 0xf2。而后10字節 00 00 00 1c 00 00 00 02 00 32 是非葉子結點所在段的segment header，偏移分別是0xf2 和 0x32，即INODE頁的前2個Entry，文件段ID分別是1和2。FSEG Header中存儲了該 INDEX 頁的INODE項，INODE項里面則記錄了該頁存儲所在的文件段以及文件段頁的使用情況。對于 File-Per-Table情況下，每個單獨的表空間文件的 FSP_HDR 頁負責管理頁使用情況。

FSEG結構關系圖

•  System Records(26字節): 每個 INDEX 頁都有兩條虛擬記錄 infimum 和 supremum，用于限定記錄的邊界，各占 13 個字節。其中記錄頭的5個字節分別標識了擁有記錄的數目和類型(擁有記錄數目是即后面頁目錄部分的owned值，當前頁目錄只有兩個槽，infimum擁有記錄數只有它自己為1，而supremum擁有我們插入的2條記錄和它自己，故為3)、下一條記錄的偏移 0x1c，即位置是 0xc07f，這就是我們實際記錄開始位置。后面8個字節為 infimum + 空值，supremum類似，只是它下一條記錄偏移為0。 

01 00 02 00 1c 69 6e 66 69 6d 75 6d 00  # infimum  
 03 00 0b 00 00 73 75 70 72 65 6d 75 6d  # supermum 

•  User Records: 接下來是2條我們插入的記錄。第1條記錄前面7字節是記錄頭(Record Header)，其中前面的 1字節記錄的是可變變量的長度03，因為我們記錄中c的值是 abc。然后1字節記錄的是可為NULL的變量是否是NULL，這里不為 NULL，故為0。接著的5字節記錄了插入順序2(infimum插入順序固定是0，supremum插入順序是1，其他記錄則是從2開始)，下一個記錄的偏移 0x1b(即下一個記錄開始位置是0xc078+0x1b=0xc093)，刪除標記等。后面就是記錄內容。第2條記錄同理。這里的事務ID可以通過 select * from information_schema.innodb_trx 進行驗證。 

03 00 00 00 10 00 1b # 記錄頭  
80 00 00 01          # 主鍵值1  
00 00 00 00 05 68    # 事務ID  
d1 00 00 01 54 01 10 # 回滾指針  
61 62 63             # ch的值 abc  
05 00 00 00 18 ff d6 # 第2條記錄頭  
80 00 00 02          # 主鍵值2  
00 00 00 00 05 69    # 事務ID  
d2 00 00 01 55 01 10 # 回滾指針  
64 65 66 67 68       # ch的值 defgh 

B+樹頁詳細結構

•  Page Directory(4字節)：因為頁目錄的slot只有2個，每個slot占2字節，故頁目錄為 00 70 00 63 這4字節，存儲的是相對于最初行的位置。其中 0xc063 正好是 infimum 記錄的開始位置，而 0xc070 正好是 supremum 記錄的開始位置。使用頁目錄進行二分查找，可以加速查詢，詳細見后面分析。
•  FIL Tail (8字節): 最后8字節為 95 45 82 8a 00 28 85 7c，其中 95 45 82 8a 為 checknum，跟 FIL Header的checksum一樣。后4字節00 28 85 7c 與 FIL Header的LSN的后4個字節一致。

當然，我們也可以通過 innodb_ruby 工具來分析表空間文件。 

root@stretch:/home/vagrant# innodb_space -s /var/lib/mysql/ibdata1 -T test/t space-page-type-regions  
start       end         count       type                  
0           0           1           FSP_HDR              
1           1           1           IBUF_BITMAP           
2           2           1           INODE                 
3           3           1           INDEX                 
4           5           2           FREE (ALLOCATED)      
root@stretch:/home/vagrant# innodb_space -s /var/lib/mysql/ibdata1 -T test/t -p 3 page-records  
Record 127: (id=1) → (ch="abc")  
Record 154: (id=2) → (ch="defgh") 

索引結構

InnoDB數據文件本身就是索引文件，其索引分聚集索引和輔助索引，聚集索引的葉節點包含了完整的數據記錄，輔助索引葉節點數據部分是主鍵的值，除了空間索引外，InnoDB的索引實現基本都是 B+ 樹，如圖所示。

其中非葉子結點存儲的是子頁的最小的鍵值和子頁的頁號，葉子結點存儲的是數據，數據按照索引鍵排序。同一層的頁之間用雙向鏈表連接(前面提到的FIL Header中PREV PAGE 和 NEXT PAGE)，同一頁內的記錄用單向鏈表連接(Record Header中記錄了下一條記錄的偏移)。每一頁設置了兩個虛擬記錄Infimum和Supremum用于標識頁的開始和結束。

索引結構

在InnoDB中根據輔助索引查詢，如果除了主鍵外還有其他字段，則需要查詢兩遍，先根據輔助索引查詢主鍵的值，然后再到主索引中查詢得到記錄。此外，因為輔助索引的數據部分是主鍵值，主鍵不能過大，否則會導致輔助索引占用空間變大，用自增ID做主鍵是個不錯的選擇。 

mysql> create table t2(id int auto_increment primary key, ch varchar(10), key(ch));  
mysql> insert into t2(ch) values('ab'); 

創建一個新的測試表 t2，有主索引 id 和 輔助索引 ch，分析 t2.ibd 文件可驗證：

•  對比表t，表t2多一個INDEX頁，用于存儲輔助索引的根結點。
•  輔助索引的INDEX頁也有兩個系統記錄 infimum 和 supremum。

          而用戶記錄內容格式跟前面分析基本一致，內容為輔助索引 ch 列的值 ab 和 主鍵值1。

頁目錄

前面提到INDEX頁內的記錄是通過單向鏈表連接在一起的，遍歷列表性能會比較差，而INDEX頁的頁目錄就是為了加速記錄搜索。表 t2 中的頁目錄只有兩項，分別是 0x63 和 0x70，即 99 和 112。

下面的ownedkey為這個頁目錄槽擁有的小于等于它的記錄數目，顯然 infimum 的ownedkey為 1，即只有它自己，沒有key會比infimum小。而 supremum 的owned是3，分別是我們插入的兩條記錄和它自己。 

slot    offset  type          owned  key  
0       99      infimum       1         
1       112     supremum      3  

每個頁目錄槽最少要包含4個記錄，最多包含8個記錄(包括它自己)。如果我們在表 t2 中另外插入 7 條記錄，則會增加一個新的slot，即 id 為 4 的記錄，如下： 

slot    offset  type          owned   key  
0       99      infimum       1         
1       207     conventional  4       (i=4)  
2       112     supremum      5   

下圖是頁目錄結構圖，可以通過頁目錄的二分查找提高頁內數據的查詢性能。

頁目錄結構

3.4 InnoDB 系統表空間

系統表空間包含內容有：數據字典，雙寫緩沖，修改緩沖，undo日志，以及在系統表空間創建的表的數據和索引。可以看到，除了分配未使用的頁外， UNDO_LOG，SYS, INDEX 頁占據了不少的空間。UNDO_LOG 頁存儲的是Undo log，SYS 頁存儲的是數據字典、回滾段、修改緩存等信息，INDEX 是索引頁，TRX_SYS 頁用于InnoDB的事務系統。數據字典就是數據表的元信息，修改緩沖前面提到是為了提高IO性能也不再贅述，這里主要分析下 Undo 日志和雙寫緩沖。 

root@stretch:/home/vagrant# innodb_space -s /var/lib/mysql/ibdata1 space-page-type-summary  
type                count       percent     description           
ALLOCATED           427         55.60       Freshly allocated     
UNDO_LOG            125         16.28       Undo log              
SYS                 110         14.32       System internal       
INDEX               71          9.24        B+Tree index         
INODE               11          1.43        File segment inode    
FSP_HDR             9           1.17        File space header     
IBUF_BITMAP         8           1.04        Insert buffer bitmap  
BLOB                5           0.65        Uncompressed BLOB    
TRX_SYS             2           0.26        Transaction system header 

Undo 日志

MySQL的MVCC(多版本并發控制)依賴Undo Log實現。MySQL的表空間文件 t.ibd 存儲的是記錄最新值，每個記錄都有一個回滾指針(見前面圖中的Roll Ptr)，指向該記錄的最近一條Undo記錄，而每條Undo記錄都會指向它的前一條Undo記錄，如下圖所示。默認情況下 undo log存儲在系統表空間 ibdata1 中。

Undo Log示意圖 

CREATE TABLE `t3` (  
  `id` int(11) NOT NULL,  
  `a` varchar(100) DEFAULT NULL,  
  PRIMARY KEY (`id`)  
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;  
insert into t3 values(1, 'A');  
update t3 set a='B' where id=1;  
update t3 set a='C' where id=1; 

插入一條數據后，可以發現當前 t3.ibd 文件中的記錄是 (1, ‘A’)，而 Undo Log此時有一條 insert 的記錄。如下： 

root@stretch:/var/lib/mysql# innodb_space -s ibdata1 -T test/t3 -p 3 -R 127 record-history  
Transaction   Type                Undo record  
(n/a)         insert              (id=1) → () 

執行后面的update語句，可以看到 undo log如下： 

root@stretch:/var/lib/mysql# innodb_space -s ibdata1 -T test/t3 -p 3 -R 127 record-history  
Transaction   Type                Undo record  
2333          update_existing     (id=1) → (a="B")  
2330          update_existing     (id=1) → (a="A")  
(n/a)         insert              (id=1) → () 

需要注意的是，Undo Log 在事務執行過程中就會產生，事務提交后才會持久化，如果事務回滾了則Undo Log也會刪除。

另外，刪除記錄并不會立即在表空間中刪除該記錄，而只是做個標記(delete-mark)，真正的刪除則是等由后臺運行的 purge 進程處理。除了每條記錄有Undo Log的列表外，整個數據庫也會有一個歷史列表，purge 進程會根據該歷史列表真正刪除已經沒有再被其他事務使用的 delete-mark 的記錄。purge 進程會刪除該記錄以及該記錄的 Undo Log。

雙寫緩沖

先回顧下InnoDB的記錄更新流程：先在Buffer Pool中更新，并將更新記錄到 Redo Log 文件中，Buffer Pool中的記錄會標記為臟數據并定期刷到磁盤。由于InnoDB默認Page大小是16KB，而磁盤通常以扇區為單位寫入，每次默認只能寫入512個字節，無法保證16K數據可以原子的寫入。

如果寫入過程發生故障(比如機器掉電或者操作系統崩潰)，會出現頁的部分寫入(partial page writes)，導致難以恢復。因為 MySQL 的重做日志采用的是物理邏輯日志，即頁間是物理信息，而頁內是邏輯信息，在發生頁部分寫入時，無法確認數據頁的具體修改而導致難以恢復。

MySQL 的數據頁在真正寫入到表空間文件前，會先寫到系統表空間文件的一段連續區域雙寫緩沖(Double-Write Buffer，默認大小為 2MB，128個頁)并 fsync 落盤，等雙寫緩沖寫入成功后才會將數據頁寫到實際表空間的位置。

因為雙寫緩沖和數據頁的寫入時機不一致，如果在寫入雙寫緩沖出錯，可以直接丟棄該緩沖頁，而如果是寫入數據頁時出錯，則可以根據雙寫緩沖區數據恢復表空間文件。

4、InnoDB 事務隔離級別

InnoDB的多版本并發控制是基于事務隔離級別實現的，而事務隔離級別則是依托前面提到的 Undo Log 實現的。當讀取一個數據記錄時，每個事務會使用一個讀視圖(Read View)，讀視圖用于控制事務能讀取到的記錄的版本。

InnoDB的事務隔離級別分為：Read UnCommitted，Read Committed，Repeatable Read以及Serializable。其中Serializable是基于鎖實現的串行化方式，嚴格來說不是事務可見性范疇。

•  Read Uncommitted：

    未提交讀也稱為臟讀，它讀取的是當前最新修改的記錄，即便這個修改最后并未生效。

•  Read Committed：

          提交讀。

          它基于的是當前事務內的語句開始執行時的最大的事務ID。

          如果其他事務修改同一個記錄，在沒有提交前，則該語句讀取的記錄還是不會變。

          但是這種情況會產生不可重復讀，即一個事務內多次讀取同一條記錄可能得到不同的結果(該記錄被其他事務修改并提交了)。

•  Repeatable Read：

          可重復讀。

          它基于的是事務開始時的讀視圖，直到事務結束。

          不讀取其他新的事務對該記錄的修改，保證同一個事務內的可重復讀取。

          InnoDB提供了 next-key lock來解決幻讀問題，不過在一些特殊場景下，可重復讀還是可能出現幻讀的情況。

          在實際開發中影響不大，就不贅述了。

5、InnoDB 和 ACID 模型

事務有 ACID 四個屬性， InnoDB 是支持事務的，它實現 ACID 的機制如下：

Atomicity

innodb的原子性主要是通過提供的事務機制實現，與原子性相關的特性有：

Autocommit 設置。

COMMIT 和 ROLLBACK 語句(通過 Undo Log實現)。

Consistency

innodb的一致性主要是指保護數據不受系統崩潰影響，相關特性包括：

InnoDB 的雙寫緩沖區(doublewrite buffer)。

InnoDB 的故障恢復機制(crash recovery)。

Isolation

innodb的隔離性也是主要通過事務機制實現，特別是為事務提供的多種隔離級別，相關特性包括：

•  Autocommit設置。
•  SET ISOLATION LEVEL 語句。
•  InnoDB 鎖機制。

Durability

innodb的持久性相關特性：

•     Redo log。
•     雙寫緩沖功能。

    可以通過配置項 innodb_doublewrite 開啟或者關閉。

•  配置 innodb_flush_log_at_trx_commit。

          用于配置innodb如何寫入和刷新 redo 日志緩存到磁盤。

          默認為1，表示每次事務提交都會將日志緩存寫入并刷到磁盤。

          innodb_flush_log_at_timeout 可以配置刷新日志緩存到磁盤的頻率，默認是1秒。

•  配置 sync_binlog。

          用于設置同步 binlog 到磁盤的頻率，為0表示禁止MySQL同步binlog到磁盤，binlog刷到磁盤的頻率由操作系統決定，性能最好但是最不安全。

          為1表示每次事務提交前同步到磁盤，性能最差但是最安全。

           MySQL文檔推薦是 sync_binlog 和 innodb_flush_log_at_trx_commit 都設置為 1。

•  操作系統的 fsync 系統調用。
•  UPS設備和備份策略等。