圖解｜12張圖告訴你MySQL的主鍵查詢為什麼這麼快

這是圖解MySQL的第3篇文章，這篇文章會讓大家清楚地明白：

  • 什麼是InnoDB行格式？InnoDB頁是什麼？
  • InnoDB頁和InnoDB行格式都有哪些欄位資訊？
  • 為什麼推薦使用自增ID作為主鍵，而不推薦使用UUID？
  • InnoDB設計者如何設計高效演算法，快速在一個頁中搜索記錄。

正文開始！

註：我們接下來的所有描述，針對的都是InnoDB存儲引擎，如果涉及到其他存儲引擎，將會特殊說明

1. 初探InnoDB行格式（ROW_FORMAT）

我們平時都是以記錄為單位向MySQL的表中插入數據的，這些記錄在磁碟中的存放的格式就是InnoDB的行格式。

為了證明我不是瞎說，舉個例子，我查詢一下本地資料庫以forward開頭的數據表的行格式

image-20220222210543904

我們平時很少操作行格式，所以對這個概念可能不是很清楚。其實InnoDB存儲引擎為我們提供了4種不同的行格式

  • DYNAMIC（默認的行格式）

  • COMPACT

  • REDUNDANT

  • COMPRESSED

我們可以在創建表時指定行格式（如果不指定，默認行格式為DYNAMIC），比如我指定row_format_table表的行格式為COMPACT

mysql> CREATE TABLE row_format_table(
    -> id INT,
    -> c1 VARCHAR(10),
    -> c2 CHAR(10),
    -> PRIMARY KEY(id)
    -> ) CHARSET=utf8 ROW_FORMAT=COMPACT;

語法了解到這一步就可以了，接下來我們看一下4種行格式的具體表現形式，畫個圖就是

image-20220222215446309

從圖中可以看出，一條完整的記錄可以分為「記錄的額外資訊」和「真實數據資訊」兩部分，4種行格式的不同也主要體現在「真實數據資訊」這一部分。也就是說，不同的行格式採用了不同的數據格式來存儲我們的真實數據，至於有什麼具體的不同，對我們這篇文章並不重要，不需要關注。

next_record表示下一條記錄的相對位置，有了這個欄位，記錄之間可以串聯成一個單鏈表，這個比較好理解，看看圖吧。至於其他的欄位資訊，我們用到的時候再介紹就好了。

image-20220223141811652

注意：圖中所列欄位的排列順序（包括下文即將提及的）並非是InnoDB行格式在存儲設備上的真實存儲順序，為了方便說明接下來的故事，此處我做了簡化，大家理解思想即可

2. 引入InnoDB頁

對於MySQL的任何存儲引擎而言，數據都是存儲在磁碟中的，存儲引擎要操作數據，必須先把磁碟中的數據載入到記憶體中才可以。

那麼問題來了，一次性從磁碟中載入多少數據到記憶體中合適呢？當獲取記錄時，InnoDB存儲引擎需要一條條地把記錄從磁碟中讀取出來嗎？

當然不行！我們知道磁碟的讀寫速度和記憶體讀寫速度差了幾個數量級，如果我們需要讀取的數據恰好運行在磁碟的不同位置，那就意味著會產生多次I/O操作。

因此，無論是作業系統也好，MySQL存儲引擎也罷，都有一個預讀取的概念。概念的依據便是統治電腦界的局部性原理。

空間局部性：如果當前數據是正在被使用的，那麼與該數據空間地址臨近的其他數據在未來有更大的可能性被使用到，因此可以優先載入到暫存器或主存中提高效率

就是當磁碟上的一塊數據被讀取的時候，我們乾脆多讀一點，而不是用多少讀多少。

InnoDB存儲引擎將數據劃分為若干個頁，以頁作為磁碟和記憶體之間交互的最小單位。InnoDB中頁的大小默認為16KB。也就是默認情況下，一次最少從磁碟中讀取16KB的數據到記憶體中，一次最少把記憶體中16KB的內容刷新到磁碟上。

img

對於InnoDB存儲引擎而言，所有的數據（存儲用戶數據的索引、各種元數據、系統數據）都是以頁的形式進行存儲的。

InnoDB頁的種類很多，比如存放Insert Buffer資訊的頁，存放undo日誌資訊的頁等，不過我們今天不關注其他亂七八糟的頁。這篇文章的主角是存放我們表中記錄的頁，姑且稱之為數據頁吧。

3. 數據頁的結構

很顯然，數據頁也會有自己的格式表示，像行格式一樣，我先列出兩個我們用到的欄位，其他的用到再說吧。

3.1 用戶記錄是如何存放的

image-20220223142635433

我們實際存儲的數據表記錄會按照指定的行格式存儲到圖中的User Records部分，如果當前的數據頁是新生成的，還沒有任何記錄的話，User Records部分其實並不會存在，而是從Free Space部分申請一塊空間劃分到User Records部分，當Free Space空間全部用完（或者剩餘的空間已經不足以承載新數據）的時候，意味著當前數據頁的空間被佔滿了，如果繼續插入記錄，就需要申請新的數據頁了，示意圖如下：

