樹是資料結構中很重要概念，不過當樹的枝葉越長越不平均，就像大樹歪向一側一樣，查找資料也會變得麻煩又費時。資料結構中的樹若失去平衡，查找效率會大大降低，甚至可能拖慢整個系統的速度。因此，我們需要設計能自我調整、保持平衡的樹，確保不管資料如何新增，都能快速查找。
以下內容為學習要點，但我建議學習樹看動畫會更容易理解。此學習筆記若內容有誤，歡迎留言指正！複習：二元搜尋樹 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）
- 操作：用指標定位到葉節點，大量資料的搜索效率更高。
- 應用：資料庫系統，如銀行交易，因為需要快速度查找和更新大量資料。
圖片來源：geeksforgeeks
B 樹與 B+樹兩者比較表格
AVL, 紅黑樹會在下個章節補充。