導讀：

? 我們已經知道了頁是數據庫存儲的基本單位，知道了一條行記錄的存儲格式是怎樣的，當數據越來越多時，那一條條行記錄具體又是怎么在頁中被組織起來的呢？

一、InnoDB數據頁結構

二、總結

1、一條條行數據是如何在數據頁中被組織起來的？

? 首先，在每一個數據頁中存在兩個虛擬記錄，一個代表最小記錄，一個代表最大記錄，它們被存儲在數據頁的 Infimum + Supremum 部分。

? 緊接著，當向表中插入一些數據時，這些記錄會被存儲在數據頁中的 User Records 中，這里不僅存儲了其真實內容，還有存儲了一些額外的數據，比如頭信息中的 next_record，通過這個標記加上兩個虛擬記錄，使得記錄形成了一條按照主鍵值由小到大的順序的單鏈表(非插入順序)。

? 然后，為了數據能夠查的更快，將數據頁中的數據進行了分組，每組最后一個記錄的地址偏移量作為槽，存放在 Page Directory(頁目錄)，這樣對于之后通過主鍵查詢記錄時，只需通過二分法確定目標結果存儲在哪個組，然后在組中通過記錄的 next_record 屬性進行遍歷即可找到目標。這樣就完成了一個數據頁中數據的組織。

? 最后，一個數據頁默認大小為 16 KB，當一個數據頁不足存儲新數據時，將會申請新的數據頁進行存儲。此時，數據頁結構中的 File Header 就發揮作用，其包含 FIL_PAGE_PREV 和 FIL_PAGE_NEXT 兩個屬性，它們分別代表本頁的上一個和下一個頁的頁號，這樣就可通過這兩個屬性將許許多多的頁就都串聯起來了，形成一個雙向鏈表。

? 總的來說，各個數據頁可以組成一個雙向鏈表，而每個數據頁中的記錄會按照主鍵值從小到大的順序組成一個單向鏈表，每個數據頁都會為存儲在它里邊兒的記錄生成一個頁目錄，在通過主鍵查找某條記錄的時候可以在頁目錄中使用二分法快速定位到對應的槽，然后再遍歷該槽對應分組中的記錄即可快速找到指定的記錄。

三、在 MySQL InnoDB 的頁目錄（Page Directory）設計中，為什么槽（Slot）記錄的是分組中??最大主鍵值??，而不是最小值？

? 在 InnoDB 數據頁中，所有記錄按主鍵順序物理存儲（升序排列）。頁目錄的槽將這些記錄分成多個分組（例如，每個分組通常包含 4-8 條記錄），槽的信息允許二分查找快速定位目標記錄所在的分組，然后在該分組內進行線性查找（因為分組內記錄數量較少，線性查找代價低）。使用最大主鍵值作為槽值的核心原因是：它使二分查找的決策更簡單、更高效，減少了比較操作的歧義，并能直接利用主鍵單調遞增的特性。

1、為什么最大值優于最小值？

1.1、使用最大值時的二分查找邏輯??：當目標主鍵（Target Key）與槽值比較時：

• 如果目標主鍵 <= 槽值（分組最大主鍵），則目標記錄可能位于該槽對應的分組或更早的分組（因為槽值是該分組的最大主鍵，目標值不超過最大值說明它可能在這個分組內）。
• 如果目標主鍵 > 槽值，則目標記錄一定位于后續的分組（因為分組最大主鍵小于目標值，說明目標不在當前或之前的任何分組）。

? 這允許二分查找高效調整搜索范圍（例如，調整 high 或 low 指針），每次比較都能明確縮小搜索范圍，沒有歧義。

1.2、使用最小值時的二分查找問題??：如果槽記錄分組的最小主鍵值：

• 如果目標主鍵 < 槽值（分組最小主鍵），則目標記錄一定位于更早的分組。
• 如果目標主鍵 >= 槽值，則目標記錄可能位于該槽對應的分組或更晚的分組。

? 這種方式在比較時存在歧義：當目標主鍵 >= 槽值時，無法立即確定目標是否在分組內，因為分組最小主鍵只表示分組的起始點，但分組可能包含更大的值（例如，目標值可能落在兩個分組之間）。這會導致二分查找需要額外的檢查步驟（如檢查后一個槽的最小值），或多次線性探測，降低了效率。

簡單來說，使用最大值允許二分查找直接通過 target <= slot_value 條件鎖定目標分組，而最小值會導致條件模糊，查詢路徑更長。

2、結合二分法的詳細示例

下面通過一個具體例子說明。假設一個 InnoDB 數據頁包含以下主鍵值（已排序）：1, 3, 5, 7, 9, 11, 13, 15。為簡化，假設每個分組包含2條記錄，頁目錄有4個槽：

分組：組1 (1, 3)、組2 (5, 7)、組3 (9, 11)、組4 (13, 15)。

現在，執行二分查找目標主鍵為10的記錄（10不存在，但查找過程相同）。

二分查找的偽代碼如下（以方案A和B分別演示）：

# 通用二分查找框架（查找可能的分組索引）

low = 0

high = num_slots - 1

while low <= high:

??? mid = (low + high) // 2

??? if target <= slots[mid].value:? # 比較目標值和槽值

??????? high = mid - 1? # 目標在左半部分（包括當前槽）

??? else:

??????? low = mid + 1?? # 目標在右半部分

# 結束時，low 是可能的目標分組索引

方案A：使用最大值的二分查找（高效）

• 槽值設置：槽0 = 3（組1最大主鍵）、槽1 = 7（組2最大主鍵）、槽2 = 11（組3最大主鍵）、槽3 = 15（組4最大主鍵）。
• 槽值數組：[3, 7, 11, 15]（槽索引：0,1,2,3）
• 查找目標：10
• 二分查找過程：
  • 初始：low = 0, high = 3
    • mid = (0 + 3) // 2 = 1, 槽值 = 7
    • 比較：10 <= 7？ False → 目標 > 7，所以目標在槽1之后，設置 low = mid + 1 = 2
  • 更新：low = 2, high = 3
    • mid = (2 + 3) // 2 = 2, 槽值 = 11
    • 比較：10 <= 11？ True → 目標可能位于槽2或更早分組，設置 high = mid - 1 = 1
  • 現在 low = 2, high = 1，low > high，循環結束。返回候選索引 low = 2（可能的目標分組）。
• 結果：槽2被選中（對應組3）。然后在組3內線性查找記錄（9和11），發現10不存在。
• 分析??：僅2次比較就鎖定了槽2（組3），因為最大值為11提供了明確的上界：10 <= 11表示目標一定在槽2之前的某個分組（或槽2本身），而前一步的 low 調整確保了高效收斂。整個查找過程直接，沒有歧義。

方案B：使用最小值的二分查找（低效）

• 槽值設置：槽0 = 1（組1最小主鍵）、槽1 = 5（組2最小主鍵）、槽2 = 9（組3最小主鍵）、槽3 = 13（組4最小主鍵）。
• 槽值數組：[1, 5, 9, 13]（槽索引：0,1,2,3）
• 查找目標：10
• 二分查找過程：
  • 初始：low = 0, high = 3
    • mid = (0 + 3) // 2 = 1, 槽值 = 5
    • 比較：10 <= 5？ False → 目標 > 5，但無法確定是否在槽1分組內（因為 min=5，目標可能位于槽1或后續分組），設置 low = mid + 1 = 2
  • 更新：low = 2, high = 3
    • mid = (2 + 3) // 2 = 2, 槽值 = 9
    • 比較：10 <= 9？ False → 目標 > 9，同樣無法確定，設置 low = mid + 1 = 3
  • 更新：low = 3, high = 3
    • mid = (3 + 3) // 2 = 3, 槽值 = 13
    • 比較：10 <= 13？ True → 目標可能位于槽3或更早分組，設置 high = mid - 1 = 2
  • 現在 low = 3, high = 2，low > high，循環結束。返回候選索引 low = 3（可能的目標分組）。
• 結果：槽3被選中（對應組4）。但組4的最小主鍵是13 > 10，所以目標不在該分組。需要額外檢查前一個槽（槽2，組3）或直接線性掃描組3，才能確定10在組3范圍內（但不存在）。
• ??分析??：使用了3次比較，但結束時 low=3 是錯誤的（組4最小主鍵13 > 10，目標不可能在組4）。二分查找后，必須額外檢查槽2的槽值（9），才能發現目標可能位于槽2分組（因為 9 <= 10 但 10 < 13）。整個路徑更長，存在歧義：當目標 > 槽值時，無法排除當前分組的可能性，導致 low 和 high 調整不精確。這會增加不必要的比較和分組訪問次數。

關鍵區別總結

• 決策清晰性??：使用最大值時，槽值（最大主鍵）定義了分組的明確上界。二分查找中，target <= slot_value 直接表示目標位于索引 <= mid 的某個分組，從而高效縮小搜索范圍。最小值則只能定義分組的起始點，沒有上界信息，導致決策模糊。
• ??效率??：最大值的二分查找平均只需 O(log N) 次比較（N是槽數），就能鎖定唯一可能的分組。最小值可能需要額外線性探測或回溯，增加開銷。
• ??插入與范圍查詢??：在插入新記錄時，使用最大值也更容易處理邊界情況（如記錄插入到分組末尾）。對于范圍查詢（如 key BETWEEN A AND B），最大值可以快速排除不相關的分組。
• ??單調性利用??：主鍵值單調遞增，使用最大值序列（如3,7,11,15）也單調遞增，恰好匹配二分查找要求。

設計背后的權衡

? InnoDB 選擇最大值是工程優化，犧牲少量內存（存儲最大值）換取查詢性能。分組大小（如默認每組6-8條記錄）也進行了權衡，確保二分查找快速收斂的同時，分組內線性查找成本低。實際實現中，InnoDB 的頁目錄還處理了記錄刪除、變長記錄等復雜情況，但最大值原則保持了二分查找的效率。

總之，槽記錄分組最大主鍵值而非最小值，是為了使二分查找在頁內定位記錄時更高效、直接，減少了歧義和額外操作，從而提升整體查詢性能。