image-20220223145824983

要注意的是，上圖中的各條記錄之間通過next_record欄位串聯成了一個單鏈表，只不過我沒有在圖中畫出來罷了。

但是，只是串聯起來就可以了嗎？

如果讓我們來設計串聯的規則的話，我們肯定希望能夠按照某種「大小關係」來確定串聯的順序，而不是單純按照插入數據的順序，畢竟我們是學過數據結構的人啊！

可是記錄之間能比較大小嗎？能啊，這篇文章的題目就是關於主鍵啊，我們可以按照主鍵的順序，從小到大來串聯當前數據頁中的所有記錄。事實上，MySQL的設計者也確實是這麼設計的。

如果你足夠叛逆，你可能會想，你不設置主鍵的話是不是MySQL就崩了啊？

aa791103d96b5c95773851d62fb7cce4

當我們沒有設置主鍵的時候，為了防止這種情況，InnoDB會優先選取一個Unique鍵作為主鍵，如果表中連Unique鍵也沒有的話，就會自動為每一條記錄添加一個叫做DB_ROW_ID的列作為默認主鍵，只不過這個主鍵我們看不到罷了。

下面我們補充一下行格式

image-20220223160640229

再次強調

  • 我畫的欄位的順序並非在存儲設備中實際存儲的順序
  • 只有在InnoDB實在無法確定主鍵的情況下（創建時不指定主鍵，同時沒有Unique鍵），才會添加DB_ROW_ID列

3.2 番外：為什麼推薦使用自增ID作為主鍵，而不推薦使用UUID？

說到這，順便談一談為什麼推薦使用自增ID作為主鍵，而不推薦使用UUID？

除了UUID主鍵索引佔據大量空間的問題之外，在插入數據的資源開銷上，自增ID也遠小於UUID。由於數據頁中的記錄是按照主鍵從小到大進行串聯的，自增ID決定了後來插入的記錄一定會排列在上一條記錄的後面，只需要簡單添加next_record指針就可以了；如果當前數據頁寫滿，那就放心地直接插入新的數據頁中就可以了。

而UUID不同，它的大小順序是不確定的，後來插入的記錄有可能（而且概率相當大）插入到上一條記錄之前（甚至是當前數據頁之前），這就意味著需要遍歷當前數據頁的記錄（或者先找到相關的數據頁），然後找到自己的位置進行插入；如果當前數據頁寫滿了，只能先找到適合自己位置的數據頁，然後在數據頁中遍歷記錄找到自己的合適位置進行插入。

因此使用UUID的方式插入記錄花費的時間更長。

3.3 數據頁自帶的兩條偽記錄

實際上，InnoDB的設計者在InnoDB頁中添加了兩條偽記錄，一條Infimum，一條Supremum。並且設計者規定，當前數據頁的任何用戶記錄都比Infimum大，任何用戶記錄都比Supremum小。

因為是偽記錄，所以需要和User Records中的內容區分開，所以把這兩條偽記錄放在了一個叫做Infimum+Supremum的部分，見下圖：

image-20220223193804123

最終在數據頁中，用戶記錄的保存形式就成了這個樣子：

image-20220223213420368

上圖中我把真實數據資訊中的主鍵id值畫了出來，方便我們後續進行解釋。

你可能不太理解InnoDB設計者為什麼要無緣無故添加這兩個欄位，這倆貨對我們的搜索工作看起來沒有任何好處。

沒錯，這倆貨不是方便我們在數據頁中檢索數據而添加的，他們發揮作用的戰場是MySQL的LOCK_GAP記錄鎖。啥？不懂？沒事兒，我就是提一嘴而已，對這篇文章沒啥用，具體以後再說。。。

3.4 數據頁中主鍵的高效查詢方案

到目前為止，我們已經知道了在一個數據頁中，用戶記錄是按照主鍵由小到大的順序串聯而成的單向鏈表。接下來我們要解決的就是如何在一個數據頁中根據主鍵值搜索數據了。

如果我們執行下面這條查詢語句

SELECT * FROM row_format_table WHERE id = 4;

最簡單的辦法就是遍歷當前頁面的所有記錄，從Infimum記錄開始沿著單向鏈表進行搜索，直到找到id為4的記錄為止。記錄數量少的時候還好說，這要是有成千上萬條，那誰能受的了。

所以InnoDb設計者想出了一種絕妙的搜索方法，把數據頁中的所有記錄（包括偽記錄）分成若干個小組，每個小組選出組內最大的一條記錄作為「小組長」，接著把所有小組長的地址拿出來，編成目錄。

這就好比我們去學校找人，我們只知道他是幾年級的（確定數據頁），然後再問問每個班主任有沒有這個人（數據頁中的小組），而不是上來就直接遍歷整個年級的所有人。

