iT邦幫忙

2021 iThome 鐵人賽

DAY 6
0
自我挑戰組

那些Mysql我不知道的事系列 第 6

Innodb資料頁結構-Part2(頁面目錄、頁面表頭、檔案表頭、檔案結尾)

資列頁(16kb大小)的結構有7個部分

1.使用者紀錄(user records)
2.空閒空間(free space)
3.頁面中最小與最大的紀錄(infimum+supermum)
4.頁面目錄(page directory)
5.頁面表頭(page header)
6.檔案表頭(file header)
7.檔案結尾(file trailer)

前文提到前三個的部分,今天會當作大家已經熟悉前面的內容,繼續說明剩下的部分,在過程中如有不清楚的地方就再回去複習吧。

頁面目錄

根據之前的學習我們已經知道資料頁的結構是一個按照主鍵大小排序的單向鏈結串列。
此時我們想要查詢資料的話,最直觀且最差的做法就是一筆一筆依序查詢,當資料頁有n筆我們新增的紀錄,那就查詢n次吧...

大家應該都認同這不是一個好的解法,我們來學習Innodb的工程師是怎麼設計的
設計的思維就像是我們在看一本書時,最前面會有各章節的頁碼,透過其我們可以知道要查詢的內容從那一頁開始找比較快。
Innodb的工程師就是這樣針對所有紀錄去分組(就像書的各章節)並定義各組的槽(就像章節的頁碼)。

具體的作法細節如下:

  1. 將所有紀錄分組(包含infimum+supermum紀錄,但不包含刪除的紀錄)。
  2. 將每組最後一筆紀錄(也是主鍵值最大的那筆)的位址偏移量(該紀錄的真實紀錄與第0個位元組之間的距離)提取出來存在接近頁尾部的地方。這些位址偏移量也稱為槽,每個槽佔2個位元組,頁目錄就是由這些槽組成。

分組有一個規定,infimum紀錄所在的組只有它自己一筆紀錄,supermum紀錄所在的組包含它自己只能有1到8筆紀錄,其餘的組別則為4到8筆紀錄。
這邊進一步補充說明前面第一點分組的細節

  1. 頁初始的時候只有infimum跟supermum紀錄,分屬兩個組,頁目錄也只有兩個槽,分別代表infimum紀錄跟
    supermum紀錄在頁面中的位址偏移量。
  2. 想像一下分組是由上而下(主鍵值由小而大)依序緊緊相連的情況。新增一筆紀錄的時候,會去找尋符合(值在界限內)的槽插入。

舉一個例子來說明:
現有16筆紀錄

mysql> insert into ryan_demo2_table(c1,c2,c3) values (1,100,'a'),(2,200,'b'),(3,300,'c'),(4,400,'d'),(5,500,'e'),(6,600,'f'),(7,700,'g'),(8,800,'h'),(9,900,'i'),(10,1000,'j'),(11,1100,'k'),(12,1200,'l'),(13,1300,'m'),(14,1400,'n'),(15,1500,'o'),(16,1600,'p');
Query OK, 16 rows affected (0.01 sec)
Records: 16  Duplicates: 0  Warnings: 0

mysql> select * from ryan_demo2_table;
+------+------+------+
| c1   | c2   | c3   |
+------+------+------+
|    1 |  100 | a    |
|    2 |  200 | b    |
|    3 |  300 | c    |
|    4 |  400 | d    |
|    5 |  500 | e    |
|    6 |  600 | f    |
|    7 |  700 | g    |
|    8 |  800 | h    |
|    9 |  900 | i    |
|   10 | 1000 | j    |
|   11 | 1100 | k    |
|   12 | 1200 | l    |
|   13 | 1300 | m    |
|   14 | 1400 | n    |
|   15 | 1500 | o    |
|   16 | 1600 | p    |
+------+------+------+
16 rows in set (0.01 sec)

其實在資料頁裡面有18筆紀錄(包含自動建立的infimum跟supermum紀錄)
而這裡的分組會是(以c1欄位主鍵值來看)
infimum紀錄自己1組(槽0 對應的主鍵值為infimum)
1、2、3、4四筆1組(槽1 對應的主鍵值為4)
5、6、7、8四筆1組(槽2 對應的主鍵值為8)
9、10、11、12四筆1組(槽3 對應的主鍵值為12)
13、14、15、16四筆紀錄跟supermum紀錄1組(槽4 對應的主鍵值為supermum)
總共5組

