Mysql?InnoDB引擎中頁目錄和槽的查找過程
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 的記錄,要如何進行?
因為 5 個槽的編號分別為 0、1、2、3、4 挨著的,并且里面的主鍵值也都是從小到大進行排序的,可以使用二分法(不清楚的可以百度),那么初始情況下 low=0,high=4:
- 計算中間槽的位置,(0+4)/ 2=2,于是查看槽 2 對應記錄的主鍵值為 8,因為 8 > 6,所以 high = 2,low 不變。
- 重新計算中間槽位置,(0+2)/ 2=1,于是查看槽 1 對應記錄的主鍵為4,因為 4 < 6,所以 high 不變,low = 1。
- 因為 high - low = 1,所以確定主鍵值為6 的記錄就在槽 2 對應的組中。接著找到該組中主鍵最小的記錄,沿著單鏈表向后遍歷,最終找到主鍵 6 的記錄。
這里有個問題,槽對應的值都是這個組的主鍵最大的記錄,如何找到組里最小的記錄?比如槽 2 對應最大主鍵是 8 的記錄,那如何找到最小記錄。
解決辦法是:
- 通過槽 2 找到 槽 1 對應的記錄,也就是主鍵為 4 的記錄。
- 主鍵為 4 的記錄的下一條記錄就是槽 2 當中主鍵最小的記錄,可以找到主鍵 5。
總結(jié)
在一個數(shù)據(jù)頁中查找指定主鍵值的記錄,過程分為 2 步:
通過二分法確定該記錄所在分組對應的槽,然后找到該槽所在分組中主鍵值最小的記錄。
通過記錄的 next_record 屬性比那里該槽所在組的各個記錄,最終找到目標記錄。
本文參考書籍: 《mysql是怎樣運行的》
以上就是Mysql InnoDB引擎中頁目錄和槽的查找過程的詳細內(nèi)容,更多關(guān)于Mysql InnoDB引擎頁目錄的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
MySQL?8.0.35數(shù)據(jù)庫下載安裝以及環(huán)境變量的配置方法
很多朋友剛開始接觸mysql數(shù)據(jù)庫服務器,這篇文章主要給大家介紹了關(guān)于MySQL?8.0.35數(shù)據(jù)庫下載安裝以及環(huán)境變量的配置方法,文中通過圖文介紹的非常詳細,需要的朋友可以參考下2023-12-12SQL實現(xiàn)相鄰兩行數(shù)據(jù)的加減乘除操作
這篇文章主要介紹了SQL實現(xiàn)相鄰兩行數(shù)據(jù)的加減乘除操作,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2020-10-10MySQL索引類型Normal、Unique和Full Text的講解
今天小編就為大家分享一篇關(guān)于MySQL索引類型Normal、Unique和Full Text的講解,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧2019-03-03MySql字符串拆分實現(xiàn)split功能(字段分割轉(zhuǎn)列)
本文主要介紹了MySql字符串拆分實現(xiàn)split功能(字段分割轉(zhuǎn)列),文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下2022-05-05wampserver下mysql導入數(shù)據(jù)庫的步驟
這篇文章主要介紹了wampserver下mysql導入數(shù)據(jù)庫的步驟,需要的朋友可以參考下2016-08-08