為了使這種方案最大程度上發揮它的檢索效率（不能隨便分組，畢竟一個數據頁分成一個組或者每條記錄獨佔一個分組跟遍歷也沒什麼區別），所以InnoDB的設計者規定了如下分組方案：

  • Infimum偽記錄單獨分成一個組
  • Supremum偽記錄所在分組的記錄條數只能在1～8條之間
  • 其餘分組的記錄條數只能在4～8條之間

規則是這樣，可是InnoDB怎麼確定每個組內有多少個組員呢？設計者又想了一個辦法，給「小組長」添加一個屬性，記錄這個組內一共有多少個組員（包括自己）。所以我們再擴充一下行格式：

image-20220224093620650

小組長的n_owned值是組員的個數（包括自己），組員的n_owned值就是0。

接下來我們向表中多添加幾條數據，看看分組到底是什麼回事兒？需要注意的是，由於我們已經在表中指定了主鍵id，因此DB_ROW_ID這個參數不會再畫出來了。

image-20220224131812089

上圖中的所有記錄（包括偽記錄）分成了4個小組，每個小組的「組長」被單獨提拔，單獨編製成「目錄」，InnoDB官方稱之為「槽」。槽在物理空間中是連續的，意味著通過一個槽可以很輕鬆地找到它的上一個和下一個，這一點非常重要。

槽的編號從0開始，我們查找數據的時候先找到對應的槽，然後再到小組中進行遍歷即可，因為一個小組內的記錄數量並不多，遍歷的性能損耗可以忽略。而且每個槽代表的「組長」的主鍵值也是從小到大進行排列的，所以我們可以用二分法進行槽的快速查找。

圖中包含4個槽，分別是0、1、2、3，二分法查找之前，最低的槽low=0，最高的槽high=3。現在我們再來看看在這個數據頁中，我們查詢id為7的記錄，過程是怎樣的。

  1. 使用二分法，計算中間槽的位置，(0+3)/2=1，查看槽1對應的「組長」的主鍵值為4，因為4<7，所以設置low=1，high保持不變；
  2. 再次使用二分法，計算中間槽的位置，(1+3)/2=2，查看槽2對應的「組長」的主鍵值為8，因為8>7，所以設置high=2，low保持不變；
  3. 現在high=2，low=1，兩者相差1，已經沒有必要繼續進行二分了，可以確定我們的記錄就在槽2中，並且我們也能知道槽2對應的「組長」的主鍵是8，但是記錄之間是單向鏈表，我們無法向前遍歷。上文提到過，我們可以通過槽2找到槽1，進而找到它的「組長」，然後沿著「組長」向下遍歷直到找到主鍵為7的記錄就可以了。

說到這裡，我們已經非常清楚在一個數據頁中是如何根據主鍵進行搜索的。但是對於我們這篇文章的主題——MySQL的主鍵查詢為什麼這麼快，只能算是回答了一半，畢竟在數據頁中進行搜索的前提是你得先找到數據頁啊。這就是每次面試必問的MySQL索引的知識了，下一篇文章再介紹吧。

4. 重要！數據頁的其他欄位

最後再補充幾個知識點，文章中有兩個問題我並沒有講

  1. 槽是怎樣被存儲的？
  2. 二分查找的時候，怎麼知道目前有幾個槽呢？

先回答第1個問題，我們上文介紹過數據頁的結構，其實並不完整，下面我們再引入一個欄位Page Directory，槽就是保存在了這個欄位資訊里。

image-20220224141327504

Page Directory翻譯成中文就是「頁目錄」，這麼一來是不是更加深了你對槽這種目錄的理解呢？

至於第2個問題，其實也是關於數據頁結構的，之前沒有一下子全畫出來，因為我覺得需要的時候再加上更有助於記憶。

接下來我把所有之後會用到的數據頁的結構都給大家畫出來（很簡單，別害怕），暫時沒用的就屏蔽掉了，之後用到再說吧。

image-20220224145712709

  • FIL_PAGE_OFFSET

InnoDB頁的頁號，相當於這個頁的身份證

  • FIL_PAGE_PREV，FIL_PAGE_NEXT

看圖你就明白了吧，每個頁之間都是雙向鏈表

  • FIL_PAGE_TYPE

InnoDB頁的種類很多，比如我們這篇文章講的數據頁，還有其他的比如存放Insert Buffer資訊的頁，存放undo日誌資訊的頁等，這個欄位就是用來標識頁面的類型的

  • PAGE_N_DIR_SLOTS

這個欄位保存的就是槽的個數了，二分法就是根據這個欄位的值來確定high的值

  • PAGE_LAST_INSERT

當前頁面最後插入記錄的位置，當有新記錄插入的時候，直接讀取這個數據，將新記錄放到相應位置就可以了

  • PAGE_N_RECS

該頁中記錄的數量（不包括最小和最大記錄）

5. 推薦閱讀

這篇文章是索引的前夜，下期索引見！

Tags:

VirMach 便宜 VPS

QNews

QNews