對于 SQL 語句的執(zhí)行來說，定位 B-TREE 索引中的一條記錄，是個(gè)舉足輕重的能力。

InnoDB 是基于索引組織數(shù)據(jù)的，更新、刪除操作都需要先去索引中找到具體的記錄。

插入操作也需要先找到記錄要插入到索引的哪個(gè)位置。

查詢語句的 WHERE 條件能夠命中索引時(shí)，也需要先找到 WHERE 條件對應(yīng)的掃描區(qū)間的第一條記錄，然后從這條記錄開始沿著索引頁內(nèi)記錄之間的單向鏈表、索引頁之間的雙向鏈表依次讀取后續(xù)的記錄。

通過以上簡短的介紹，定位 B-TREE 索引中的記錄的重要性就顯而易見了。

本文是 MySQL 8 的第一篇文章，也是查詢優(yōu)化器的開篇。希望通過本文的介紹，能為大家理解后續(xù)文章打下一些基礎(chǔ)。

本文內(nèi)容基于 MySQL 8.0.29 源碼。

正文

1、 概述

更新、刪除、查詢操作定位索引中的一條記錄，插入操作找到要插入的位置，過程基本上是一樣的，源碼中也是在同一個(gè)方法中實(shí)現(xiàn)。

本文以 WHERE 條件能夠命中索引為前提，介紹查詢操作定位 WHERE 條件掃描區(qū)間的第一條記錄。

定位記錄過程中進(jìn)行的二分法查找、順序查找，會涉及到索引頁的部分結(jié)構(gòu)。

接下來會先用 2 個(gè)小節(jié)分別介紹掃描區(qū)間、以及和定位記錄過程相關(guān)的索引頁的部分結(jié)構(gòu)。

2、什么是掃描區(qū)間?

掃描區(qū)間就是 WHERE 條件中，由字段、關(guān)系運(yùn)算符(>、>=、<、<=、=)組成的，用于限定需要掃描記錄的范圍。

這個(gè)一句話描述太抽象，我們展開細(xì)說。

掃描區(qū)間可以按照不同維度分類：

• 按是否有界，可以分為有界區(qū)間、單側(cè)有界區(qū)間。
• 按開閉，可以分為開區(qū)間、閉區(qū)間、半開半閉區(qū)間。
• 特殊區(qū)間，單點(diǎn)區(qū)間。

有界區(qū)間

• 開區(qū)間，例如：WHERE a > 100 AND a < 200，掃描區(qū)間為 (100, 200)。
• 閉區(qū)間，例如：WHERE a >= 100 AND a <= 200，掃描區(qū)間為 [100, 200]。
• 左開右閉區(qū)間，例如：WHERE a > 100 AND a <= 200，掃描區(qū)間為 (100, 200]。
• 左閉右開區(qū)間，例如：WHERE a >= 100 AND a < 200，掃描區(qū)間為 [100, 200)。

單側(cè)有界區(qū)間

• 有下界，左開區(qū)間，例如：WHERE a > 100，掃描區(qū)間為 (100, +∞)。
• 有下界，左閉區(qū)間，例如：WHERE a >= 100，掃描區(qū)間為 [100, +∞)。
• 有上界，右開區(qū)間，例如：WHERE a < 200，掃描區(qū)間為 (-∞, 200)。
• 有上界，右閉區(qū)間，例如：WHERE a <= 200，掃描區(qū)間為 (-∞, 200]。

單點(diǎn)區(qū)間

• 只有一個(gè)值的區(qū)間，例如：WHERE a = 100，掃描區(qū)間為 [100, 100]。

3、索引頁結(jié)構(gòu)

B-TREE 索引的根結(jié)點(diǎn)、內(nèi)結(jié)點(diǎn)、葉結(jié)點(diǎn)，都是索引頁。

索引頁內(nèi)部結(jié)構(gòu)比較復(fù)雜，以后會有文章專門介紹整個(gè)索引頁的結(jié)構(gòu)，接下來我們只介紹定位記錄需要用到的結(jié)構(gòu)：偽記錄、記錄鏈表、槽(SLOT，也可以叫記錄分組)。

記錄鏈表

索引頁每條記錄的頭信息中，都有一個(gè) 2 字節(jié)的空間，保存著下一條記錄在當(dāng)前索引頁中的偏移量。

