MySQL 內核級二分查找實現詳解：PAGE_CUR_G/GE/L/LE 四種搜尋模式與邊界處理

為何資料庫內核極度依賴二分查找

99% 以上 SQL（索引範圍掃描、等值查詢、唯一查詢）都在 B+ 樹頁面內透過二分查找定位記錄。

四大搜尋模式對應 SQL 語義

五大易錯點與內核級對策

1. 參數有效性檢查

頁面可能無用戶記錄（全刪除未合併），low=high=0 直接計算 mid 會越界。內核先判斷 PAGE_GET_N_RECS(page) == 0 直接返回。

2. 中值計算溢出防護

• 寫法一：mid = (low + high) / 2 — 極端情況溢出
• 寫法二：mid = low + (high - low) / 2 — 安全，推薦
• InnoDB 頁面 ≤ 16KB，記錄數有限，實際用寫法一也安全，但嚴謹代碼仍用寫法二

3. 遞迴 vs 迴圈

遞迴有壓棧/出棧開銷，內核全用 while (low <= high) 迴圈。InnoDB、PostgreSQL 均無遞迴實現。

4. 等值區間首/尾定位優化

naïve 做法：二分定位任一等值 → 線性掃描首/尾。若頁面 400 筆同值，需 200 次比較。
內核做法：比較函數內部根據 mode 修正返回值，使等值仍走二分分支，log2(400) ≈ 9 次搞定。

5. 通用比較修正邏輯

InnoDB 依 mode 決定等值時移動 low 或 high：

• G / LE：等值視為「小於」→ low = mid + 1
• GE / L：等值視為「大於」→ high = mid - 1

TNT 引擎採用查表法，含 includeKey、forward 兩維度：

操作符  includeKey  forward  |  cmp=1   0   -1
>=         1          1      |   1    -1   -1
>          0          1      |   1     1   -1
=          1          1      |   1    -1   -1
<          0          0      |   1    -1   -1
<=         1          0      |   1     1   -1