【Mysql】InnoDB 引擎中的頁目錄

標簽：mysq   示意圖   提取   編號   src   mys   目錄   主鍵   strong   

一、頁目錄和槽

接上一篇，現在知道記錄在頁中按照主鍵大小順序串成了單鏈表。

那么我使用主鍵查詢的時候，最順其自然的辦法肯定是從第一條記錄，也就是 Infrimum 記錄開始，一直向后找，只要存在總會找到。這種在數據量少的時候還好說，一旦數據多了，遍歷耗時一定非常長。

于是，作者又想到了一個好辦法，靈感來自于書本中的目錄。我們翻書的時候想查找一些內容，就會去查看目錄，然后直接確定好內容所在的頁碼。

那么對于 InnoDB 來說，過程如下：

• 將所有正常的記錄劃分為幾個組，這里包括那 2 條虛擬記錄，但是不包含已經被移除到垃圾鏈表的記錄。
• 每個組內最后一條記錄（也就是最大的那條）就是“大哥”，其他記錄都是“小弟”，而“大哥”記錄的頭信息中的 n_owned 屬性表示該組內共有幾條記錄。
• 將每個組中最后一條記錄在頁面中的地址偏移量單獨提取出來，按順序存儲到靠近頁尾部的地方。

這個地方就是頁目錄 Page Directory。而上述的地址偏移量就是該記錄的真實數據與頁面中第 0 個字節之間的距離，這些地址偏移量被稱為槽。

每個槽占用 2 字節，頁目錄就是由多個槽組成。

二、頁目錄的規定

在上一篇中，創建的表里存在 4 條數據，那么在頁中還要算上 Infimum 和 Supremum，共 6 條記錄。

這時候 InnoDB 會把它們分出 2 個組：

• 第一組：只有一個 Infimum 記錄
• 第二組：剩下的 5 條記錄

每個槽中，存放著每個組里最大的那條記錄所在頁面中的地址偏移量。

從圖中，需要關注頁目錄的一些點：

• 頁目錄有 2 個槽，說明記錄被分為 2 個組。
• Infimum 記錄的 n_owned 屬性值為 1，而 Supremum 的為 5。

為什么這 6 條記錄要這樣分？因為作者對于每組中的記錄數量有規定：

• 對于 Infimum 所在的分組只能有 1 條記錄。
• Supremum 所在的分組只能在 1~8 條之間。
• 剩下的分組，記錄條數范圍只能是 4~8 之間。

三、頁目錄查找記錄的過程

現在繼續向測試表里插入 12 條數據，也就是說在頁中共有 18 條記錄。

然后這些記錄就被分成了 5 個組，這里參考書籍上的示意圖（只保留一些關鍵屬性）：

現在，要查找主鍵是 6 的記錄，要如何進行？

因為 5 個槽的編號分別為 0、1、2、3、4 挨著的，并且里面的主鍵值也都是從小到大進行排序的，可以使用二分法（不清楚的可以百度），那么初始情況下 low=0，high=4：

1. 計算中間槽的位置，（0+4）/ 2=2，于是查看槽 2 對應記錄的主鍵值為 8，因為 8 > 6，所以 high = 2，low 不變。
2. 重新計算中間槽位置，（0+2）/ 2=1，于是查看槽 1 對應記錄的主鍵為4，因為 4 < 6，所以 high 不變，low = 1。
3. 因為 high - low = 1，所以確定主鍵值為6 的記錄就在槽 2 對應的組中。接著找到該組中主鍵最小的記錄，沿著單鏈表向后遍歷，最終找到主鍵 6 的記錄。

這里有個問題，槽對應的值都是這個組的主鍵最大的記錄，如何找到組里最小的記錄？比如槽 2 對應最大主鍵是 8 的記錄，那如何找到最小記錄。

解決辦法是：

• 通過槽 2 找到 槽 1 對應的記錄，也就是主鍵為 4 的記錄。
• 主鍵為 4 的記錄的下一條記錄就是槽 2 當中主鍵最小的記錄，可以找到主鍵 5。

總結
在一個數據頁中查找指定主鍵值的記錄，過程分為 2 步：

1. 通過二分法確定該記錄所在分組對應的槽，然后找到該槽所在分組中主鍵值最小的記錄。
2. 通過記錄的 next_record 屬性比那里該槽所在組的各個記錄，最終找到目標記錄。

【Mysql】InnoDB 引擎中的頁目錄

標簽：mysq   示意圖   提取   編號   src   mys   目錄   主鍵   strong   

原文地址：https://www.cnblogs.com/pingguo-softwaretesting/p/15053856.html