MySQL 源碼學習(五)——Page和BTree
InnoDB通過BTree實現索引，Page(這里主要指Index Page，以下類似)包含了所有數據和索引的信息。原因是：Page為了讓BTree索引更加高效，對Page的結構進行針對性的設計，使得Page被加載到內存中后，可以基于Page中的信息快速地構建出BTree，同時盡可能地減少額外的內存占用，提升BTree的修改、重構的性能。本文將通過Page的結構，來看InnoDB是如何做到這些的。
Page的主要結構
Page具有四個主要結構：File Header，Page Header, Page Body和Page Trailer。
其中File Header，Page Header和Page Trailer是定長，分別占38,56和8個字節。
而Page Body是變長的，主要存儲具體的數據。下面再分別說明每個部分的具體結構。
File Header
源代碼中，File Header可以在fil0file.h文件中找到：
圖1 File Header定義
這里主要關注FIL_PAGE_PREV，FIL_PAGE_NEXT及FIL_PAGE_TYPE三個字段。
FIL_PAGE_TYPE
FIL_PAGE_TYPE是PAGE的類型定義，我們知道Btr的數據都在leaf節點，非leaf節點只包含索引數據。PAGE中就一種類型，表示索引Page。從這里也就看出了，實際上整個Btr都是存儲在Page中的。
FIL_PAGE_NEXT和PIL_PAGE_PREV
BTree在同一層級，不同node間有一個橫向的指針，此兩者就是把同一個層級的不同Page連接起來，組成雙向鏈表的指針。
Page Header
Page Header可以在page0page.h文件中找到定義：
圖2 Page Header的定義
Page Header主要用于記錄Page的狀態信息，共56個字節，這里暫時不展開說明。
Page Body
Page Body包含了User Record，System Record，Free Space以及Page Dictionary四個部分。
User Record就是存儲的實際數據，為InnoDB的行數據格式。
System Record中包含了兩個特殊的Record：Infimum Record和Supremum Record。這兩個Record是用來表示User Record的邊界。Page Body中，User Record也是以鏈表的形式存儲，因此使用Infimum Record表示鏈表的頭，Supremum Record表示鏈表尾部。為什么要有這兩個特殊的Record呢。原因是我們在操作表記錄時，主鍵有可能是不連續的，也有可能在兩個主鍵中間插入一個擁有新主鍵的記錄。但是Page在物理上是連續的，因此只能通過鏈表來實現邏輯上的連續。當我們用index進行order by時，數據庫并不需要進行排序，而只需要遍歷鏈表即可，這也就是通過索引查詢高效的原因之一。如圖3所示，1~5是鏈表連接的順序，也是記錄的邏輯順序。
圖3 User Record鏈表的邏輯順序
Free Space
Free Space是空閑的空間，當記錄被刪除后，User Record所占用的空間就會被放到Free Space中。
Page Dictionary
Page Dirctionary用于存放Page中Record的相對位置。這種相對位置并非是偏移量，而是類似于一個記錄的指針。同時并不是每個記錄都會有一個這樣的指針，而是擁有這樣指針的記錄，會使用一個額外的屬性：n_owned來記錄這條記錄后面跟隨了幾條記錄。這樣就可以在找到這條記錄之后，再次向后找到后面真正需要查找的記錄。
需要Page Dictionary的目的是：通過Btree并不能直接查找到對應的Record(Btree 的Leaf節點并不是一條一條的Record)，只能找到這個Record所對應的Page，然后再通過Page Dictinary進行二叉查找找到對應的目錄。
Page Trailer
Page的尾部，只有FIL_PAGE_END_LSN一個字段，8個字節，前4個字節是該頁的checksum，后4個字節是File Header中的FILE_PAGE_LSN。主要是用于檢測Page是否被完整的寫入了磁盤。
從上面對Page對說明中，我們可以看出，BTree是隱含在Page結構中的數據結構。用一張圖來表示的話，可以表示為：
圖4 Page視角的BTree
RDS-MYSQL 云數據庫 MySQL RDS MySQL MySQL
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
相關文章