偏移量，是記錄的數(shù)據(jù)(不包含記錄頭信息)的第一個(gè)字節(jié)的地址，減去索引頁的第一個(gè)字節(jié)的地址得到的數(shù)字。

InnoDB 索引頁最大可以設(shè)置為 64K，2 字節(jié)就可以表示索引頁中任何一個(gè)字節(jié)的偏移量。

這個(gè) 2 字節(jié)的空間，叫作 next_record，通過 next_record 可以把索引頁中的記錄串起來形成一個(gè)單向鏈表。

從任何一條記錄開始，一直往后遍歷，都能到達(dá)當(dāng)前索引頁中的最后一條記錄。

偽記錄

偽記錄指的是索引頁中，不是由用戶插入，而是 InnoDB 偷偷插入的記錄。

不管索引頁中是否有用戶插入的記錄(用戶記錄)，每個(gè)索引頁中都會有 2 條偽記錄：

• infimum，索引頁中的第一條記錄。

索引頁中有用戶記錄時(shí)，infimum 的 next_record 指向第一條用戶記錄。

索引頁中沒有用戶記錄時(shí)，infimum 的 next_record 指向 supremum 記錄。

• supremum，索引頁中的最后一條記錄。

槽(SLOT)

索引頁中的 槽 分為 3 種類型：

• infimum 槽，只包含一條記錄，就是 infimum 偽記錄。
• supremum 槽，包含 1 ~ 8 條記錄，最后一條是 supremum 偽記錄，其余的是用戶記錄。
• 普通槽，包含 4 ~ 8 條用戶記錄。

每個(gè)槽占用 2 字節(jié)，保存著該槽對應(yīng)的 N 條記錄中，最大的那條記錄在當(dāng)前索引頁中的偏移量。

最大記錄指的是槽中按照索引字段升序排序的最后一條記錄。

索引頁中的槽，存儲在索引頁的一個(gè)專門的區(qū)域，這個(gè)區(qū)域叫作頁目錄(Page Directory)。

頁目錄區(qū)域中的槽是按照倒序排序，并且是緊挨著存儲的，第一個(gè)槽的位置在最后，第二個(gè)槽的位置在倒數(shù)第二個(gè)，依此類推，最后一個(gè)槽的位置在第一個(gè)。

4、定位掃描區(qū)間的第一條記錄

（1）抽象過程描述

B+ 樹索引包含根結(jié)點(diǎn)、內(nèi)結(jié)點(diǎn)、葉結(jié)點(diǎn)，在一棵 3 層的 B+ 樹中定位掃描區(qū)間的第一條記錄，大體流程如下：

• 從根結(jié)點(diǎn)開始，確定記錄在哪個(gè)內(nèi)結(jié)點(diǎn)中。
• 進(jìn)入內(nèi)結(jié)點(diǎn)，確定記錄在哪個(gè)葉結(jié)點(diǎn)中。
• 進(jìn)入葉結(jié)點(diǎn)，確定記錄的位置。

隨著 B+ 樹的層級增多或減少，以上步驟也會相應(yīng)的增多或減少。

上述流程中的每一個(gè)步驟，內(nèi)部過程是一樣的，都需要先進(jìn)行二分法查找、再進(jìn)行順序查找。

最后，如果是根結(jié)點(diǎn)和內(nèi)結(jié)點(diǎn)，就再進(jìn)入下一個(gè)步驟;如果是葉結(jié)點(diǎn)，就沒有然后了。

二分法查找、順序查找過程如下：

第 1 步，通過二分法查找，確定記錄屬于哪個(gè)槽。

每個(gè)索引頁的頭信息中有一個(gè) 2 字節(jié)的區(qū)域，存放著當(dāng)前索引頁中有多少個(gè)槽，這個(gè)區(qū)域的名字叫作 PAGE_N_DIR_SLOTS。

讀取 PAGE_N_DIR_SLOTS 的值，得到槽的數(shù)量，然后減 1，計(jì)算出槽的最大序號：high = PAGE_N_DIR_SLOTS - 1，由此，我們就得到了二分法的初始狀態(tài)的上邊界。

初始狀態(tài)的下邊界，就是第一個(gè)槽(infimum 槽)的序號，low = 0。

