30-11 之資料庫層的核心 — 索引結構演化論 B+樹
統整
全文回答一個問題：
要如何儲放資料，才能更快速的找到資料？——這個技術就是索引。 在 MySQL 中由儲存引擎決定怎麼放；InnoDB 預設用 B+ 樹。為什麼是它？
作者用「演化」的寫法回答：每一代資料結構都是為了補上一代的缺陷而生。順序是 二分搜尋 → BST → 平衡 BST → B 樹 → B+ 樹。
第 0 代：線性搜尋 O(n)
資料庫誕生的本質就是為了找東西更快。比較對象是線性搜尋：1000 筆資料一筆一筆慢慢查，時間複雜度 O(n)。
要加快，就是把資料整理成固定的規律與特性，讓我們能依這個規律做更快的搜尋——這就是資料結構。
第 1 代：二分搜尋 Binary Search
- 前提條件：必須是排序好的資料
- 思路：把資料砍成兩半，判斷要的資料在左還右（因為有排序所以判斷得出來），再從那段重複一樣的事
那要用哪個資料結構來實現？ 作者說資料結構只是一種概念，關鍵在記憶體的連續性，由此導出兩個候選：
Array（✗） 兩個理由：
- 記憶體是連續區塊，需事先分配大小，大量新增刪除時很浪費資源
- 新增、刪除有時很快、有時很慢，而資料庫應該盡可能讓操作都是平均的
為什麼會忽快忽慢？一開始分 5 個位置，前 5 次新增都很快；第 6 次沒空間了，要：建立兩倍大的記憶體空間 → 把原陣列拷貝過去 → 才寫入第 6 筆。
List（✗）：記憶體是分散的，無法做二分搜尋——要走到 5，得先知道 3 的記憶體位置，因為只有那裡記著 5 在哪。
第 2 代：二元搜尋樹 BST
兩個候選各有優點：Array 可以二分搜尋、List 解決了 Array 的新增效率問題。兼具兩者的就是 BST。
- 特性：左子樹的值一定小於根節點，右子樹的值一定大於根節點
- 資料庫的三個基本操作，平均時間複雜度都是 log(n)：
- 搜尋 log(n)：只要往其中一邊走
- 新增 log(n)：要找到適當的插入位置
- 刪除 log(n)：要找到適當的移除位置
第 3 代：平衡二元搜尋樹 Balanced BST
BST 沒被選中的原因：最壞會退化成 O(n)——一條斜下去的鏈也是合法的 BST，查詢就變成一個一個慢慢找。
平衡 BST 的特點：
- 葉節點的高度差的絕對值不能超過 1
- 左右子樹都為平衡二元搜尋樹
- 最好／最壞／平均的新增、刪除、搜尋都是 O(log n)
- AVL 樹、紅黑樹都屬於平衡 BST，會自動進行平衡操作
那為什麼還是沒選它？
因為它是以記憶體來說操作最有效率，以硬碟來說則否。 資料庫的資料量通常很大，不可能全塞在記憶體，通常放在硬碟中。
硬碟上的瓶頸是 I/O：一棵很深的平衡 BST，要找的值在最下面，至少要進行 100 次 I/O 操作。
第 4 代：B 樹
誕生理由：解決高度太高所產生的問題（例如資料庫索引的 I/O 問題）。
一顆 m 階 B 樹的特點：
- 每個節點內最多有 m − 1 個內部節點
- 每個節點最多有 m 個子樹
- 每個內部節點都有儲放完整資料
- 每個節點內的內部節點都依順序排序
概念就是在一個節點內多塞些東西，以減少 I/O 讀取次數。
為什麼塞多一點就能減少 I/O？節點不是一樣多嗎？
關鍵在於：平衡 BST 的每一個節點都存在一個硬碟區塊中，而這個區塊大小是 4 KB。 讀取時以一個區塊為最小單位——不管節點資料是 2 byte 還是 1 KB，讀取次數都和 4 KB 的一樣。
所以 B 樹的想法是：盡可能把每個節點塞滿 4 KB，內部再用節點來區分，這樣一次 I/O 就能讀到多個節點。
B 樹仍然沒被 InnoDB 選中，三個問題：
- 查詢時不穩定：找 10 只要 1 次 I/O（根節點就中），找 1 要 3 次 I/O（走到最底）。最好是根節點就找到，最壞是最底下才找到
- 範圍搜尋沒效率：要找大於 2 的資料，所有節點都會走一次
- 節點太多 I/O 的問題：資料本身變大時，原本一個區塊能放兩個的，就放不下兩個了
第 5 代：B+ 樹（InnoDB 的選擇）
B+ 樹就是為了解決上面三個問題。一顆 m 階 B+ 樹和 B 樹相比的特點：
- 每個節點最多只能有 M 個子樹
- 每個節點中的內部節點最多只能有 M − 1 個
- 每個非葉子節點（非最底層）只儲放索引用
- 每個葉子節點（最底層）儲放了實際資料
- 每個葉子節點會包含一個指針，指向右邊的葉子節點
小重點：只有最下面的節點有資料，其它上面的節點只存索引。
搜尋流程：取 5 要 3 次 I/O，取 6 也是 3 次 I/O——所有節點搜尋的速度是平均的，不會有快有慢。範圍搜尋則是找到起點後一直往右抓就夠了。
與 B 樹的三點比較（對應三個問題）：
| 原因 | |
|---|---|
| B+ 樹層級更少 | 非葉子節點的 4 KB 空間全部只拿來存指針，代表有更多空間可存 |
| B+ 樹查詢更穩定 | 一定要走到葉子節點才能取得資料 |
| B+ 樹自帶排序 | 有一條鏈表依順序把葉子節點串起來 |
作者的結語
從 0 到 1 理解 InnoDB 為什麼選 B+ 樹，是學習資料庫核心索引的第一步；理解了這個，之後就知道為什麼索引要那樣用。
反覆出現的關鍵字
- I/O 次數 — 全文真正的主角。每一代的淘汰理由最後都收束到這個數字（平衡 BST「至少 100 次 I/O」、B 樹「1 次 vs 3 次」、B+「都是 3 次」）
- 4 KB 硬碟區塊 / 讀取以區塊為最小單位 — 作者用來解釋「為什麼塞滿節點有用」的唯一機制
- 記憶體 vs 硬碟 — 平衡 BST 被淘汰的分水嶺：在記憶體最有效率，在硬碟則否
- 樹的高度 / 層級 — 與 I/O 次數劃等號
- 穩定 / 平均 — 出現在兩個地方：Array 被否決（操作忽快忽慢）、B 樹被否決（查詢不穩定）。「平均」是作者替資料庫設下的隱含需求
- 範圍搜尋 — B+ 葉子鏈表存在的理由
- 葉子節點存資料、非葉子只存索引 — B+ 樹的定義句，作者特地標成「小重點」
- 演化 / 誕生原由 — 全文的敘事骨架：每一代都是為了補上一代的缺陷
矛盾點
文章內部
-
「log(n) 指數級」用詞錯誤。 在 BST 那節寫「這三個基本操作平均而言都有 log(n) 指數級的操作時間」——log 是對數級，與指數級（exponential）正好相反。（推論）作者應是想說「比 O(n) 快一個數量級」。
-
「內部節點」一詞被用來指兩種東西。 B 樹特點寫「每個節點內最多有 m − 1 個內部節點」「每個內部節點都有儲放完整資料」——前者指的是節點內的鍵（key），後者指的是樹中的非葉節點。同一個詞在相鄰兩行指不同層級的東西，是全文最容易讀錯的地方。
-
B 樹「每個內部節點都有儲放完整資料」與「盡可能塞滿 4 KB」互相拉扯。 既然每個節點都要存完整資料，那能塞進 4 KB 的鍵就變少——這正是作者自己在第三個問題（節點太多 I/O）講的事，但在介紹 B 樹優點時沒有先說明，讀起來像先誇再打臉。（推論）這兩段其實是同一件事的正反面：B 樹的鍵密度受制於它把資料也放在內部節點。
-
BST 的新增／刪除複雜度只給了「平均」。 寫「新增：平均 log(n)、刪除：平均 log(n)」，下一節才說最壞是 O(n)；但平衡 BST 那節又強調「最好、最壞、平均都是 O(log n)」。（推論）BST 那三行的「平均」是關鍵限定詞，作者沒有當場點明，要讀到下一節才會回頭發現。
-
「至少要進行 100 次 I/O」沒有交代 100 從哪來。 圖 7 的例子沒有給節點數或樹高，數字是憑空出現的。
與 vault 既有筆記
-
補上 B-tree 靠一個節點放多個鍵把樹壓矮，換到更少的讀取次數 缺的那一塊機制。 那篇（來源 ExplainThis）只說「一個節點放多個鍵 → 層數變少 → 讀取次數少」，並用「每節點最多 10 個鍵」當假設。本文給出為什麼層數等於 I/O 次數：每個節點存在一個 4 KB 硬碟區塊裡，讀取以區塊為最小單位。 → 「每節點幾個鍵」不是可以隨意假設的參數，是被 page size 決定的。
-
那篇筆記的標題講 B-tree，但 InnoDB 選的是 B+ 樹。 既有筆記從頭到尾談 B-tree 降低層數，本文明確說 B 樹有三個問題所以沒被選中（查詢不穩定、範圍搜尋沒效率、資料變大時塞不下）。 → 既有筆記不算錯（它講的是 B 系列相對 BST 的優勢），但停在了 B 樹，少了最後一跳。
-
和 叢集索引一張表只有一個，非叢集索引是另一份帶 pointer 的結構 互相印證。 本文的「葉子節點儲放實際資料」就是叢集索引的機制面；也和還在 Inbox 的 MySQL 與 PostgreSQL 怎麼選？ 裡「InnoDB：表就是索引，數據直接存在主鍵 B+ Tree 的葉子節點」完全對上。 （推論）但要小心跨資料庫套用：PostgreSQL 的 B+ 樹葉子存的是 CTID 指標不是資料行，所以「葉子存實際資料」是 InnoDB 的選擇，不是 B+ 樹的定義。
-
和 全表掃描和索引掃描的適用場景是相反的 接得起來。 本文開頭的「線性搜尋 O(n)、一筆一筆慢慢查」就是那篇講的 full table scan；本文回答的是那篇沒展開的下一題：索引掃描的那棵樹，為什麼長成這個形狀。