MySQL系列：innodb源碼分析之page結構解析

在表空間結構分析當中，我們知道innodb的最小物理存儲分配單位是page頁，在MySQL-3.23版本的源碼中，頁只有兩種頁，一種是index page，一種是undo page。其類型值定義在fil0fil.h當中。 FIL_PAGE_INDEX 數據索引頁，在表空間的inode page和xdes page都是屬於這類。 FIL_PAGE_UNDO_LOG 事務回滾日志頁。 在這裡我們主要分析的是 index page，undo log page在事務部分來介紹。不管是index page還是undo log page都是由三部分組成，page_header、page_body、page_trailer三部分組成。針對index page來分析者三部分結構。

1.page header

page header是page的頭信息，占用38個字節，分別存儲以下信息: FIL_PAGE_SPACE 4字節 page所屬的表空間的space id FIL_PAGE_OFFSET 4字節 page no，一般是在表空間的物理偏移量 FIL_PAGE_PREV 4 字節 前一頁的page no (B+tree的葉子節點是通過鏈表串起來的，有前後關系) FIL_PAGE_NEXT 4字節 後一頁的page no FIL_PAGE_LSN 8字節 更改記錄時最大的redo log lsn，一般用在redo log恢復時使用 FIL_PAGE_TYPE 2字節 page的類型 FIL_PAGE_FILE_FLUSH_LSN 8字節 space文件最後被flush是的redo log lsn,這個值只會在space的第一個頁中被設置 FIL_PAGE_ARCH_LOG_NO 4字節 最後被歸檔的archive log file 序號，這個值只會在space的第一個頁中被設置

2.page trailer

page trailer是在文件末尾的最後8個字節， 低位4個字節是用來表示page頁中數據的checksum,高位4位是用來存儲FIL_PAGE_LSN的部分信息，關於checksum的計算是通過buf_calc_page_checksum這個函數來結算得到的，基本是通過對page中數據作為參數用ut_fold_binary來快速計算得到。在後續的版本中，page checksum是可以選擇其他算法來做計算。這兩個字在頁保存到物理磁盤的時會進行更行，在頁從物理磁盤讀取出來的時候會被校驗。宗旨就是保證頁的完整性。

3.page body

index page body是由5部分組成，分別是body header、recorders、free recorders、free heap和page directory 組成。body header的結構定義如下：

#define	PAGE_N_DIR_SLOTS     0     /*page directory擁有的slot個數*/
#define PAGE_HEAP_TOP         2     /*heap中空閒位置的偏移量*/
#define PAGE_N_HEAP             4     /*heap中的記錄數,所有分配出去的記錄數，free rec + PAGE_N_RECS + 2*/
#define PAGE_FREE                   6     /*指向page中空閒空間的偏移量*/
#define PAGE_GARBAGE           8     /*已刪除的記錄字節數,用於重分配*/
#define PAGE_LAST_INSERT     10    /*最後插入記錄的位置*/
#define PAGE_DIRECTION        12    /*記錄的操作方向,PAGE_LEFT PAGE_RIGHT PAGE_SAME_REC PAGE_SAME_PAGE PAGE_NO_DIRECTION*/
#define PAGE_N_DIRECTION    14    /*同一方向連續插入的記錄數*/
#define PAGE_N_RECS              16    /*頁中存在的記錄數，不包括infimum和supremum*/
#define PAGE_MAX_TRX_ID     18    /*修改當前頁最大的事務ID*/
#define PAGE_HEADER_PRIV_END	 26
#define PAGE_LEVEL                 28     /*當前頁在索引樹的層位置*/
#define PAGE_BTR_SEG_LEAF   36     /*B+樹葉子節點所在段的segment header信息*/
define PAGE_BTR_SEG_TOP	 (36 + FSEG_HEADER_SIZE)     /*B+樹非葉子節點所在段的segment header信息*/

innodb在把真個頁可以用的空間當著一個heap,當需要插入記錄的時候，首先會在PAGE FREE中找是否有合適的記錄 可以用，如果沒有，就會在PAGE_HEAP_TOP的偏移上分配一個指定大小的rec_t的記錄塊，並將記錄案主鍵值插入到 recorders當中。那麼recorders是通過什麼樣的方式組織的呢?

3.1記錄的組織方式

在index page body中，rec（記錄）組織方式采用的是單向鏈表的方式來組織的，最前面一個記錄和最後面一個記錄是innodb定義的虛擬記錄，叫做infimum和supremum。這兩個記錄的物理物質是在body header後面緊接著的連個記錄。 其偏移如下：

#define PAGE_DATA             (PAGE_HEADER + 36 + 2 * FSEG_HEADER_SIZE)
#define PAGE_INFIMUM       (PAGE_DATA + 1 + REC_N_EXTRA_BYTES)           /*本page中索引最小的記錄位置*/
#define PAGE_SUPREMUM	 (PAGE_DATA + 2 + 2 * REC_N_EXTRA_BYTES + 8)     /*本page中索引最大的記錄位置*/

這兩條記錄在index page創建的時候就會被創建，參見page_create函數，其他的記錄是插入在其之間，入下示意圖：

3.2body free list

除了有效記錄以外，page中還有一類是之間使用過但被刪除的記錄，這類記錄不會直接回收到heap中（因為rec是邏輯 順序關系進行組織的，無法直接回收到heap中），innodb采用了page free recorders列表來組織和管理，通過 body header中的PAGE_FREE來進行定位，PAGE_FREE指向第一個被刪除的rec記錄的頁內偏移量。 示意圖如下：
body header除了用PAGE_FREE來管理釋放的記錄外，還使用了PAGE_GARBAGE來管理其空間大小，這個值表示所有刪除的記錄占用空間字節總和，以便刪除的記錄可以重復被使用，提高空間的使用率。 除了recorders和free recorders外，還有一個連續的空間，這個空間是用來做記錄分配的，只有當free recorders中沒有合適的記錄空間的時候，才會在這個連續空間上分配記錄。這個空間的地址偏移是在PAGE_HEAP_TOP中的。