二分法查找可能會進(jìn)行 0 ~ N 輪(N >= 1)，每一輪查找，都會先通過 mid = (low + high) / 2 計(jì)算出中間位置。

然后，判斷要查找的記錄是在 low 區(qū)間(low ~ mid)，還是在 high 區(qū)間(mid ~ high)。

最后，根據(jù)判斷結(jié)果，進(jìn)入 low 區(qū)間或 high 區(qū)間，查找范圍就縮小了一半，繼續(xù)進(jìn)行下一輪查找，依此類推，直到 low 和 high 的值不滿足循條件 high - low > 1，二分法查找結(jié)束。

這里的二分法，不僅要支持單點(diǎn)掃描區(qū)間，還要支持大于、大于等于、小于、小于等于這些范圍掃描區(qū)間，不能找到一條滿足掃描區(qū)間的記錄之后就馬上停下來，而是要等到 low 和 high 的值不滿足循環(huán)條件，才能結(jié)束二分法查找的過程。

二分法查找結(jié)束時(shí)，要查找的記錄總是屬于high 槽(上邊界 high 對應(yīng)的槽)，low 槽 總是 high 槽的前一個(gè)槽。這對于第 2 步順序查找能夠順利的找到記錄在槽中的位置很關(guān)鍵。

第 2 步，確定記錄所在的槽之后，沿著每條記錄頭信息中的 next_record 順序查找，確定記錄在槽中的位置。

以二分法查找結(jié)束時(shí)的狀態(tài)為基礎(chǔ)，繼續(xù)進(jìn)行順序查找。

從 low 槽的最大記錄開始，通過頭信息中的 next_record 讀取下一條記錄。

比較下一條記錄中索引字段值和掃描區(qū)間的字段值，判斷下一條記錄是不是掃描區(qū)間的第一條記錄。

如果是，順序查找過程結(jié)束。

如果不是，繼續(xù)讀取下一條記錄，并判斷是否是掃描區(qū)間的第一條記錄，依此類推，直到要讀取的下一條記錄是 high 槽中的最大記錄，查找過程結(jié)束。

接下來，我們通過一個(gè)例子來把上面描述的抽象過程具體化。

（2）準(zhǔn)備一棵 B+ 樹

有一個(gè)主鍵索引，包含一個(gè) int 類型的 id 字段，結(jié)構(gòu)為 B+ 樹，包含 2 層：根結(jié)點(diǎn)、葉結(jié)點(diǎn)，索引結(jié)構(gòu)如下圖所示：

我們以定位 id >= 700 查詢條件對應(yīng)的掃描區(qū)間 [700, +∞) 的第一條記錄為例，來分析在 B+ 樹索引中定位掃描區(qū)間的第一條記錄的過程。

（3）記錄在哪個(gè)葉結(jié)點(diǎn)?

示例索引的 B+ 樹，包含根結(jié)點(diǎn)、葉結(jié)點(diǎn)兩層，定位掃描區(qū)間的第一條記錄，從根結(jié)點(diǎn)開始。

根據(jù)抽象過程描述的步驟，先通過二分法查找確定 [700, +∞) 掃描區(qū)間的第一條記錄在哪個(gè)槽。

示例索引的 B+ 樹，根結(jié)點(diǎn)中有 8 個(gè)槽，初始狀態(tài)下，二分法的上下邊界分別為：low = 0、high = 8 - 1 = 7。

二分法查找

第 1 輪，計(jì)算中間位置 mid = (low + high) / 2 = (0 + 7) / 2 = 3，得到 low 區(qū)間(low ~ mid => 0 ~ 3)、high 區(qū)間(mid ~ high => 3 ~ 7)。

中間位置對應(yīng)槽 3(序號為 3 的槽)，其最大記錄的 id = 41，小于掃描區(qū)間左端點(diǎn)值 700，說明 id >= 700 的第一條記錄(后面就直接稱為第一條記錄了)位于 high 區(qū)間。

修改下邊界值，low = mid = 3，進(jìn)入 high 區(qū)間。

第 2 輪，計(jì)算中間位置 mid = (low + high) / 2 = (3 + 7) / 2 = 5，得到 low 區(qū)間(3 ~ 5)、high 區(qū)間(5 ~ 7)。