在這樣的情境下,我們想搜尋一筆主鍵值為6的紀錄,搜尋的過程會是以下這樣的。
1.一開始low為0,high為4,計算中間槽的位置(0+4)/2=2,查看槽2對應的主鍵值為8,因爲6小於8,所以high變為2(界限縮小),而low不變一樣為0
2.重新計算中間槽的位置(0+2)/2=1,查看槽1對應的主鍵值為4,因為6大於4,所以low為1(界限縮小),而high不變一樣為2
3.因為high-low為1,表示要搜尋的紀錄就在槽2的組別裡面,這時只要找到槽2主鍵值最小的那一筆紀錄,沿著單向鏈結串列歷遍槽2的所有紀錄即可找到我們要的紀錄

本來要比對16次的紀錄變成只要歷遍5,6就找到6了,就算不幸為此組最後一筆,1組紀錄筆數最多為8筆,因此最多也就8次,大大的提升了搜尋的速度。

頁面表頭

Innodb為了想得到資料頁的紀錄狀態定義了頁面標頭,方便知道情況。
這邊總共有14個狀態(佔用固定56位元組)但我不會全部列出來,我覺得現在看也看不懂的就不贅述了,等未來有遇到再來補充大家也比較清楚。我這邊就特別提幾個應該要知道且實用的狀態。

  • PAGE_N_DIR_SLOTS 頁目錄中的槽數量(佔用2個位元組)
  • PAGE_HEAP_TOP 還未使用的空間最小位址,也就是説從該位址之後就是free space(佔用2個位元組)
  • PAGE_GARBAGE 已刪除紀錄佔用的位元組數(佔用2個位元組)
  • PAGE_LAST_INSERT 最後插入紀錄的位置(佔用2個位元組)
  • PAGE_DIRECTION 表示最後一筆紀錄插入的方向。加入新紀錄的主鍵值比上一筆的大就是右邊,反之為左邊(佔用2個位元組)
  • PAGE_N_DIRECTION 一個方向連續插入的紀錄數量(佔用2個位元組)
  • PAGE_N_RECS 該頁中使用者紀錄的數量(不包含infimum跟supermum紀錄及被刪除的紀錄,佔用2個位元組)

檔案表頭

前面的頁面表頭是紀錄資料頁的各種狀態,而檔案表頭則不侷限於資料頁,包含了其他各種類型頁面的紀錄狀態。這裡一樣只說明幾個比較重要的狀態。

  • FIL_PAGE_SPACE_OR_CHKSUM 校正碼(什麼是校正碼?當有一個很長的位元組串,我們會透過演算法計算出較短的值來代表,這個短值就是校正碼。好處是當要比對兩個很長的位元組串前,先比較校正碼就可以大幅降低時間)
  • FIL_PAGE_OFFSET 獨立頁號(像我們的身份證號一樣)
  • FIL_PAGE_TYPE 頁的類型。之前有提過除了資料頁外還有很多其他的頁類型。
  • FIL_PAGE_PREV和FIL_PAGE_NEXT 有時候資料量非常大無法一次性的分配很多頁,資料可能儲存在不連續的頁中,因此有了這兩個屬性把不連續的頁串連起來,形成一個雙向鏈結串列。要注意的是並不是所有類型的頁都有這兩個屬性唷,但資料頁有。

檔案結尾

我們知道Innodb會先把資料從磁碟讀取到記憶體去更新(因為磁碟速度太慢),更新完畢後在刷新回磁碟。
但如果在記憶體更新後,發生意外(斷電等),導致沒有刷新回磁碟,兩邊資料不一致的bug就尷尬了。
所以Innodb在每個頁的尾部增加了檔案結尾的部分。佔8位元組包含兩個部分(校正碼4位元組及最後被修改時對應的LSN的後4位元組[LSN是新名詞之後會再說明,先大概知道有這東西就好])。
透過比對檔案表頭與檔案結尾的校正碼及LSN驗證來確保資料成功刷新。

今天的內容較多,但這些都是基礎且很重要的東西,大家要好好熟悉,因為這對接下來要說明的內容都是必要的前提知識。在一起好好加油吧~耶~吃蒼蠅去!


上一篇
Innodb資料頁結構-Part1(使用者紀錄、空閒空間、頁面中最小與最大的紀錄)
下一篇
快速查詢的秘密武器B+樹索引-Part1(無索引如何搜尋、基本索引概念)
系列文
那些Mysql我不知道的事30

尚未有邦友留言

立即登入留言