Binary tree

在電腦科學中，二元樹（英語：Binary tree）是每個節點最多只有兩個分支（即不存在分支度大於2的節點）的樹結構。通常分支被稱作「左子樹」或「右子樹」。二元樹的分支具有左右次序，不能隨意顛倒。

二元樹

B TREE

B樹（英語：B-tree），是一種在計算機科學自平衡的樹，能夠保持數據有序。這種資料結構能夠讓查找數據、順序訪問、插入數據及刪除的動作，都在對數時間內完成。B樹，概括來說是一個一般化的二元搜尋樹（binary search tree）一個節點可以擁有2個以上的子節點。與自平衡二元搜尋樹不同，B樹適用於讀寫相對大的數據塊的存儲系統，例如磁碟。B樹減少定位記錄時所經歷的中間過程，從而加快存取速度。B樹這種資料結構可以用來描述外部存儲。這種資料結構常被應用在資料庫和文件系統的實現上。

B TREE

B+ TREE

B+ 樹是一種樹資料結構，通常用於資料庫和作業系統的檔案系統中。B+ 樹的特點是能夠保持資料穩定有序，其插入與修改擁有較穩定的對數時間複雜度。B+ 樹元素由下而上插入，這與二元樹恰好相反。

B+ 樹在節點存取時間遠遠超過節點內部存取時間的時候，比可作為替代的實現有著實在的優勢。這通常在多數節點在次級儲存比如硬碟中的時候出現。通過最大化在每個內部節點內的子節點的數目減少樹的高度，平衡操作不經常發生，而且效率增加了。這種價值得以確立通常需要每個節點在次級儲存中占據完整的磁碟塊或近似的大小。

B+ TREE

MySQL索引

1.使用Binary tree，以2做為根節點，要找到11，必須經過2、7、6、11，極端狀況下可能出現非常不平衡的樹，不適合當索引，那把它進化成平衡樹（AVL）如何?

2.AVL樹是透過旋轉達成平衡，能避免出現單鏈的最差狀況，但在數據量大時，資料無法全放在隨機存取記憶體，只能放在磁碟，影響了查詢的效率

3.B TREE中，插入、刪除節點後可進行分裂與合併，查找過程經過一個個節點，但在隨機存取記憶體與硬碟的交互中消耗性能。

4.MySQL選用B+ TREE的原因

1.樹高度降低，儲存節點增多
2.搜尋數據只需要遍歷子節點
3.優秀的排序效能
4.查詢效能穩定、查詢次數接近