## 疑問 數據存儲在硬盤，InnoDB如何高效讀寫? 頁 + 行格式 數據存儲在硬盤如何高效的利用空間? 行格式 ## InnoDB頁簡介 InnoDB需要把數據存儲到硬盤(持久性)，但是真正處理數據的過程是發生在內存中的(內存速度快)。所以需要把磁盤中的數據加載到內存中，如果是處理寫入或修改請求的話，還需要把內存中的內容刷新到磁盤上。磁盤的速度非常慢，和內存讀寫差了幾個數量級，所以當我們想從表中獲取某些記錄時，`InnoDB`存儲引擎不能一條一條的把去磁盤讀取記錄，需要更高效的方式。 `InnoDB`采取的方式是：將數據分為若干頁，以 **頁** 作為磁盤和內存之間交互的最小單位。InnoDB中頁的大小一般為 16 KB。也就是一次最少從磁盤中讀取16KB的內容到內存中，一次最少把內存中的16KB內容刷新到磁盤中。 ## InnoDB行格式 我們平時是以記錄為單位來向表中插入數據的，這些記錄在磁盤上的存放方式也被稱為`行格式`或者`記錄格式`。設計`InnoDB`存儲引擎的大叔們到現在為止設計了4種不同類型的`行格式`，分別是`Compact`、`Redundant`、`Dynamic`和`Compressed`行格式，隨著時間的推移，他們可能會設計出更多的行格式，但是不管怎么變，在原理上大體都是相同的。 Compact 行格式是MySQL5.1后的默認格式。但在 MySQL 5.7.9 及以后版本，默認行格式是innodb_default_row_format變量決定，**默認值是 Dynamic** ### 指定行格式的語法 我們可以在創建或修改表的語句中指定`行格式`： ``` CREATE TABLE 表名 (列的信息) ROW_FORMAT=行格式名稱 ALTER TABLE 表名 ROW_FORMAT=行格式名稱 ``` ### COMPACT行格式  一條完整的記錄其實可以被分為記錄的額外信息和記錄的真實數據兩大部分 #### 記錄的額外信息 這部分信息是服務器為了描述這條記錄而不得不額外添加的一些信息，這些額外信息分為3類，分別是**變長字段長度列表、NULL值列表和記錄頭信息**。 ##### 變長字段長度列表 變長字段占用的存儲空間分為兩部分： 1. 真正的數據內容 2. 占用的字節數 在`Compact`行格式中，所有的變長字段數據占用的字節長度都放在記錄的開頭部位， 形成一個變長字段長度列表， 各變長字段數據占用的字節數按照列的順序**逆序存放**。變長字段長度列表中只存儲值為 非NULL 的列內容占用的長度，值為 NULL 的列的長度是不儲存的 。 對于***CHAR(M)***類型的列來說，當列采用的是定長字符集時，該列占用的字節數不會被加到變長字段長度列表，而如果采用變長字符集時，該列占用的字節數也會被加到變長字段長度列表。 ### 行溢出數據 #### VARCHAR(M)最多能存儲的數據 `VARCHAR(M)`類型的列最多可以占用`65535`個字節。其中的`M`代表該類型最多存儲的字符數量，`MySQL`對一條記錄占用的最大存儲空間是有限制的，除了`BLOB`或者`TEXT`類型的列之外，**其他所有的列（不包括隱藏列和記錄頭信息）占用的字節長度加起來不能超過`65535`個字節。** 存儲一個`VARCHAR(M)`類型的列，其實需要占用3部分存儲空間： * 真實數據 * 真實數據占用字節的長度 * `NULL`值標識，如果該列有`NOT NULL`屬性則可以沒有這部分存儲空間 如果該`VARCHAR`類型的列沒有`NOT NULL`屬性，那最多只能存儲`65532`個字節的數據， 有則存儲`65533`個字節的數據。 utf8字符集表示一個字符最多需要3個字節，那在該字符集下，M的最大取值就是21844（也就是：65532/3）個字符。 `MySQL`是以`頁`為基本單位來管理存儲空間的，頁能存儲16kb數據，也就是`16384`字節，而一個`VARCHAR(M)`類型的列就最多可以存儲`65532`個字節，這樣就可能造成一個頁存放不了一條記錄的尷尬情況。這種就會在`記錄的真實數據`處只會存儲該列的一部分數據，把剩余的數據分散存儲在幾個其他的頁中，然后`記錄的真實數據`處用20個字節存儲指向這些頁的地址。 ### Dynamic和Compressed行格式 如果某一列中的數據非常多的話，在本記錄的真實數據處只會存儲該列的前`768`個字節的數據和一個指向其他頁的地址，然后把剩下的數據存放到其他頁中，這個過程也叫做`行溢出`，存儲超出`768`字節的那些頁面也被稱為`溢出頁`。 `Dynamic`和`Compressed`行格式，我現在使用的`MySQL`版本是`5.7`，它的默認行格式就是`Dynamic`，這倆行格式和`Compact`行格式挺像，只不過在處理`行溢出`數據時有點兒分歧，它們不會在記錄的真實數據處存儲字段真實數據的前`768`個字節，而是把所有的字節都存儲到其他頁面中，只在記錄的真實數據處存儲其他頁面的地址 `Compressed`行格式和`Dynamic`不同的一點是，`Compressed`行格式會采用壓縮算法對頁面進行壓縮，以節省空間。 ## InnoDB數據頁結構 | 名稱 | 中文名 | 占用空間大小 | 簡單描述 | | :-: | :-: | :-: | :-: | | `File Header` | 文件頭部 | `38`字節 | 頁的一些通用信息 | | `Page Header` | 頁面頭部 | `56`字節 | 數據頁專有的一些信息 | | `Infimum + Supremum` | 最小記錄和最大記錄 | `26`字節 | 兩個虛擬的行記錄 | | `User Records` | 用戶記錄 | 不確定 | 實際存儲的行記錄內容 | | `Free Space` | 空閑空間 | 不確定 | 頁中尚未使用的空間 | | `Page Directory` | 頁面目錄 | 不確定 | 頁中的某些記錄的相對位置 | | `File Trailer` | 文件尾部 | `8`字節 | 校驗頁是否完整 | ## 記錄在頁中的存儲 一開始生成頁的時候，其實并沒有`User Records`這個部分，每當我們插入一條記錄，都會從`Free Space`部分，也就是尚未使用的存儲空間中申請一個記錄大小的空間劃分到`User Records`部分，當`Free Space`部分的空間全部被`User Records`部分替代掉之后，也就意味著這個頁使用完了，如果還有新的記錄插入的話，就需要去申請新的頁了。 ### 記錄頭信息 | 名稱 | 大小（單位：bit） | 描述 | | :-: | :-: | :-: | | `預留位1` | `1` | 沒有使用 | | `預留位2` | `1` | 沒有使用 | | `delete_mask` | `1` | 標記該記錄是否被刪除 | | `min_rec_mask` | `1` | B+樹的每層非葉子節點中的最小記錄都會添加該標記 | | `n_owned` | `4` | 表示當前記錄擁有的記錄數 | | `heap_no` | `13` | 表示當前記錄在記錄堆的位置信息 | | `record_type` | `3` | 表示當前記錄的類型，`0`表示普通記錄，`1`表示B+樹非葉節點記錄(目錄項記錄)，`2`表示最小記錄，`3`表示最大記錄 | | `next_record` | `16` | 表示下一條記錄的相對位置 | * delete_mask 這個屬性標記著當前記錄是否被刪除，占用1個二進制位，值為`0`的時候代表記錄并沒有被刪除，為`1`的時候代表記錄被刪除掉了。這些被刪除的記錄之所以不立即從磁盤上移除，是因為移除它們之后把其他的記錄在磁盤上重新排列需要性能消耗，所以只是打一個刪除標記而已，所有被刪除掉的記錄都會組成一個所謂的垃圾鏈表，在這個鏈表中的記錄占用的空間稱之為所謂的可重用空間，之后如果有新記錄插入到表中的話，可能把這些被刪除的記錄占用的存儲空間覆蓋掉。 * min_rec_mask B+樹的每層非葉子節點中的最小記錄都會添加該標記 * n_owned 這個分組中的記錄數 * heap_no 這個屬性表示當前記錄在本頁中的位置，值從 2 開始, 0和1分別被自動插入的最小記錄和最大記錄占用了,也就是 Infimum + Supremum 的部分 * record_type 當前記錄的類型，一共有4種類型的記錄，`0`表示普通記錄，`1`表示B+樹非葉節點記錄，`2`表示最小記錄，`3`表示最大記錄。 * next_record 非常重要，它表示從當前記錄的真實數據到下一條記錄的真實數據的地址偏移量 ## Page Directory（頁目錄）  從這個圖中我們需要注意這么幾點： * 現在`頁目錄`部分中有兩個槽，也就意味著我們的記錄被分成了兩個組，`槽1`中的值是`112`，代表最大記錄的地址偏移量（就是從頁面的0字節開始數，數112個字節）；`槽0`中的值是`99`，代表最小記錄的地址偏移量。 * 注意最小和最大記錄的頭信息中的`n_owned`屬性 * 最小記錄的`n_owned`值為`1`，這就代表著以最小記錄結尾的這個分組中只有`1`條記錄，也就是最小記錄本身。 * 最大記錄的`n_owned`值為`5`，這就代表著以最大記錄結尾的這個分組中只有`5`條記錄，包括最大記錄本身還有我們自己插入的`4`條記錄。 每個分組中的記錄條數是有規定的：對于最小記錄所在的分組只能有***1***條記錄，最大記錄所在的分組擁有的記錄條數只能在***1~8***條之間，剩下的分組中記錄的條數范圍只能在是***4~8***條之間。 ## Page Header（頁面頭部） 比如本頁中已經存儲了多少條記錄，第一條記錄的地址是什么，頁目錄中存儲了多少個槽等等 | 名稱 | 占用空間大小 | 描述 | | :-: | :-: | :-: | | `PAGE_N_DIR_SLOTS` | `2`字節 | 在頁目錄中的槽數量 | | `PAGE_HEAP_TOP` | `2`字節 | 還未使用的空間最小地址，也就是說從該地址之后就是`Free Space` | | `PAGE_N_HEAP` | `2`字節 | 本頁中的記錄的數量（包括最小和最大記錄以及標記為刪除的記錄） | | `PAGE_FREE` | `2`字節 | 第一個已經標記為刪除的記錄地址（各個已刪除的記錄通過`next_record`也會組成一個單鏈表，這個單鏈表中的記錄可以被重新利用） | | `PAGE_GARBAGE` | `2`字節 | 已刪除記錄占用的字節數 | | `PAGE_LAST_INSERT` | `2`字節 | 最后插入記錄的位置 | | `PAGE_DIRECTION` | `2`字節 | 記錄插入的方向 | | `PAGE_N_DIRECTION` | `2`字節 | 一個方向連續插入的記錄數量 | | `PAGE_N_RECS` | `2`字節 | 該頁中記錄的數量（不包括最小和最大記錄以及被標記為刪除的記錄） | | `PAGE_MAX_TRX_ID` | `8`字節 | 修改當前頁的最大事務ID，該值僅在二級索引中定義 | | `PAGE_LEVEL` | `2`字節 | 當前頁在B+樹中所處的層級 | | `PAGE_INDEX_ID` | `8`字節 | 索引ID，表示當前頁屬于哪個索引 | | `PAGE_BTR_SEG_LEAF` | `10`字節 | B+樹葉子段的頭部信息，僅在B+樹的Root頁定義 | | `PAGE_BTR_SEG_TOP` | `10`字節 | B+樹非葉子段的頭部信息，僅在B+樹的Root頁定義 | * `PAGE_DIRECTION` 假如新插入的一條記錄的主鍵值比上一條記錄的主鍵值大，我們說這條記錄的插入方向是右邊，反之則是左邊。用來表示最后一條記錄插入方向的狀態就是`PAGE_DIRECTION`。 * `PAGE_N_DIRECTION` 假設連續幾次插入新記錄的方向都是一致的，`InnoDB`會把沿著同一個方向插入記錄的條數記下來，這個條數就用`PAGE_N_DIRECTION`這個狀態表示。當然，如果最后一條記錄的插入方向改變了的話，這個狀態的值會被清零重新統計。 ## File Header（文件頭部） `File Header`針對各種類型的頁都通用，也就是說不同類型的頁都會以`File Header`作為第一個組成部分，它描述了一些針對各種頁都通用的一些信息，比方說這個頁的編號是多少，它的上一個頁、下一個頁是誰 | 名稱 | 占用空間大小 | 描述 | | :-: | :-: | :-: | | `FIL_PAGE_SPACE_OR_CHKSUM` | `4`字節 | 頁的校驗和（checksum值） | | `FIL_PAGE_OFFSET` | `4`字節 | 頁號 | | `FIL_PAGE_PREV` | `4`字節 | 上一個頁的頁號 | | `FIL_PAGE_NEXT` | `4`字節 | 下一個頁的頁號 | | `FIL_PAGE_LSN` | `8`字節 | 頁面被最后修改時對應的日志序列位置（英文名是：Log Sequence Number） | | `FIL_PAGE_TYPE` | `2`字節 | 該頁的類型 | | `FIL_PAGE_FILE_FLUSH_LSN` | `8`字節 | 僅在系統表空間的一個頁中定義，代表文件至少被刷新到了對應的LSN值 | | `FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID` | `4`字節 | 頁屬于哪個表空間 | * `FIL_PAGE_SPACE_OR_CHKSUM` 這個代表當前頁面的校驗和（checksum）。啥是個校驗和？就是對于一個很長很長的字節串來說，我們會通過某種算法來計算一個比較短的值來代表這個很長的字節串，這個比較短的值就稱為`校驗和`。這樣在比較兩個很長的字節串之前先比較這兩個長字節串的校驗和，如果校驗和都不一樣兩個長字節串肯定是不同的，所以省去了直接比較兩個比較長的字節串的時間損耗。 * `FIL_PAGE_OFFSET` 每一個`頁`都有一個單獨的頁號，就跟你的身份證號碼一樣，`InnoDB`通過頁號來可以唯一定位一個`頁`。 * `FIL_PAGE_TYPE` 這個代表當前`頁`的類型，我們前邊說過，`InnoDB`為了不同的目的而把頁分為不同的類型，我們上邊介紹的其實都是存儲記錄的`數據頁`，其實還有很多別的類型的頁 | 類型名稱 | 十六進制 | 描述 | | :-: | :-: | :-: | | `FIL_PAGE_TYPE_ALLOCATED` | 0x0000 | 最新分配，還沒使用 | | `FIL_PAGE_UNDO_LOG` | 0x0002 | Undo日志頁 | | `FIL_PAGE_INODE` | 0x0003 | 段信息節點 | | `FIL_PAGE_IBUF_FREE_LIST` | 0x0004 | Insert Buffer空閑列表 | | `FIL_PAGE_IBUF_BITMAP` | 0x0005 | Insert Buffer位圖 | | `FIL_PAGE_TYPE_SYS` | 0x0006 | 系統頁 | | `FIL_PAGE_TYPE_TRX_SYS` | 0x0007 | 事務系統數據 | | `FIL_PAGE_TYPE_FSP_HDR` | 0x0008 | 表空間頭部信息 | | `FIL_PAGE_TYPE_XDES` | 0x0009 | 擴展描述頁 | | `FIL_PAGE_TYPE_BLOB` | 0x000A | 溢出頁 | | `FIL_PAGE_INDEX` | 0x45BF | 索引頁，也就是我們所說的`數據頁` | 我們存放記錄的數據頁的類型其實是`FIL_PAGE_INDEX`，也就是所謂的`索引頁`。 * `FIL_PAGE_PREV`和`FIL_PAGE_NEXT` `InnoDB`可能不可以一次性為這么多數據分配一個非常大的存儲空間，如果分散到多個不連續的頁中存儲的話需要把這些頁關聯起來，`FIL_PAGE_PREV`和`FIL_PAGE_NEXT`就分別代表本頁的上一個和下一個頁的頁號。這樣通過建立一個雙向鏈表把許許多多的頁就都串聯起來了，而無需這些頁在物理上真正連著。 ## File Trailer 每個頁的尾部都加了一個`File Trailer`部分，這個部分由`8`個字節組成，校驗頁是否完整 * 前4個字節代表頁的校驗和 這個部分是和`File Header`中的校驗和相對應的。每當一個頁面在內存中修改了，在同步之前就要把它的校驗和算出來，因為`File Header`在頁面的前邊，所以校驗和會被首先同步到磁盤，當完全寫完時，校驗和也會被寫到頁的尾部，如果完全同步成功，則頁的首部和尾部的校驗和應該是一致的。二者不同則意味著同步中間出了錯。 * 后4個字節代表頁面被最后修改時對應的日志序列位置（LSN） 這個`File Trailer`與`File Header`類似，都是所有類型的頁通用的。 ## 總結 1. InnoDB為了不同的目的而設計了不同類型的頁，我們把用于存放記錄的頁叫做`數據頁`。 2. 一個數據頁可以被大致劃分為7個部分，分別是 * `File Header`，表示頁的一些通用信息，占固定的38字節。 * `Page Header`，表示數據頁專有的一些信息，占固定的56個字節。 * `Infimum + Supremum`，兩個虛擬的偽記錄，分別表示頁中的最小和最大記錄，占固定的`26`個字節。 * `User Records`：真實存儲我們插入的記錄的部分，大小不固定。 * `Free Space`：頁中尚未使用的部分，大小不確定。 * `Page Directory`：頁中的某些記錄相對位置，也就是各個槽在頁面中的地址偏移量，大小不固定，插入的記錄越多，這個部分占用的空間越多。 * `File Trailer`：用于檢驗頁是否完整的部分，占用固定的8個字節。 3. 每個記錄的頭信息中都有一個`next_record`屬性，從而使頁中的所有記錄串聯成一個`單鏈表`。 4. `InnoDB`會把頁中的記錄劃分為若干個組，每個組的最后一個記錄的地址偏移量作為一個`槽`，存放在`Page Directory`中，所以在一個頁中根據主鍵查找記錄是非常快的，分為兩步： * 通過二分法確定該記錄所在的槽。 * 通過記錄的next\_record屬性遍歷該槽所在的組中的各個記錄。 5. 每個數據頁的`File Header`部分都有上一個和下一個頁的編號，所以所有的數據頁會組成一個`雙鏈表`。 6. 為保證從內存中同步到磁盤的頁的完整性，在頁的首部和尾部都會存儲頁中數據的校驗和和頁面最后修改時對應的`LSN`值，如果首部和尾部的校驗和和`LSN`值校驗不成功的話，就說明同步過程出現了問題。