理解進階資料結構（一）：B樹 ｜B+樹

樹是資料結構中很重要概念，不過當樹的枝葉越長越不平均，就像大樹歪向一側一樣，查找資料也會變得麻煩又費時。資料結構中的樹若失去平衡，查找效率會大大降低，甚至可能拖慢整個系統的速度。因此，我們需要設計能自我調整、保持平衡的樹，確保不管資料如何新增，都能快速查找。

以下內容為學習要點，但我建議學習樹看動畫會更容易理解。

此學習筆記若內容有誤，歡迎留言指正！

複習：二元搜尋樹 BST

我之前都記成BTS XD

一個節點只能存一個資料。左邊是最小，右邊最大。

一個節點存多筆資料效率高

如何存放資料？才能更有效率地找到資料？

如果數據量大到，葉子跟根的距離很遠，查找就會變得很沒效率。所以在資料結構裡，出現能夠讓一個節點同時存放多筆資料的設計，等於給我們的搜尋速度開了「加速模式」！尤其是當數據量龐大到無法一眼看完時，這些樹的特性就像是一條捷徑，讓我們更快找到答案。

M way search tree

每個節點最多可以有 M 位子節點(Children)，而每個節點可以放M-1個數值(key)。以下圖來說，這是 5 way search key。最多可以連五條線，即最多可以有個子節點。

https://faculty.cs.niu.edu/~freedman/340/340notes/340multi.htm

B 樹

• 特性：B 樹是一種多元樹（非二元），根節點最少有兩個子節點。每個節點可以存多個值，因而減少資料的偏斜。每個節點都是資料。
• 操作：插入或刪除時，節點會重新分配，且節點中的資料可能會“借”相鄰節點，來維持平衡。每次都會往上長。插入新資料，先拆分，再往上長
• 限制與規則：每個節點中的資料數量有上下限，通常為一個範圍值 m；節點裡的資料必須排序，讓搜尋和插入保持有序。刪除時，若節點內的資料少於最小值，會從相鄰節點「借資料」來保持平衡。
• 應用：資料庫索引，B 樹是搜尋大量資料（如交易匹配、資料庫檢索）的常見結構，因為每次操作會讓整個樹保持平衡。
• 參考動畫影片：Understanding B-Trees: The Data Structure Behind Modern Databases

B+ 樹：

跟 B 樹不一樣的是，他的資料僅存在最底層的 Leaf，其餘往上長的都是指標，指向最底層的實際資料值 ，而不用進行 Tree Travesal（遍歷）。

• 特性：擴充了 B 樹，除了根節點，每個節點都會有指標（leaf pointers），能直接找到下一個節點，無需重頭搜尋。最底層的葉節點是鏈結串列（Linked List）
• 操作：用指標定位到葉節點，大量資料的搜索效率更高。
• 應用：資料庫系統，如銀行交易，因為需要快速度查找和更新大量資料。

B 樹與 B+樹兩者比較表格

AVL, 紅黑樹會在下個章節補充。

補充資料：

10.2 B Trees and B+ Trees. How they are useful in Databases

B 樹、B+ 樹比較

B 樹影片