3.3directory slots

innodb為了快速查找記錄，在body的後面定義了一個稱之為directory的目錄槽（slots）,每個槽位占用兩個字節，采用的是逆序存儲，也就是說mifimum的槽位總是在body最後2個字節上，其他的一次類推。每個槽位可以存儲多個紀錄。以下是各種slot的記錄數描述范圍（n_owned）：

Infimum slot owned

只有一條記錄

supremum slot owned

1到8條記錄

普通slot owned

4到8條記錄

如果普通slot在插入新的一條記錄時，普通slot或者supremum管理的記錄數是8，這個時候會對supremum進行split，產生一個slots，所以它的范圍是從4開始。以下是directory的一個關系示意圖:
從上可以看出，slot指向的rec中的owned代表的是向前有多少個rec屬於這個slot管轄，中間被管轄的rec的owned = 0。通過directory的二分查找只能查到對應記錄所屬的slot，還需要通過owned內部的二分查找才能精確定位到對應的記錄。這種設計的做法可以減小directory對page空間的占用，又能有很好查找的效率。關於slot相關的函數說明： page_dir_split_slot slot分裂函數，當一個slot管轄的范圍內插入新的記錄後超出其最大管理的記 錄數，就會對其進行平均范圍分裂。 page_dir_balance_slot slot均衡函數，當一個slot管轄的范圍內有記錄刪除後，其管理的記錄數小於 它最小范圍，就會和鄰近的slot做均衡。 不管是均衡還是分裂，都是最大范圍提高directory存儲空間效率和記錄查找效率。

3.4index page結構關系圖

4頁的操作

innodb的index page對記錄的操作主要有3種：查找記錄、插入記錄、刪除記錄。關於page的操作實現在page0cur.* 當中，在這些操作的中，innodb定義了一個page_cur_t，也就是page的游標，它是個邏輯概念的游標，只在內存中 有效。這個page cur是指向當前操作的記錄。定義如下：

typedef struct page_cur_struct
    {
         byte*	rec;	/*游標記錄的指針*/
    }page_cur_t;

因為所有的page操作必須將page從物理磁盤讀入到內存中進行邏輯頁的構建，再使用page_cur來進行查找、插入、刪除操作。

4.1查詢操作

我們知道在innodb的B+Tree索引搜索中，只能找到對應記錄所在的index page，那麼找到page後，會在頁中進行記錄查找，這個頁內查找過程如下： 1.先通過key在page的directory slots中進行二分查找，找到key對應的slot 2.因為slot是管理多個記錄（普通的slot owned = [4,8]),所以會再根據KEY在對應的slot管理的記錄中一次二分查找，直到找到記錄為止。 頁內查找的實現在page0cur.c的page_cur_search_with_match函數當中，這個函數除了返回查找的記錄以外，還會記錄二分查找過程中匹配的字節數和經過的跳數。值得注意的是這個函數支持四種模式的查找，分別定義如下：

#define	PAGE_CUR_G	 1        /*大於查詢*/
        #define	PAGE_CUR_GE	 2      /*大於等於查詢*/
        #define	PAGE_CUR_L	 3         /*小於查詢*/
        #define	PAGE_CUR_LE	 4       /*小於等於查詢*/

4.2插入操作

在記錄插入之前，會通過要插入記錄KEY找到要插入的位置，查找的模式是PAGE_CUR_LE，具體步驟如下： 1.通過記錄的key和記錄查找函數查找要插入的位置(操作page cur指向插入記錄的前一個記錄） 2.修改前後記錄的關聯關系和插入記錄的關聯關系 3.修改page游標方向計數器、page last insert 4.修改所在的slot的owned數值，如果超出范圍，進行split slot 5.因為插入記錄是對頁進行修改，所以記錄插入記錄的mtr log。以便異常時對頁的恢復。 插入記錄的mtr log構造比較復雜，以下是它的結構示意圖：
vc+jrNXiuPax5MG/vs3Kx7LlyOu1xLzHwry6zcbkx7DD5rXEvMfCvLTTv6rKvM671sPP4M2s19a92sr9o6zV4tH5cmVjIGRhdGHKx7TmtKLBy9Pr1q7HsLzHwryyu82stcTK/b7doaMK0rvM9bzHwry1xLLlyOvKvtLizbyjugo8aW1nIHNyYz0="http://www.2cto.com/uploadfile/Collfiles/20141229/20141229093158128.jpg" alt="\">
整記錄插入過程在page0cur.c中的page_cur_insert_rec_low函數中實現的。

4.3刪除操作

記錄刪除也是首先會通過刪除記錄的key或者記錄地址來確定操作page cur.操作步驟如下： 1.通過記錄信息確定page cur 2.添加一條刪除記錄的mtr log 3.將記錄前後對應關聯關系進行刪除和更改 4.設置page last insert和其他的頭信息（n _rec） 5.將記錄插入到body header free列表的起始位置，並修改PAGE_GARBAGE 6.設置所在slot的owned,如果小於管轄范圍的最小值，進行slot的均衡化。 刪除的mtr log格式如下：
刪除記錄示意圖：

5.小結

innodb的index page結構是一個高效利用空間的存儲結構，不僅考慮到查詢的速度，也考慮了合理的利用存儲空 間的存儲效率。innodb在這兩者之間找到了比較好的平衡點。頁除了提供基本的插入刪除查詢操作外，還提供批量 拷貝記錄、批量刪除記錄等功能。當這些都是基於基本的插入刪除操作之上的。批量操作函數如下：