二叉排序樹或平衡二叉樹（AVL樹、紅黑樹）
查找-之二叉排序樹（查找、插入、删除）
查找-之平衡二叉樹AVL和紅黑樹
結點隻有兩個孩子，且結點隻能存儲一個元素
問題：
一個結點隻存儲1個元素，在元素很多時，使得樹的深度或高度很大
出現的問題是：記憶體存取外存的次數非常多-使得時間效率降低
解決方法：
2-3樹
結構：
1970年 約翰·霍普克洛夫發明的多路查找樹，它一個結點具有2孩子（2結點）或3孩子（3結點）
2結點：一個元素+2個孩子（或沒有孩子）
3結點：一大一小2元素+3個孩子（或沒有孩子），3個孩子的排列順序是小、中、大
2-3樹結構圖
2-3-4樹
結點具有2孩子（2結點）或3孩子（3結點）或4個孩子（4結點）
結構：
2結點：一個元素+2個孩子（或沒有孩子）
3結點：一大一小2元素+3個孩子（或沒有孩子），3個孩子的排列順序是小、中、大
4結點：小中大3元素+4個孩子（或沒有孩子）， 4個孩子的排列順序是小、中、大
B樹
Blance-Tree
一種平衡多路查找樹，其中的2-3樹和2-3-4樹是B樹的特例，結點最大的孩子數目稱為B樹的階，
B樹的孩子數目有可以有多個
其中：
2-3樹最多有3個孩子--3階B樹
2-3-4樹最多有4個孩子--4階B樹
B樹是如何做到減少記憶體和外存資料交換的次數？
在處理的硬碟資料量很大，一次無法全部裝入記憶體--調整B樹的階數和硬碟存儲的頁面大小比對，讓樹的根結點持久儲存在記憶體中；例如：B樹的階為1001，則一個結點包含1000個關鍵字，高度為2，可以存儲10億個關鍵字，那麼在這棵樹上尋找關鍵字至多需要兩次硬碟的讀取。
B樹減少定位記錄時所經曆的中間過程，進而加快存取速度
适用于：内外存資料的互動、 讀寫相對大的資料塊的存儲系統、檔案系統的查找、資料庫索引
時間複雜度：O（logn）
缺點是：B樹需要中序周遊結點，且最壞的情況是在葉子結點找到
B+樹
在出現分支結點中的元素會被當做該分支結點位置的中序後繼者（葉子結點）再次列出
B+樹的存儲結構
和B樹的差別：
1）有n棵子樹的結點中包含n個關鍵字
2）所有葉子結點包含全部的關鍵字資訊（所有的資料都在葉子結點），指向含這些關鍵字記錄的指針；其中的葉子結點本身依據關鍵字大小順序連接配接
3）所有的分支結點可看出索引，結點中僅含有子樹中最大或最小的關鍵字
2）點的詳細解析：
所有的資料都在葉子結點，非葉子結點中存放元素（用于索引）不存放資料，是以每一層可容納更多的元素，磁盤的IO操作次數相比B樹少；
B+樹的所有葉子結點使用連結清單連接配接，便于區間查找和周遊。
适用于：檔案系統的查找、資料庫索引