BST樹：二叉查找樹
B-樹，B+樹，B*樹都不是二叉查找樹。
參考資料：http://blog.csdn.net/dazhong159/article/details/7963846
https://wenku.baidu.com/view/548325b5e009581b6ad9eb21.html?from=search
http://blog.csdn.net/hijiankang/article/details/9166451
一、B-樹（B樹）
性質：是一種多路搜尋樹（并不是二叉的）
1 定義任意非葉子結點最多隻有M個兒子（且M>2），M是B-樹的階數；
2 根結點的兒子數為[2, M]；
3 除根結點以外的非葉子結點的兒子數為[M/2, M]；
4 每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字）
5 非葉子結點的關鍵字個數=指向兒子的指針個數-1；（3 4 5應該配合着一起看）
6 非葉子結點的關鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7 非葉子結點的指針：P[1], P[2], …, P[M]；其中P[1]指向關鍵字小于K[1]的子樹，P[M]指向關鍵字大于K[M-1]的子樹，其它P[i]指向關鍵字屬于(K[i-1], K[i])的子樹（注意，是開區間）；
8 所有葉子結點位于同一層；
搜尋：從根結點開始，對結點内的關鍵字（有序）序列進行二分查找，如果命中則結束，否則進入查詢關鍵字所屬範圍的兒子結點；重複，直到所對應的兒子指針為空，或已經是葉子結點；
1 關鍵字集合分布在整顆樹中；
2 任何一個關鍵字出現且隻出現在一個結點中；
3 搜尋有可能在非葉子結點結束；
4 其搜尋性能等價于在關鍵字全集内做一次二分查找；
5 自動層次控制；
6 由于限制了除根結點以外的非葉子結點，至少含有M/2個兒子，確定了結點的至少使用率，其最底搜尋性能為lgN；
7 B-樹的性能總是等價于二分查找（與M值無關），沒有B樹平衡的問題；
插入：由于M/2的限制，在插入結點時，如果結點已滿，需要将結點分裂為兩個各占M/2的結點；删除結點時，需将兩個不足M/2的兄弟結點合并；
應用：檔案系統
最簡單的B-樹是2-3樹
二、B+樹
性質： B+樹是B-樹的變體，也是一種多路搜尋樹：
1 其定義基本與B-樹同，除了：
2 非葉子結點的子樹指針與關鍵字個數相同，範圍區間為[M/2, M]；
3 非葉子結點的子樹指針P[i]，指向關鍵字值屬于[K[i], K[i+1])的子樹（B-樹是開區間，這裡是半開區間）；
4 為所有葉子結點增加一個鍊指針；
5 所有關鍵字都出現在葉子結點的連結清單中（稠密索引），且連結清單中的關鍵字恰好是有序的；
6 非葉子結點相當于是葉子結點的索引（稀疏索引），葉子結點相當于是存儲（關鍵字）資料的資料層；
搜尋： B+的搜尋與B-樹也基本相同，差別是B+樹隻有達到葉子結點才命中（B-樹可以在非葉子結點命中），其性能也等價于在關鍵字全集做一次二分查找；
插入：當一個結點滿時，配置設定一個新的結點，并将原結點中1/2的資料複制到新結點，最後在父結點中增加新結點的指針；B+樹的分裂隻影響原結點和父結點，而不會影響兄弟結點，是以它不需要指向兄弟的指針；
應用：檔案系統
三、B*樹
性質：
1 是B+樹的變體，在B+樹的非根和非葉子結點再增加指向兄弟的指針；
2 非葉子結點的子樹指針與關鍵字個數相同，範圍區間為[2*M/3, M]；
插入：當一個結點滿時，如果它的下一個兄弟結點未滿，那麼将一部分資料移到兄弟結點中，再在原結點插入關鍵字，最後修改父結點中兄弟結點的關鍵字（因為兄弟結點的關鍵字範圍改變了）；如果兄弟也滿了，則在原結點與兄弟結點之間增加新結點，并各複制1/3的資料到新結點，最後在父結點增加新結點的指針；
B*樹配置設定新結點的機率比B+樹要低，空間使用率更高。
小結
B-樹：多路搜尋樹，每個結點存儲M/2到M個關鍵字，非葉子結點存儲指向關鍵字範圍的子結點；所有關鍵字在整顆樹中出現，且隻出現一次，非葉子結點可以命中；
B+樹：在B-樹基礎上，為葉子結點增加連結清單指針，所有關鍵字都在葉子結點中出現，非葉子結點作為葉子結點的索引；B+樹總是到葉子結點才命中；
B*樹：在B+樹基礎上，為非葉子結點也增加連結清單指針，将結點的最低使用率從1/2提高到2/3。