1. 樹結(jié)構(gòu)示意圖
補充：
- 兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點醒串。
- 樹的深度：從根節(jié)點開始（其深度為0）自頂向下逐層累加的执桌。上圖中，3的深度是1芜赌，6的深度是2仰挣，10的深度是3。
- 節(jié)點高度：從葉子節(jié)點開始（其高度為0）自底向上逐層累加的缠沈。6的高度是1膘壶，根節(jié)點1的高度是3错蝴。
2. 二叉樹（Binary Tree）
- 任何一個節(jié)點的子節(jié)點數(shù)量不超過2（子節(jié)點分為左節(jié)點與右節(jié)點）。
2.1 滿二叉樹（Full Binary Tree）
- 所有葉子結(jié)點都在最后一層颓芭。
- 節(jié)點的總數(shù)為2^n-1 （n為樹的高度）顷锰。
2.2 完全二叉樹（Complete Binary Tree）
- 所有葉子結(jié)點都在最后一層或倒數(shù)第二層。
- 最后一層的葉子結(jié)點在左邊連續(xù)亡问，倒數(shù)第二節(jié)的葉子結(jié)點在右側(cè)連續(xù)官紫。
2.3 平衡二叉樹（Balanced Binary Tree）
- 也叫 AVL 樹。
- 它是一顆空樹或左右兩個子樹的高度差的絕對值不超過1州藕。
- 左右兩個子樹均為平衡二叉樹万矾。
2.4 二叉搜索樹（Binary Search Tree）
- 也叫二叉查找樹、二叉排序樹慎框。
- 若子樹不空，則子樹上所有節(jié)點的值均小于或等于根節(jié)點的值后添。
- 若右子樹不空笨枯，則右子樹所有節(jié)點的值均大于或等于根節(jié)點的值。
- 左遇西、右子樹也分別為二叉排序樹馅精，或是一顆空樹。
2.5 紅黑樹（Red Black Tree）
- 每個節(jié)點都帶有顏色屬性（顏色為紅或黑）的平衡二叉查找樹粱檀。
- 節(jié)點是紅色或黑色洲敢。
- 根節(jié)點是黑色。
- 所有葉子結(jié)點都是黑色茄蚯。
- 每個紅色節(jié)點必須有兩個黑色的子節(jié)點（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點）压彭。
- 從任一節(jié)點到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點。
3. B 樹
B-tree（多路搜索樹渗常，并不是二叉的）是一種常見的數(shù)據(jù)結(jié)構(gòu)壮不。使用B-tree結(jié)構(gòu)可以顯著減少定位記錄時所經(jīng)歷的中間過程，從而加快存取速度皱碘。按照翻譯询一，B 通常認為是Balance的簡稱。這個數(shù)據(jù)結(jié)構(gòu)一般用于數(shù)據(jù)庫的索引癌椿，綜合效率較高健蕊。
3.1 B- 樹
B-樹 就是指 B樹，也是一種用于查找的平衡樹踢俄，但是它不是二叉樹缩功，B樹可以擁有多于2個子節(jié)點，能夠用來存儲排序后的數(shù)據(jù)都办。這種數(shù)據(jù)結(jié)構(gòu)能夠讓查找數(shù)據(jù)掂之、循序存取抗俄、插入數(shù)據(jù)及刪除的動作，都在對數(shù)時間內(nèi)完成世舰。這種數(shù)據(jù)結(jié)構(gòu)常被應(yīng)用在數(shù)據(jù)庫和文件系統(tǒng)的實作上动雹。
定義任意非葉子結(jié)點最多只有M個兒子；且M>2跟压。
根結(jié)點的兒子數(shù)為[2, M]胰蝠。
除根結(jié)點以外的非葉子結(jié)點的兒子數(shù)為[M/2, M]。
每個結(jié)點存放至少M/2-1（取上整）和至多M-1個關(guān)鍵字震蒋；（至少2個關(guān)鍵字）茸塞。
非葉子結(jié)點的關(guān)鍵字個數(shù)=指向兒子的指針個數(shù)-1。
非葉子結(jié)點的關(guān)鍵字：K[1], K[2], …, K[M-1]查剖；且K[i] < K[i+1]钾虐。
非葉子結(jié)點的指針：P[1], P[2], …, P[M]；其中P[1]指向關(guān)鍵字小于K[1]的子樹笋庄，P[M]指向關(guān)鍵字大于K[M-1]的子樹效扫，其它P[i]指向關(guān)鍵字屬于(K[i-1], K[i])的子樹。
所有葉子結(jié)點位于同一層直砂。
3.2 B+ 樹
B+樹 是 B樹 的變體菌仁，也是一種多路搜索樹
其定義基本與B-樹相同，除了：
非葉子結(jié)點的子樹指針與關(guān)鍵字個數(shù)相同静暂。
非葉子結(jié)點的子樹指針P[i]济丘，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹（B-樹是開區(qū)間）。
為所有葉子結(jié)點增加一個鏈指針洽蛀。
所有關(guān)鍵字都在葉子結(jié)點出現(xiàn)摹迷。
特性：
所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點的鏈表中（稠密索引），且鏈表中的關(guān)鍵字恰好是有序的郊供。
不可能在非葉子結(jié)點命中泪掀。
非葉子結(jié)點相當于是葉子結(jié)點的索引（稀疏索引），葉子結(jié)點相當于是存儲（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層颂碘。
B+樹的分裂：當一個結(jié)點滿時异赫，分配一個新的結(jié)點，并將原結(jié)點中1/2的數(shù)據(jù)復(fù)制到新結(jié)點头岔，最后在父結(jié)點中增加新結(jié)點的指針塔拳；B+樹的分裂只影響原結(jié)點和父結(jié)點，而不會影響兄弟結(jié)點峡竣，所以它不需要指向兄弟的指針靠抑。
更適合文件索引系統(tǒng)。
3.3 B* 樹
是 B+樹 的變體适掰，在 B+樹 的非根和非葉子結(jié)點再增加指向兄弟的指針
特性：
B*樹定義了非葉子結(jié)點關(guān)鍵字個數(shù)至少為(2/3)M颂碧，即塊的最低使用率為2/3（代替B+樹的1/2）荠列。
B*樹的分裂：當一個結(jié)點滿時，如果它的下一個兄弟結(jié)點未滿载城，那么將一部分數(shù)據(jù)移到兄弟結(jié)點中肌似，再在原結(jié)點插入關(guān)鍵字，最后修改父結(jié)點中兄弟結(jié)點的關(guān)鍵字（因為兄弟結(jié)點的關(guān)鍵字范圍改變了）诉瓦；如果兄弟也滿了川队，則在原結(jié)點與兄弟結(jié)點之間增加新結(jié)點，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點睬澡，最后在父結(jié)點增加新結(jié)點的指針固额。
所以，B*樹分配新結(jié)點的概率比B+樹要低煞聪，空間使用率更高斗躏。
本篇到此完結(jié)，如有補充內(nèi)容隨時更新昔脯！歡迎關(guān)注本人繼續(xù)跟進技術(shù)干貨的更新啄糙！
推薦一款超好玩的微信小程序，無數(shù)俊男靚女為之瘋狂栅干！（真的好玩！×3）