中間位置對應(yīng)槽 5，其最大記錄的 id = 81，小于掃描區(qū)間左端點(diǎn)值 700，說明第一條記錄位于 high 區(qū)間。

修改下邊界值，low = mid = 5，進(jìn)入 high 區(qū)間。

第 3 輪，計(jì)算中間位置 mid = (low + high) / 2 = (5 + 7) / 2 = 6，得到 low 區(qū)間(5 ~ 6)、high 區(qū)間(6 ~ 7)。

中間位置對應(yīng)槽 6，其最大記錄的 id = 901，大于掃描區(qū)間左端點(diǎn)值 700，說明第一條記錄位于 low 區(qū)間。

修改上邊界值，high = mid = 6。

然后，high - low = 6 - 5 = 1，不滿足循環(huán)條件 high - low > 1，二分法查找結(jié)束。

掃描區(qū)間左端點(diǎn)值 700，大于槽 5的最大記錄的 id 值(81)，小于槽 6的最大記錄的 id 值(901)，說明第一條記錄屬于槽 6 的管轄范圍(此時(shí)，槽 6 就是 high 槽)。

接下來，就要進(jìn)入順序查找的主場，去尋找第一條記錄在槽中的位置了。

順序查找

二分法查找結(jié)束時(shí)，low = 5(槽 5)，其最大記錄的 id = 81;high = 6(槽 6)，其最大記錄的 id = 901。

二分法查找過程中，已經(jīng)確定了掃描區(qū)間左端點(diǎn)值 700 在槽 6中，所以，在順序查找過程中，不需要讀取 id = 81 這條記錄(槽 5的最后一條記錄)，而是從這條記錄的下一條記錄，也就是槽 6 的第一條記錄開始。

第 1 輪，讀取 id = 81 的下一條記錄，得到 id = 101 的記錄，101 小于掃描區(qū)間左端點(diǎn)值 700，還需要繼續(xù)讀取下一條記錄進(jìn)行比較。

第 2 輪，讀取 id = 101 的下一條記錄，得到 id = 888 的記錄，888 大于掃描區(qū)間左端點(diǎn)值 700，也就鎖定了 id >= 700 的第一條記錄，位于 id 為 101 ~ 888 的記錄之間，也就是在 id = 888 之前。

然而，id = 888 這條記錄，是其所在的葉結(jié)點(diǎn)索引頁的第一條用戶記錄。

id >= 700 的第一條記錄，不可能和 id = 888 這條記錄同處于一個(gè)索引頁了，只能立足于這個(gè)索引頁的前一個(gè)索引頁。

根結(jié)點(diǎn)中 id = 101 是 id = 888 的前一條記錄，id = 101 所在的葉結(jié)點(diǎn)索引頁就是 id = 888 所在的葉結(jié)點(diǎn)索引頁的前一頁了。

最終，id >= 700 的第一條記錄，也就位于 id = 101 這條記錄所在的葉結(jié)點(diǎn)索引頁中了。

至此，經(jīng)過 2 輪比較，就已經(jīng)確定了 id >= 700 的第一條記錄所在的葉結(jié)點(diǎn)索引頁了，順序查找過程結(jié)束。

接下來，從 id = 101 這條記錄中讀取其對應(yīng)的葉結(jié)點(diǎn)索引頁的頁號，進(jìn)入葉結(jié)點(diǎn)。

（4）記錄在葉結(jié)點(diǎn)的哪個(gè)位置?

示例索引的 B+ 樹，葉結(jié)點(diǎn)中有 10 個(gè)槽，初始化狀態(tài)下，二分法查找的上下邊界分別為：low = 0，high = 10 - 1 = 9。

二分法查找

第 1 輪，計(jì)算中間位置 mid = (low + high) / 2 = (0 + 9) / 2 = 4，得到 low 區(qū)間(low ~ mid => 0 ~ 4)、high 區(qū)間(mid ~ high => 4 ~ 9)。

中間位置對應(yīng)槽 4，其最大記錄的 id = 404，小于掃描區(qū)間左端點(diǎn)值 700，說明 id >= 700 的第一條記錄(簡稱為第一條記錄)位于 high 區(qū)間。

修改下邊界值，low = mid = 4，進(jìn)入 high 區(qū)間。

