Mysql InnoDB引擎頁目錄

一、頁目錄和槽

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

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

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

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

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

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

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

二、頁目錄的規(guī)定

在上一篇中，創(chuàng)建的表里存在 4 條數(shù)據(jù)，那么在頁中還要算上 Infimum 和 Supremum，共 6 條記錄。

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

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

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

從圖中，需要關(guān)注頁目錄的一些點：

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

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

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

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

現(xiàn)在繼續(xù)向測試表里插入 12 條數(shù)據(jù)，也就是說在頁中共有 18 條記錄。

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

現(xiàn)在，要查找主鍵是 6 的記錄，要如何進(jìn)行？

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

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

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

解決辦法是：

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

總結(jié)

在一個數(shù)據(jù)頁中查找指定主鍵值的記錄，過程分為 2 步：

通過二分法確定該記錄所在分組對應(yīng)的槽，然后找到該槽所在分組中主鍵值最小的記錄。

通過記錄的 next_record 屬性比那里該槽所在組的各個記錄，最終找到目標(biāo)記錄。

本文參考書籍： 《mysql是怎樣運(yùn)行的》

以上就是Mysql InnoDB引擎中頁目錄和槽的查找過程的詳細(xì)內(nèi)容，更多關(guān)于Mysql InnoDB引擎頁目錄的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論