MySQL 索引底層數據結構與算法原理（上）：B+Tree 為何成為首選
索引的本質
MySQL 官方定義：索引是幫助 MySQL 高效獲取數據的數據結構。
核心：索引 = 數據結構。
數據庫通過維護滿足特定查找算法的額外數據結構（索引），引用（指向）實際數據，實現高級查找算法（如二分查找、B-Tree 查找）。
從二叉查找樹到 B-Tree
二叉查找樹查找復雜度 O(log2n)，但數據庫幾乎不用，原因見下文磁盤存取原理分析。
B-Tree 定義
- 度
d > 1，高度 h
- 非葉節點：
n-1 個 key，n 個指針，d ≤ n ≤ 2d
- 葉節點：1~
2d-1 個 key，指針為 null
- 所有葉節點深度相同 =
h
- Key 非遞減排列，指針與 Key 間隔分布
B+Tree 改進
- 節點指針上限
2d（而非 2d+1）
- 內節點不存數據，僅存 Key；葉節點不存指針，存完整數據記錄
- 葉節點通過鏈表指針串聯，支持高效範圍掃描
帶順序訪問指針的 B+Tree
葉節點增加相鄰葉節點指針，範圍查詢（如 key 18~49）只需定位到 18，然後順鏈表遍歷，極大提升區間查詢效率。
為什麼選 B-Tree/B+Tree？磁盤存取原理視角
主存 vs 磁盤
- 主存（RAM）：隨機訪問，時間與次數線性相關，無「距離」概念。
- 磁盤：機械運動（尋道 + 旋轉），I/O 消耗比主存高數量級。
局部性原理與預讀
數據被訪問時，鄰近數據大概率即將被訪問。磁盤順序讀取極快（無尋道、少旋轉），因此預讀一頁（通常 4KB）載入內存，觸發缺頁中斷後程序繼續運行。
B-Tree 節點大小 = 一頁
數據庫設計將節點大小設置為一頁，每個節點一次 I/O 即可完全載入。新建節點直接申請一頁空間，利用頁對齊特性保證物理連續。
性能分析
- B-Tree 查找最多
h-1 次 I/O（根節點常駐內存），復雜度 O(h) = O(logd N)。
- 出度
d 通常 > 100，樹高 h 一般 ≤ 3。
- 紅黑樹高度大得多，邏輯鄰近物理可能遠離，無法利用局部性，I/O 復雜度同級但常數項大得多。
B+Tree 更優
內節點無 data 域，dmax = floor(pagesize / (keysize + pointsize)) 更大，出度更大，樹高更矮，性能更強。
MySQL 存儲引擎索引實現差異
MyISAM：非聚集索引
- 索引文件與數據文件分離。
- B+Tree 葉節點
data 域存數據記錄地址。
- 主索引要求 Key 唯一，輔助索引 Key 可重複，結構無差異。
- 檢索：搜索索引 → 取地址 → 讀取數據文件。
InnoDB：聚集索引
- 數據文件本身就是主索引（B+Tree），葉節點存完整數據記錄。
- 主鍵即索引 Key，表必須有主鍵（無則自動生成 6 字節隱藏列）。
- 輔助索引
data 域存主鍵值而非地址。
- 輔助索引查找需回表：搜輔助索引得主鍵 → 回主索引取數據（兩次 B+Tree 查找）。
實戰優化啟示
- 不建議過長字段做主鍵：所有輔助索引引用主鍵，主鍵過大導致輔助索引膨脹。
- 避免非單調主鍵（UUID、隨機串）：導致 B+Tree 頻繁分裂調整，插入性能極差。自增整數主鍵是最佳選擇。
下篇將深入討論高性能索引使用策略（覆蓋索引、最左前綴、索引下推等）。