第 2 輪，計(jì)算中間位置 mid = (low + high) / 2 = (4 + 9) / 2 = 6，得到 low 區(qū)間(4 ~ 6)、high 區(qū)間(6 ~ 9)。

中間位置對應(yīng)槽 6，其最大記錄的 id = 606，小于掃描區(qū)間左端點(diǎn)值 700，說明第一條記錄位于 high 區(qū)間。

修改下邊界值，low = mid = 6，進(jìn)入 high 區(qū)間。

第 3 輪，計(jì)算中間位置 mid = (low + high) / 2 = (6 + 9) / 2 = 7，得到 low 區(qū)間(6 ~ 7)、high 區(qū)間(7 ~ 9)。

中間位置對應(yīng)槽 7，其最大記錄的 id = 707，大于掃描區(qū)間左端點(diǎn)值 700，說明第一條記錄位于 low 區(qū)間。

修改上邊界值，up = mid = 7，此時(shí)，high - low = 7 - 6 = 1，不滿足循環(huán)條件 up - low > 1，循環(huán)結(jié)束。

掃描區(qū)間左端點(diǎn)值 700，大于槽 6 的最大記錄的 id(606)，小于槽 7 的最大記錄的 id(707)，說明第一條記錄屬于槽 7 的管轄范圍(此時(shí)，槽 7就是 high 槽)。

接下來，就要去尋找第一條記錄在槽中的位置了。

順序查找

二分法查找結(jié)束時(shí)，low = 6(槽 6)，其最大記錄的 id = 606;high = 7(槽 7)，其最大記錄的 id = 707。

二分法查找過程中，已經(jīng)確定了第一條記錄在槽 7 的范圍內(nèi)，所以，在順序查找過程中，不需要讀取 id = 606 這條記錄(槽 6 的最后一條記錄)，而是從這條記錄的下一條記錄，也就是槽 7 的第一條記錄開始。

第 1 輪，讀取 id = 606 的下一條記錄，得到 id = 666 的記錄，666 小于掃描區(qū)間左端點(diǎn)值 700，還需要讀取下一條記錄進(jìn)行比較。

第 2 輪，讀取 id = 666 的下一條記錄，得到 id = 688 的記錄，688 小于掃描區(qū)間左端點(diǎn)值 700，繼續(xù)讀取下一條記錄。

第 3 輪，讀取 id = 688 的下一條記錄，得到 id = 700 的記錄，700 等于掃描區(qū)間左端點(diǎn)值 700， 滿足 id >= 700 條件。

至此，經(jīng)過 3 輪比較，已找到 id >= 700 對應(yīng)的掃描區(qū)間 [700, +∞) 的第一條記錄，葉結(jié)點(diǎn)的順序查找過程結(jié)束，定位掃描區(qū)間的第一條記錄的整個(gè)過程也結(jié)束了。

5、 性能優(yōu)化

前面介紹二分法查找定位槽、順序查找定位記錄位置的過程中，都涉及到對掃描區(qū)間字段值和索引字段值進(jìn)行比較，但是我們沒有更進(jìn)一步介紹比較的過程。

如果只是常規(guī)的比較，無非是循環(huán)掃描區(qū)間的字段，逐個(gè)和索引中對應(yīng)的字段進(jìn)行比較，這也就不需要再多說什么了。

但是，InnoDB 對比較的過程進(jìn)行了優(yōu)化，對于已經(jīng)比較過的字段、字段前面的部分內(nèi)容，盡可能避免進(jìn)行重復(fù)比較，從而提升二分法查找、順序查找過程的執(zhí)行效率，以提升性能。

InnoDB 對于葉結(jié)點(diǎn)的優(yōu)化相比于根結(jié)點(diǎn)、內(nèi)結(jié)點(diǎn)來說更進(jìn)一步，我們分兩個(gè)小節(jié)分別介紹對于根結(jié)點(diǎn) & 內(nèi)結(jié)點(diǎn)、葉結(jié)點(diǎn)的二分法查找、順序查找的優(yōu)化。

（1）根結(jié)點(diǎn)、內(nèi)結(jié)點(diǎn)優(yōu)化

