TL;DR | 面試情境模擬 #
👴 面試官：為什麼databaseindex通常使用 B+ Tree，而不是 Hash 表或二元搜尋樹？
🧑💻 你：核心原因在於減少磁碟 I/O 次數。
- B+ Tree 是「矮胖」的：它能儲存大量資料，但高度很低（通常 3-4 層），查詢時只需要讀取幾次磁碟。
- 節點連續性：葉節點之間有指標相連，適合範圍查詢（Range Query）。
為什麼需要index？ #
想像一本沒有目錄的字典，要查一個字，你得從第一頁翻到最後一頁。
- database表：就像沒有目錄的字典（全表掃描，慢）。
- index：就像字典前面的目錄，告訴你字在哪一頁，直接跳過去找，效率極高。
為什麼選 B+ Tree？（白話理解與面試要點） #
1. Hash 表：像是「存包櫃」，找單點快但無法查範圍 #
給號碼牌（Key）就能一秒拿到包包。但如果你想找「編號 100 到 200 的所有包包」，系統會卡住。
- 結論：Hash 很適合找「精確值」，但不適合database常用的「範圍查詢」。
2. 二元搜尋樹 vs. B+ Tree：樹高與 I/O 效率 #
二元搜尋樹透過二分法一層層往下找，資料量越大，樹就會長得越高（越深）。在database中，每一層代表一次「硬碟讀取 (I/O)」。樹越高，讀取次數越多，速度就越慢。
B+ Tree 透過「高分支度」，讓節點變得很胖，樹就變得很矮。
[二元搜尋樹 - 瘦高] [B+ Tree - 矮胖]
( ) ( )
/ \ / | | \
( ) ( ) (...) (...) (...)
/ \
( ) ( )
- 結論：B+ Tree 保持「矮胖」狀態，確保讀取 3-4 次硬碟就能找到資料。
💡 深入理解結構 #
1. 結構圖解 #
B+ Tree 的資料都存在最底層的「葉節點」，上層只負責導航。
[ 根節點 ]
/ | \
[節點A] [節點B] [節點C]
/ | \ / | \ / | \
[葉1]<==>[葉2]<==>[葉3]<==>[葉4]<==>[葉5]<==>[葉6]
(1-50) (51-100) (101-150)(151-200)(201-250)(251+)
- 垂直找（導航路徑）：根節點就像是 GPS 指示牌，裡面存的不是資料，而是「通往下一層的路徑」。
- 水平找（節點連續性/雙向鍊結）：到了最底層（葉節點），如果資料還沒找完，直接順著
<===>箭頭往右邊的「車廂」找，不需要再繞回樹頂。
2. 為什麼可以這麼「矮胖」？ #
database把節點大小設計成跟硬碟的「分頁 (Page, 通常 16KB)」一樣大。因為 Page 很大，單個節點就能塞進成百上千個 Key。
這使得樹呈現指數級的容量成長：
- 1 層：可存 100 筆
- 2 層：可存 10,000 筆
- 3 層：可存 1,000,000 筆
- 4 層：可存 100,000,000 筆
這就是為什麼對於大多數系統，3-4 層的 B+ Tree 就足以支撐上億筆資料的查詢，效能非常穩定。
💡 進階補充：常見追問 #
Q1：叢集index (Clustered Index) 是什麼？ #
簡單說，就是把資料直接按照index順序存放在硬碟裡。
- 比喻：就像一本字典，內容本身就是按字母排序的。找到index（單字），就直接找到了資料（頁面內容），不需要再跑一趟去查主表。
- 關鍵優勢：資料物理位置是連續的，範圍查詢速度極快。
- 最佳實踐：主鍵通常設為「自增長整數 (Auto Increment Key)」。因為如果順序亂跳，database為了維持物理順序，需要頻繁搬動資料（頁分裂 Page Split），會嚴重拖慢寫入效能。