InnoDB數(shù)據頁結構
#?不同類型頁
InnoDB存儲引擎為了出于不同的存儲目的設計多種類型的頁，比如
存放表空間頭部信息的頁，存放 Insert Buffer信息的頁，存放 INODE 信息的頁，存放 undo 日志信息的頁等等等等
其中這次重點介紹：存放數(shù)據表中記錄的那種類型的頁，官方稱這種存放記錄的頁為索引（ INDEX ）頁
#?數(shù)據頁結構
InnoDB 數(shù)據頁的存儲空間大致被劃分成了 7 個部分
名稱 中文名 占用空間大小 簡單描述 File Header 文件頭部 38字節(jié) 頁的一些通用信息 Page Header 頁面頭部 56字節(jié) 數(shù)據頁專有的一些信息 Infimum + Supremum 最小記錄和最大記錄 26字節(jié) 兩個虛擬的行記錄 User Records 用戶記錄 不確定 實際存儲行記錄內容 Free Space 空閑空間 不確定 頁中尚未使用的空間 Page Directory 頁面目錄 不確定 頁中的某些記錄的相對位置 File Trailer 文件尾部 8字節(jié) 校驗頁是否完整
#?記錄在頁中的儲存
在頁的7個組成部分中，我們自己存儲的記錄會按照我們指定的?行格式?存儲到 User Records 部分。但是在一開始生成頁的時候，其實并沒有 User Records 這個部分，每當我們插入一條記錄，都會從 Free Space 部分，也就是尚未使用的存儲空間中申請一個記錄大小的空間劃分到 User Records 部分，當 Free Space 部分的空間全部被 User Records 部分替代掉之后，也就意味著這個頁使用完了，如果還有新的記錄插入的話，就需要去申請新的頁了，這個過程的圖示如下：
你以為插入記錄就是這么簡單嗎，不！這只是大概的過程，要具體了解這個過程還得從行格式的變化說起
###記錄信息頭的秘密
為了更好的了解記錄在頁變化的過程，我們先創(chuàng)建一個表，插入四條數(shù)據
這個新創(chuàng)建的 page_demo 表有3個列，其中 c1 和 c2 列是用來存儲整數(shù)的， c3 列是用來存儲字符串的。需要注意的是，我們把 c1 列指定為主鍵，所以在具體的行格式中InnoDB就沒必要為我們去創(chuàng)建那個所謂的 row_id 隱藏列了。而且我們?yōu)檫@個表指定了 ascii 字符集以及 Compact 的行格式。
所以這個表中記錄的行格式示意圖就是這樣的：
名稱 大小（單位：bit） 描述 預留位1 1 沒有使用 預留位2 1 沒有使用 delete_mask 1 標記該記錄是否被刪除 min_rec_mask 1 B+樹的每層非葉子節(jié)點中的最小記錄都會添加該標記 n_owned 4 表示當前記錄擁有的記錄數(shù) heap_no 13 表示當前記錄在記錄堆的位置信息 record_type 3 表示當前記錄的類型， 0 表示普通記錄， 1 表示B+樹非葉節(jié)點記錄， 2 表示最小記錄， 3表示最大記錄 next_record 16 表示下一條記錄的相對位置
delete_mask
這個屬性標記著當前記錄是否被刪除，占用1個二進制位，值為 0 的時候代表記錄并沒有被刪除，為 1 的時 候代表記錄被刪除掉了。啥？被刪除的記錄還在 頁 中么？是的，擺在臺面上的和背地里做的可能大相徑庭，你以為它刪除了，可它 還在真實的磁盤上[攤手]（忽然想起冠?！?。這些被刪除的記錄之所以不立即從磁盤上移除，是因為移除它們之后把其他的記錄在磁盤上重新排列需要性能消耗，所以只是打一個刪除標記而已，所有被刪除掉的記錄都會組成一個所謂的 垃圾鏈表?，在這個鏈表中的記錄占用的空間稱之為所謂的 可重用空間 ，之后如果有新記錄插入到表中的話，可能把這些被刪除的記錄占用的存儲空間覆蓋掉。
next_record
這玩意兒非常重要，說白了就是單向鏈表的存放了下個節(jié)點的地址。它表示從當前記錄的真實數(shù)據到下一條記錄的真實數(shù)據的地址偏移量。比方說第一條記錄的 next_record 值為 32 ，意味著從第一條記錄的真實數(shù)據的地址處向后找 32 個字節(jié)便是下一條記錄的真實數(shù)據。如果你熟悉數(shù)據結構的話，就立即明白了，這其實是個 鏈表 ，可以通過一條記錄找到它的下一條記錄。但是需要注意注意再注意的一點是，?下一條記錄 指得并不是按照我們插入順序的下一條記錄，而是按照主鍵值由小到大的順序的下一條記錄。而且規(guī)定 Infimum記錄（也就是最小記錄） 的下一條記錄就是本頁中主鍵值最小的用戶記錄，而本頁中主鍵值最大的用戶記錄的下一條記錄就是 Supremum記錄（也就是最大記錄） ，為了更形象的表示一下這個 next_record 起到的作用，我們用箭頭來替代一下 next_record 中的地址偏移量：
#?Page Directory（頁目錄）
上面我們可以知道記錄在頁中是以單向鏈表的形式存在，如果我們要查找一條記錄，比如下面
1
最笨的辦法：從 Infimum 記錄（最小記錄）開始，沿著鏈表一直往后找，總有一天會找到（或者找不到[攤手]），在找的時候還能投機取巧，因為鏈表中各個記錄的值是按照從小到大順序排列的，所以當鏈表的某個節(jié)點代表的記錄的主鍵值大于你想要查找的主鍵值時，你就可以停止查找了，因為該節(jié)點后邊的節(jié)點的主鍵值依次遞增。時間復雜度為O(n)。
但是設計InnoDB的大叔們可沒有那么笨，他們采取了類似二分查找的方法，來查詢記錄；
將所有正常的記錄（包括最大和最小記錄，不包括標記為已刪除的記錄）劃分為幾個組。
每個組的最后一條記錄（也就是組內最大的那條記錄）的頭信息中的?
n_owned?屬性表示該記錄擁有多少條記錄，也就是該組內共有幾條記錄。將每個組的最后一條記錄的地址偏移量單獨提取出來按順序存儲到靠近?
頁的尾部的地方，這個地方就是所謂的 Page Directory ，也就是?頁目錄?（此時應該返回頭看看頁面各個部分的圖）。頁面目錄中的這些地址偏移量被稱為?槽（英文名： Slot ），所以這個頁面目錄就是由?槽組成的。
比方說現(xiàn)在的 page_demo 表中正常的記錄共有6條， InnoDB 會把它們分成兩組，第一組中只有一個最小記錄，第二組中是剩余的5條記錄，看下邊的示意圖：
注意：
現(xiàn)在 頁目錄 部分中有兩個槽，也就意味著我們的記錄被分成了兩個組， 槽1 中的值是 112 ，代表最大記錄的地址偏移量（就是從頁面的0字節(jié)開始數(shù)，數(shù)112個字節(jié)）； 槽0 中的值是 99 ，代表最小記錄的地址偏移量。
注意最小和最大記錄的頭信息中的 n_owned 屬性最小記錄的 n_owned 值為 1 ，這就代表著以最小記錄結尾的這個分組中只有 1 條記錄，也就是最小記錄本身。
最大記錄的 n_owned 值為 5 ，這就代表著以最大記錄結尾的這個分組中只有 5 條記錄，包括最大記錄本身還有我們自己插入的 4 條記錄。
為什么最小記錄的 n_owned 值為1，而最大記錄的 n_owned 值為 5 呢，這里頭有什么貓膩么？
設計 InnoDB 的大叔們對每個分組中的記錄條數(shù)是有規(guī)定的：
對于最小記錄所在的分組只能有 1 條記錄，最大記錄所在的分組擁有的記錄條數(shù)只能在 1~8 條之間，
剩下的分組中記錄的條數(shù)范圍只能在是 4~8 條之間。
###查找過程
往表里面再添加12條記錄
現(xiàn)在頁里邊就一共有18條記錄了（包括最小和最大記錄），這些記錄被分成了5個組，如圖所示：
因為把16條記錄的全部信息都畫在一張圖里太占地方，讓人眼花繚亂的，所以只保留了用戶記錄頭信息中的n_owned?和?next_record?屬性，也省略了各個記錄之間的箭頭，我沒畫不等于沒有啊！現(xiàn)在看怎么從這個?頁目錄中查找記錄。因為各個槽代表的記錄的主鍵值都是從小到大排序的，所以我們可以使用所謂的?二分法?來進行快速查找。
4個槽的編號分別是： 0 、 1 、 2 、 3 、 4 ，所以初始情況下最低的槽就是 low=0 ，最高的槽就是high=4 。比方說我們想找主鍵值為 6 的記錄，過程是這樣的：
計算中間槽的位置： (0+4)/2=2 ，所以查看 槽2 對應記錄的主鍵值為 8 ，又因為 8 > 6 ，所以設置high=2 ， low 保持不變。
重新計算中間槽的位置： (0+2)/2=1 ，所以查看 槽1 對應的主鍵值為 4 ，又因為 4 < 6 ，所以設置low=1 ， high 保持不變。
因為?high - low 的值為1，所以確定主鍵值為 5 的記錄在 槽2 對應的組中。此刻我們需要找到?槽2 中主鍵值最小的那條記錄，然后沿著單向鏈表遍歷 槽2 中的記錄。但是我們前邊又說過，每個槽對應的記錄都是該組中主鍵值最大的記錄，這里 槽2 對應的記錄是主鍵值為 8 的記錄，怎么定位一個組中最小的記錄呢？別忘了各個槽都是挨著的，我們可以很輕易的拿到 槽1 對應的記錄（主鍵值為 4 ），該條記錄的下一條記錄就是 槽2 中主鍵值最小的記錄，該記錄的主鍵值為 5 。所以我們可以從這條主鍵值為 5 的記錄出發(fā)，遍歷 槽2 中的各條記錄，直到找到主鍵值為 6 的那條記錄即可。由于一個組中包含的記錄條數(shù)只能是1~8條，所以 遍歷一個組中的記錄的代價是很小的。所以在一個數(shù)據頁中查找指定主鍵值的記錄的過程分為兩步：
通過二分法確定該記錄所在的槽，并找到該槽中主鍵值最小的那條記錄。
通過記錄的 next_record 屬性遍歷該槽所在的組中的各個記錄。
#?Page Header（頁面頭部）
設計 InnoDB 的大叔們?yōu)榱四艿玫揭粋€數(shù)據頁中存儲的記錄的狀態(tài)信息，比如本頁中已經存儲了多少條記錄，第一條記錄的地址是什么，頁目錄中存儲了多少個槽等等，特意在頁中定義了一個叫 Page Header 的部分，它是頁?結構的第二部分，這個部分占用固定的 56 個字節(jié)，專門存儲各種狀態(tài)信息
#?File Header（文件頭部）
File Header 針對各種類型的頁都通用，也就是說不同類型的頁都會以 File Header 作為第一個組成部分，它描述了一些針對各種頁都通用的一些信息，比方說這個頁的編號是多少，它的上一個頁、下一個頁是誰啦吧啦吧啦～ 這個部分占用固定的 38 個字節(jié)，是由下邊這些內容組成的：
每個數(shù)據頁的 File Header 部分都有上一個和下一個頁的編號，所以所有的數(shù)據頁會組成一個 雙鏈表 。
#?File Trailer
我們知道 InnoDB 存儲引擎會把數(shù)據存儲到磁盤上，但是磁盤速度太慢，需要以 頁 為單位把數(shù)據加載到內存中處理，如果該頁中的數(shù)據在內存中被修改了，那么在修改后的某個時間需要把數(shù)據同步到磁盤中。但是在同步了一半的時候中斷電了咋辦，這不是莫名尷尬么？為了檢測一個頁是否完整（也就是在同步的時候有沒有發(fā)生只同步一半的尷尬情況），設計 InnoDB 的大叔們在每個頁的尾部都加了一個 File Trailer 部分，這個部分由 8 個字節(jié)組成，可以分成2個小部分：
前4個字節(jié)代表頁的校驗和
這個部分是和 File Header 中的校驗和相對應的。每當一個頁面在內存中修改了，在同步之前就要把它的校驗和算出來，因為 File Header 在頁面的前邊，所以校驗和會被首先同步到磁盤，當完全寫完時，校驗和也會被寫到頁的尾部，如果完全同步成功，則頁的首部和尾部的校驗和應該是一致的。如果寫了一半兒斷電了，那么在 File Header 中的校驗和就代表著已經修改過的頁，而在 File Trialer 中的校驗和代表著原先的頁，二者不同則意味著同步中間出了錯。
后4個字節(jié)代表頁面被最后修改時對應的日志序列位置（LSN）
這個部分也是為了校驗頁的完整性的，只不過我們目前還沒說 LSN 是個什么意思，所以大家可以先不用管這個屬性。 這個 File Trailer 與 File Header 類似，都是所有類型的頁通用的。
歡迎關注[ggball](https://ggball.top)！