我們基于上圖索引頁中槽的示例數(shù)據(jù)，以查詢條件 i1 >= 160 and i2 >= 44 為例，來分析定位掃描區(qū)間左端點(diǎn) 160, 44(用這個(gè)代表掃描區(qū)間的第一條記錄) 在哪個(gè)槽中的過程。

初始狀態(tài)下，二分法查找的上下邊界為：low = 0，high = 13。

二分法查找

第 1 輪，計(jì)算中間位置 mid = (low + high) / 2 = (0 + 13) / 2 = 6，得到 low 區(qū)間(low ~ mid => 0 ~ 6)、high 區(qū)間(mid ~ high => 6 ~ 13)。

中間位置對應(yīng)槽 6，其最大記錄的 i1 = 160、i2 = 33，逐個(gè)比較掃描區(qū)間左端點(diǎn)和槽 6 的最大記錄的 i1、i2 字段值，以確定掃描區(qū)間左端點(diǎn)位于 low 區(qū)間還是 high 區(qū)間。

先比較 i1 字段值，掃描區(qū)間左端點(diǎn)的 i1 字段值和索引中的 i1 字段值都等于 160。

接著比較 i2 字段的值，掃描區(qū)間左端點(diǎn)的 i2 字段值(44)大于索引記錄中的 i2 字段值(33)，說明掃描區(qū)間左端點(diǎn)值 160, 44 位于 high 區(qū)間(槽 6 ~ 13)。

修改下邊界值，low = mid = 6，進(jìn)入 high 區(qū)間。

第 2 輪，計(jì)算中間位置 mid = (low + high) / 2 = (6 + 13) / 2 = 9，得到 low 區(qū)間(6 ~ 9)、high 區(qū)間(9 ~ 13)。

中間位置對應(yīng)槽 9，其最大記錄的 i1 = 160，i2 = 66，逐個(gè)比較掃描區(qū)間左端點(diǎn)和槽 9 的最大記錄的 i1、i2 字段值，以確定掃描區(qū)間左端點(diǎn)位于 low 區(qū)間還是 high 區(qū)間。

先比較 i1 字段值，掃描區(qū)間左端點(diǎn)的 i1 字段值和索引記錄中的 i1 字段值都等于 160。

接著比較 i2 字段的值，掃描區(qū)間左端點(diǎn)的 i2 字段值(44)小于索引記錄中的 i2 字段值(66)，說明掃描區(qū)間左端點(diǎn)值 160, 44 位于 low 區(qū)間(槽 6 ~ 9)。

修改上邊界值，high = mid = 9，進(jìn)入 low 區(qū)間。

第 3 輪，計(jì)算中間位置 mid = (low + high) / 2 = (6 + 9) / 2 = 7，得到 low 區(qū)間(6 ~ 7)、high 區(qū)間(7 ~ 9)。

中間位置對應(yīng)槽 7，其最大記錄的 i1 = 160，i2 = 44。

按照第 1、2 輪的套路，接下來該逐個(gè)比較掃描區(qū)間左端點(diǎn)和槽 7 的最大記錄的 i1、i2 字段值了。

但是 ……，重點(diǎn)來了，經(jīng)過第 1 輪比較，確定了掃描區(qū)間左端點(diǎn)值 160, 44 位于槽 6 ~ 13 之間;經(jīng)過第 2 輪比較，確定了掃描區(qū)間左端點(diǎn)值 160, 44 位于槽 6 ~ 9 之間。

取交集可得：掃描區(qū)間左端點(diǎn)值 160, 44 位于槽 6 ~ 9 之間。

從前面的示意圖中可見，槽 6 ~ 9 之間，每個(gè)槽的最大記錄的 i1 字段值都是 160，掃描區(qū)間左端點(diǎn)的 i1 字段值也是 160。

在這個(gè)范圍內(nèi)，不管接下來要進(jìn)行多少輪比較，都能夠很確定的知道記錄的 i1 字段值是等于掃描區(qū)間左端點(diǎn)的 i1 字段值的。

既然在比較之前就已經(jīng)能確定比較的結(jié)果是相等的，也就不用比較了 i1 字段的值了。

二分法查找結(jié)束之后，后面的順序查找過程，也是在這個(gè)范圍之內(nèi)，也都可以不用比較 i1 字段的值了。

