Learning Objectives
- 說明磁碟一次讀一整塊，所以搜尋樹要「矮胖」：每個節點放很多鍵、分很多路
- 說出最小度數 t 的 B 樹裡，每個節點的鍵數範圍與子節點數，以及所有葉節點都在同一層
- 追蹤 B 樹的搜尋，數出讀了幾個節點
- 追蹤插入時節點分裂、中間鍵上升，說明樹為什麼只會從根長高
- 說明 B+ 樹把資料全部放在葉節點、葉節點串成串列，範圍查詢不必回到上層
- 說明資料庫索引（例如 MySQL InnoDB）為什麼採用這一類樹
資料放在磁碟上時，二元搜尋樹太高了
前幾課的二元搜尋樹、AVL 樹、紅黑樹都假設資料在記憶體裡：走到下一個節點，只是跟著指標跳一下。 資料庫、檔案系統的資料多到放不進記憶體，必須放在磁碟（硬碟或 SSD）上，情況就不一樣了：
- 從磁碟讀資料比從記憶體讀慢上許多倍
- 磁碟不是一個位元組一個位元組讀，而是一次讀一整塊（叫做頁 page 或區塊 block），例如 MySQL 的 InnoDB 預設一頁 16 KB
- 讀一整塊和只讀其中幾個位元組，花的時間幾乎一樣
所以在磁碟上搜尋，成本主要看讀了幾個節點（幾次磁碟讀取），而不是比較了幾次。 一千萬筆資料放進平衡的二元搜尋樹，高度大約 24，找一筆就要讀 24 次磁碟。
解法是把樹做得矮胖：既然一次就讀進一整塊，乾脆在一個節點裡放幾百個鍵，分出幾百條路。下面的程式算一算，每個節點分的路越多，樹會矮多少。
分的路越多，樹越矮
cap 是「這麼多層的樹，最下面一層最多能分出幾條路」，每多一層就乘以 m。一千萬筆資料，二元樹要 24 層；每個節點分 1000 路，3 層就夠了。
B 樹的規則
B 樹（B-tree）由 Rudolf Bayer 與 Edward McCreight 在波音公司的研究實驗室提出，1970 年發表研究報告，1972 年刊登在期刊 Acta Informatica，就是為了存放在磁碟上的大型索引設計的。 它是一種多路搜尋樹：一個節點放多個排好序的鍵，鍵之間把範圍切開，每一段對應一個子節點。
本課採用最小度數 t（minimum degree，許多教科書的寫法）來描述，t ≥ 2：
| 規則 | 內容 |
|---|---|
| 鍵數 | 根有 1～2t - 1 個鍵；其他節點有 t - 1～2t - 1 個鍵 |
| 子節點數 | 有 m 個鍵的內部節點，剛好有 m + 1 個子節點 |
| 順序 | 節點裡的鍵由小到大；第 i 個子節點裡的鍵都介於第 i - 1 個和第 i 個鍵之間 |
| 平衡 | 所有葉節點都在同一層 |
t = 2 時每個節點有 1～3 個鍵、2～4 個子節點，就是第 12 課的 2-3-4 樹。實際的資料庫 t 是幾百，由「一頁放得下幾個鍵」決定。
「至少 t - 1 個鍵」保證每個節點至少半滿，樹不會變得稀疏：n 個鍵的 B 樹，高度大約是 log_t n，t 越大越矮。 另外也有教科書用「階」（order）m 描述 B 樹，也就是每個節點最多 m 個子節點，規則相同、只是換一種說法。
搜尋和二元搜尋樹一樣由根往下：在節點裡找到第一個 ≥ k 的鍵；相等就找到了，否則走它左邊那個子節點。 在節點裡找鍵是在記憶體裡做的（可以用二分搜尋），很快；真正花時間的是往下讀一個節點。
搜尋：數一數讀了幾個節點
這棵 B 樹有 3 層、8 個節點。找 45 讀 2 個節點；找 25 讀 3 個；找 33 一路讀到葉節點都沒有，也是 3 個。不管找什麼，讀取次數都不會超過樹高。
想一想：B 樹的形狀
最小度數 t = 3 的 B 樹，一個不是根的節點可以有幾個鍵？
為什麼存在磁碟上的索引要用 B 樹，而不用 AVL 樹這類二元平衡樹？
在上面那棵 3 層的 B 樹裡找 12，會讀幾個節點？
插入：節點滿了就分裂，中間鍵上升
新的鍵一律放進葉節點。葉節點還有空位就直接按順序放進去；問題是葉節點已經有 2t - 1 個鍵（滿了）的時候。
分裂（split）：一個滿的節點有 2t - 1 個鍵，拿正中間那一個（第 t - 1 個）當中間鍵：
- 中間鍵往上放進父節點
- 左邊 t - 1 個鍵留在原本的節點，右邊 t - 1 個鍵搬到一個新節點
- 原本的節點不是葉節點時，子節點也一分為二：左邊 t 個留著，右邊 t 個跟著搬
中間鍵上升後，父節點多了一個鍵、多了一個子節點。如果父節點也滿了怎麼辦？本課用教科書常見的預先分裂寫法： 從根往下找插入位置的路上，只要遇到滿的子節點，就先把它分裂再走下去。這樣一來，每次分裂時父節點一定還有空位，不需要再回頭往上處理。
根滿了時，先長出一個新的空節點當作新的根，舊的根變成它的子節點，再分裂舊的根：中間鍵成為新根唯一的鍵。 這是 B 樹唯一會長高的方式：樹從上面長高，所有葉節點同時往下一層，所以葉節點永遠在同一層，不需要像 AVL 樹那樣旋轉。
依序插入 10～90：分裂與長高
插入 40 時根 [10 | 20 | 30] 已經滿了：長出新的根，20 上升，樹高變成 2。插入 60、80 時，右下的葉節點在往下走的路上被分裂。插入 90 時根 [20 | 40 | 60] 又滿了，40 上升，樹高變成 3。
刪除：借一個鍵，或合併兩個節點
刪除比插入麻煩，這裡只說明想法，不寫程式。插入的危險是節點太滿（超過 2t - 1 個鍵），刪除的危險相反：節點太空（少於 t - 1 個鍵）。
- 要刪的鍵在葉節點：直接拿掉
- 要刪的鍵在內部節點：和二元搜尋樹一樣，用它的前驅（左子樹最大的鍵）或後繼（右子樹最小的鍵）頂替，問題就變成刪除葉節點裡的那個鍵
- 拿掉之後節點只剩 t - 2 個鍵（太少）時： - 借：相鄰的兄弟節點鍵比 t - 1 多，就透過父節點「轉」一個過來：父節點的分隔鍵下來，兄弟的一個鍵上去 - 合併：兄弟也只有 t - 1 個鍵，就把這個節點、父節點的分隔鍵、兄弟三者合併成一個節點（t - 2 + 1 + t - 1 = 2t - 2 個鍵，不會超過上限）
合併會讓父節點少一個鍵，父節點也可能因此太少，要繼續往上處理。如果根的最後一個鍵被合併下去，根變成空的，就把它拿掉，由唯一的子節點當新的根： B 樹只會從根變矮，和插入時只會從根長高對稱。和插入一樣，教科書也有「往下走的路上先確保子節點至少有 t 個鍵」的寫法，避免回頭往上處理。
B+ 樹：資料只放在葉節點
資料庫實際上更常用 B 樹的變形 B+ 樹（B+ tree），差別有兩個：
- 資料全部放在葉節點。內部節點的鍵只是「路標」（從葉節點複製上去的分隔值），不帶資料
- 葉節點由左到右串成一條鏈結串列，每個葉節點都有指向右邊下一個葉節點的指標
| B 樹 | B+ 樹 | |
|---|---|---|
| 資料放在哪裡 | 每個節點都可能有 | 只在葉節點 |
| 內部節點的鍵 | 真正的資料 | 路標（葉節點裡也有一份） |
| 找一筆資料 | 有可能在上層就找到 | 一律走到葉節點，每次讀取次數相同 |
| 範圍查詢（例如 12～33） | 要在樹裡上上下下走訪 | 找到起點的葉節點後，沿著串列往右讀 |
| 一個內部節點放幾個鍵 | 鍵帶著資料，放得少 | 只放路標，放得多，樹更矮 |
WHERE age BETWEEN 20 AND 30、ORDER BY 這類查詢在資料庫裡非常常見，B+ 樹只要找到第一筆，接下來就是順著葉節點讀下去。
下面的範例是一棵兩層的 B+ 樹：根只放路標 15、25、35，鍵 ≥ 路標就往右邊的子節點走；四個葉節點存放真正的資料，並且用 next 串起來。
B+ 樹的範圍查詢：找到起點再往右讀
查 12～33：從根判斷 12 落在第 0 個葉節點，接著只沿著下方的串列往右讀，讀到 [35 | 40] 第一個鍵就超過 33，停下。總共讀了 4 個節點，不需要再回到根。
資料庫索引：MySQL InnoDB
以 MySQL 的 InnoDB 儲存引擎為例（以下依 MySQL 參考手冊）：
- 除了空間索引（用 R 樹）之外，InnoDB 的索引都是 B 樹結構，一個節點就是一頁，預設 16 KB
- 每張表都有一個叢集索引（clustered index），存放整列資料；表有主鍵（PRIMARY KEY）時，叢集索引就是依主鍵建的
- 索引的資料列存在葉節點的頁裡，上層的頁只存指向下一層的指標；同一層的頁彼此用前後指標串成雙向串列
- 次要索引（secondary index，例如對 email 欄位建的索引）的每一筆紀錄，除了索引欄位，還存著那一列的主鍵值：用次要索引找到主鍵後，再到叢集索引找整列資料
MySQL 手冊把它叫做 B-tree，並說明這個詞指的是一整類索引設計，實際的結構是加了許多改良的變形。 從「資料在葉節點、上層只放指標、同一層串起來」這幾點看，它的形狀就是本課的 B+ 樹，所以一般的資料庫教材也稱它為 B+ 樹索引。
這也解釋了幾個寫 SQL 時的經驗：主鍵查詢只要讀幾頁；範圍查詢與 ORDER BY 主鍵很快；
用遞增的主鍵插入資料，新的列總是放在最右邊的葉節點，比隨機的主鍵（例如亂數產生的 UUID）少很多分裂。
想一想：分裂與 B+ 樹
t = 2 的 B 樹裡，一個葉節點是 [10 | 20 | 30]，它的父節點是 [40]。插入 25 時（預先分裂的寫法），會發生什麼事？
B 樹的所有葉節點為什麼一定在同一層？
資料表依主鍵建了 B+ 樹索引。執行 SELECT * FROM t WHERE id BETWEEN 100 AND 200，最合理的做法是？
實作：分裂一個滿的子節點
插入（含預先分裂）與一層一層印出樹的程式都寫好了，只缺 split_child。完成後依序插入 5、1、9、3、7、2、8、6、4、10，印出的樹應該有 3 層。預期輸出在右邊；可以切換成你熟悉的語言。
重點整理
- 磁碟一次讀一整塊，成本看讀了幾個節點；B 樹一個節點放很多鍵，樹很矮，高度約 log_t n
- 最小度數 t：根有 1～2t - 1 個鍵，其他節點 t - 1～2t - 1 個；m 個鍵的內部節點有 m + 1 個子節點；所有葉節點在同一層
- 插入放在葉節點；節點滿了就分裂，中間鍵上升到父節點；預先分裂的寫法在往下走的路上先處理滿的子節點
- B 樹只會從根長高（根分裂），刪除時只會從根變矮；刪除靠向兄弟借鍵或與兄弟合併
- B+ 樹把資料全部放在葉節點、葉節點串成串列，範圍查詢找到起點後往右讀即可；MySQL InnoDB 的索引就是這種形狀，一頁一個節點
下一課：堆積的建立與堆積排序。從磁碟回到記憶體，看另一種「用陣列存的樹」怎麼一次建好。