導讀

在《為什么MySQL能夠支撐千萬數據規模的快速查詢？》中，我詳細講解了InnoDB B-Tree的結構，同時，我以下面這條SQL舉例：

SELECT * FROM user WHERE age >= 15

講解了該查詢是如何搜索輔助索引index_age_birth這顆索引樹的。其中，我在查找葉子節點時，說到從節點內第一條記錄開始，向右遍歷該節點內所有記錄即可定位到滿足條件的第一條記錄，然后，遍歷該記錄后繼所有記錄，即可得到滿足條件的所有記錄。

但是，如果葉子節點內的記錄太多，而滿足條件的第一條記錄又不在頭部位置，那么，順序遍歷查找的性能是很差的。該如何解決這個問題呢？我想，你可能已經猜到了，是的，由于葉子節點的記錄是升序排列的，我們完全可以用二分查找，快速定位到滿足條件的第一條記錄。

那么，InnoDB具體是怎么做的呢？

槽

我以用戶表索引index_age_birth為例，先來看一下該索引葉子節點的結構：

見上圖，跟之前我講的輔助索引B-Tree的葉子節點是不是不一樣？是的，之前我講的比較粗，現在我把它細化了，為了詳細講解一個查詢是如何在B-Tree的葉子節點中定位一條記錄的。

我們來仔細看下上面這張圖，相比之前的葉子節點，這張圖多出來三個元素：

infimum：葉子節點中的虛擬記錄，該記錄的下一條記錄即為葉子節點中的最小記錄。比如：圖中<15, 2007-06-06, 6>為頁4這個葉子節點中的最小記錄。

supremum：葉子節點中的虛擬記錄，該記錄的上一條記錄為葉子節點中的最大記錄。比如：圖中<18, 2007-06-10, 12>為頁4這個葉子節點中的最大記錄。

槽：InnoDB將葉子節點內的記錄分成幾組，每一組由一個叫做slot，也就是槽指向分組內最大的一條記錄。這個槽有以下幾個特點：

(1) 槽內存儲的是一個偏移量，這個偏移量是從葉子節點0字節開始計算的。比如：

? a. 圖中的99，表示從葉子節點0字節開始第115字節的位置為槽0。

? b. 圖中的252，表示從葉子節點0字節開始第99字節的位置為槽1。

? c. 圖中的112，表示從葉子節點0字節開始第220字節的位置為槽2。

為啥需要偏移量？為了根據偏移量定位該偏移量位置所在的記錄。

(2) 一個槽指向一個分組中的最大記錄。比如，圖中，橘色框代表分組，所以，槽1指向第二個分組的最大記錄<17, 2007-06-10, 11>。

(3) 槽與槽之間組成一個無序數組，但槽的下標是有序的。比如，圖中，99、252、112這3個偏移量是無序的，但是，槽的下標0、1、2是有序的。

這時，你可能會有個疑問：為什么第一個分組只有1條記錄，第二個分組有4條記錄，而最后一個分組有2條記錄？

因為InnoDB引擎規定：對于infimum記錄所在的分組只能有 1 條記錄，supremum記錄所在的分組擁有的記錄條數只能在 1~8 條之間，剩下的分組中記錄的條數范圍只能在是 4~8 條之間。

下面，我結合槽的結構定義，詳細講解InnoDB在葉子節點中定位記錄的過程。

查找過程

InnoDB查找葉子節點的過程采用的是對槽二分查找，槽所指記錄所在分組內順序查找的方式。至于為什么槽內不用二分查找，是因為槽指向的記錄所在分組記錄總數不會超過8條，所以，沒必要使用二分查找來提升查找性能。

我以本章《導讀》中的SQL為例，詳細講解InnoDB在葉子節點中如何查找第一條滿足查詢條件的記錄。

SELECT * FROM user WHERE age >= 15

見下面5張圖，其中的葉子節點都是索引index_age_birth這個B-Tree的，頁4是通過B-Tree搜索定位的葉子節點：

說明：

定位最小下標的槽為low，即圖(1)中的槽0，定位最大下標的槽為high，即圖(1)中的槽2。

(low + high) / 2進行二分查找，即(0 + 2) / 2 = 1，所以，定位槽1，見圖(2)，找到槽1指向的記錄<17, 2007-06-10, 11>。

該記錄age = 17，查詢條件age的值為15，17 > 15，說明目標記錄在該記錄左邊，所以，見圖(2)，high指向槽1，由于low指向槽0，high - low = 1，所以，查找記錄在槽0和槽1之間。

見圖3，將low_rec指向槽0指向的infimum記錄，high_rec指向槽1指向的<17, 2007-06-10, 11>記錄，從槽0指向的記錄，即從infimum記錄開始向右遍歷記錄。ps：圖(3)和(4)為了更清晰地描述槽指向記錄所在的分組內部的查找過程，將槽移除了。

遍歷到第二條記錄<15, 2007-06-06, 6>，見圖(4)，該記錄age = 15，查詢條件age的值為15，15 = 15，所以，該記錄為滿足查詢條件的第一條記錄，low_rec指向該記錄。

遍歷到第三條記錄<16, 2007-06-08, 8>，見圖(5)，該記錄age = 16，查詢條件age的值為15，16 > 15，所以，high_rec指向該記錄。

high_rec和low_rec間隔1，說明查找結束，最終，定位滿足查詢條件age >= 15的第一條記錄為<15, 2007-06-06, 6>。

在這個查找過程中，你可能有個疑問，我都已經在第5步找到了滿足條件的第一條記錄，為什么還要進行第6步？

因為這個查找過程是一個通用算法，假設我們要查找age = 16的記錄，那么，頁4中包含兩條滿足條件的記錄，結合上面的查找算法，是不是要執行到第6、7步才能找到所有匹配的記錄？！所以，InnoDB采用了該通用查找算法，覆蓋age >= 15和age = 16兩個場景。

小結

最后，我來總結一下本章講解的內容：

槽的結構：將葉子節點分組，槽指向每組中最大的一條記錄，槽中存儲其指向記錄在葉子節點內的偏移量，該偏移量是相對葉子節點0字節計算得到的。

InnoDB查找索引樹葉子節點的過程： 對槽二分查找，槽指向記錄所在的分組內順序查找。

思考題

InnoDB直接對葉子節點記錄進行二分查找不香嗎？為什么要引入槽的概念查找索引樹葉子節點，即對槽二分查找，槽指向記錄所在的分組內順序查找？

總結

以上是生活随笔為你收集整理的earcharts tree 节点间隔_InnoDB是顺序查找B-Tree叶子节点的吗？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。