好了，這一節(jié)我們要講的是 InnoDB 對定位過程的優(yōu)化，目標(biāo)已經(jīng)達(dá)成，對于上面的例子，剩下的二分法查找和順序查找過程，就不再接著往下分析了。

（2）葉結(jié)點(diǎn)優(yōu)化

如果能夠在二分法查找過程中鎖定一個(gè)范圍，葉結(jié)點(diǎn)的二分法查找、順序查找過程，不但能跳過前面 N 個(gè)已經(jīng)比較過并且相等的字段，還能更進(jìn)一步，跳過第 N + 1 個(gè)字段中已經(jīng)比較過并且相等的前 M 字節(jié)。

不過，跳過已經(jīng)比較過的字節(jié)有一些限制，只能應(yīng)用于以下字段：

• tinyint、int、smallint、mediumint、bigint、tinyblob、blob、mediumblob、longblob、binary、varbinary 類型的字段。
• InnoDB B-TREE 根結(jié)點(diǎn)、內(nèi)結(jié)點(diǎn)的記錄中指向子結(jié)點(diǎn)索引頁的頁號。
• InnoDB B-TREE 葉結(jié)點(diǎn)記錄中的 DB_ROW_ID、DB_TRX_ID、DB_ROLL_PTR 字段。

以上這些類型的字段，在二分法查找和順序查找的過程中，源碼中是要循環(huán)字段內(nèi)容，逐字節(jié)進(jìn)行比較的。

我們還是以一個(gè)具體例子來說明：

有一個(gè) B-TREE 索引，包含 2 個(gè)字段，i1 為 int 類型，b1 為 blob 類型，如下圖所示：

假設(shè)掃描區(qū)間左端點(diǎn)的 i1 字段值為 160，b1 字段值的前 1000 字節(jié)為 0x001 0x002 … 0x999 0x1000。

再次假設(shè)，經(jīng)過前 2 輪比較已經(jīng)鎖定了掃描區(qū)間的左端點(diǎn)值在 槽 6 ~ 槽 9 之間，這個(gè)區(qū)間內(nèi)所有記錄的 i1 字段值都是 160，所有記錄的 b1 字段前 1000 字節(jié)都是 0x001 0x002 … 0x999 0x1000。

如果在第 3 輪及以后的二分法查找、順序查找過程中，只能跳過已經(jīng)比較過的 i1 字段，對于 b1 字段，每次都要從第 1 個(gè)字節(jié)開始比較，前 1000 字節(jié)的逐字節(jié)比較就重復(fù)了。

按照我們前面介紹的場景，在鎖定范圍內(nèi)(槽 6 ~ 9)，掃描區(qū)間左端點(diǎn)的 i1 字段和所有記錄的 i1 字段值都相等;b1 字段前 1000 字節(jié)也都相等，也不用比較，是可以跳過的。

那么，在二分法查找的后續(xù)比較、順序查找過程中，只需要從 b1 字段的第 1001 字節(jié)開始比較，又能更多的避免一些重復(fù)的比較操作了。

6、總結(jié)

正式進(jìn)入本文主題內(nèi)容之前，2、3 小節(jié)先介紹了掃描區(qū)間的定義，以及舉例說明了每種類型的掃描區(qū)間;然后介紹了索引頁中和本文關(guān)聯(lián)比較大的結(jié)構(gòu)：記錄鏈表、偽記錄、槽(SLOT)。

4 小節(jié)先對二分法查找定位槽、順序查找定位槽中的記錄進(jìn)行抽象的過程描述，然后，以一個(gè) 2 層的 B-TREE 索引為例，詳細(xì)分析了二分法查找定位槽、順序查找定位槽中記錄的每一步。

5 小節(jié)介紹了 InnoDB 為了減少二分法查找定位槽、順序查找定位槽中記錄的過程中的比較次數(shù)，在鎖定一個(gè)范圍之后，對于根結(jié)點(diǎn)、內(nèi)結(jié)點(diǎn)，能夠跳過已經(jīng)比較過并確認(rèn)為相等的字段;對于葉結(jié)點(diǎn)，除了能跳過字段，還能跳過字段中已經(jīng)比較過并確認(rèn)為相等的前面的部分字節(jié)。

本文轉(zhuǎn)載自微信公眾號「一樹一溪」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系一樹一溪公眾號。