1.二叉排序樹
二叉排序樹是一個空樹赴涵，或者是具有如下性質(zhì)的二叉樹：
- 若它的左子樹不為空，則左子樹上的所有節(jié)點的值均小于它的根節(jié)點的值订讼；
- 若它的右子樹不為空髓窜，則右子樹上的所有節(jié)點的值均大于它的根節(jié)點的值；
- 左右子樹都是二叉排序樹欺殿。
二叉排序樹的數(shù)據(jù)操作效率：
1.查找效率最好為O(log n)寄纵、最壞為O(n);
2.插入效率和查找效率相同（先查找插入的位置，且只插入到葉子節(jié)點）脖苏；
3.刪除效率最好為O(log n) + O(1)（只有左或者右子樹）程拭，最壞為O(log n) + O(log n)（只有左右子樹同時存在）
2.平衡二叉樹
平衡二叉樹是空樹或者左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是平衡二叉樹棍潘。
平衡二叉樹犧牲了插入和刪除數(shù)據(jù)的代價恃鞋，但是提高了查詢效率（穩(wěn)定查詢效率為O(log n)）崖媚。
3.紅黑樹
紅黑樹是一種自平衡二叉排序樹，特征如下：
1.節(jié)點是紅色或者是黑色恤浪；
2.根節(jié)點是黑色畅哑；
3.所有葉子節(jié)點都是黑色（葉子節(jié)點的值都是NULL）；
4.每個紅色節(jié)點的兩個子節(jié)點都是黑色（即從根到葉子遍歷不能出現(xiàn)兩個連續(xù)的紅節(jié)點）水由；
5.從任意一個節(jié)點到每個葉子節(jié)點的所有簡單路徑都包含相同數(shù)據(jù)的黑色節(jié)點荠呐。
紅黑樹解決的問題，它可以在O(log n)時間復(fù)雜度內(nèi)實現(xiàn)查找砂客，插入和刪除泥张，任何不平衡都會在三次旋轉(zhuǎn)內(nèi)解決。
4.B樹（多路查找樹）
特征：
1.根節(jié)點至少有兩個子女節(jié)點鞭盟；
2.每個非根節(jié)點包含的關(guān)鍵字個數(shù)i滿足：n/2 - 1 < i < n -1;
3.除根節(jié)點以外的所有節(jié)點（不包括葉子節(jié)點）的度數(shù)正好是關(guān)鍵字的總數(shù)+1圾结，故內(nèi)部子樹個數(shù)k滿足：n/2 < k < n -1;
4.所有的葉子節(jié)點都位于同一層瑰剃。
5.B+樹
B+樹是一個n叉樹齿诉，每個節(jié)點通常都有多個孩子，一顆B+樹包含根節(jié)點晌姚、內(nèi)部節(jié)點和葉子節(jié)點粤剧。B+樹的特征如下：
1.有n個子樹的節(jié)點含有n個關(guān)鍵字；
2.所有葉子節(jié)點包含了全部關(guān)鍵字的信息挥唠，以及指向這些關(guān)鍵字記錄的指針抵恋，且葉子節(jié)點本身依賴關(guān)鍵字的大小，即自小而大順序連接宝磨；
3.所有的非終端節(jié)點可以看成索引的一部分弧关，節(jié)點中包含了其他子樹的最大或最小關(guān)鍵字。
B+樹有效內(nèi)容均保存在葉子節(jié)點唤锉，且B+樹有兩個指針世囊，一個指向根節(jié)點，一個指向關(guān)鍵字最小的元素的葉子節(jié)點窿祥，因此B+樹支持從根節(jié)點開始隨機查詢和從最小關(guān)鍵字順序查詢株憾。
B+樹相比B樹擁有更小的磁盤代價，讀寫代價更低（因為同樣的數(shù)據(jù)量晒衩，B+樹比B樹高度低嗤瞎，因為B+樹非葉子節(jié)點不保存數(shù)據(jù)），B+樹的查詢關(guān)鍵字的路徑相等听系，即從根節(jié)點到葉子節(jié)點的路徑贝奇，即每個數(shù)據(jù)的查詢效率相等且穩(wěn)定。
