B 樹
即二叉搜索樹：
- 所有非葉子節(jié)點至多擁有兩個子節(jié)點
- 所有結(jié)點存儲一個關(guān)鍵字
- 非葉子結(jié)點的左指針指向小于其關(guān)鍵字的子樹，右指針指向大于其關(guān)鍵字的子樹
B樹查找順序：從根結(jié)點開始，如果查詢的關(guān)鍵字與結(jié)點的關(guān)鍵字相等，命中；如果比結(jié)點關(guān)鍵字小，進入左子結(jié)點繼續(xù)查找，如果比結(jié)點關(guān)鍵字大，進入右子結(jié)點繼續(xù)查找；
B- 樹
是一種多路搜索樹（并不是二叉的）
1. 定義任意非葉子結(jié)點最多只有M個子結(jié)點，且M>2
2. 根結(jié)點的兒子數(shù)為[2,M]
3. 除根結(jié)點以外的非葉子結(jié)點兒子數(shù)為[M/2,M]
4. 每個結(jié)點存放至少M/2-1和至多M-1個關(guān)鍵字，（至少2個關(guān)鍵字）
5. 非葉子結(jié)點的關(guān)鍵字個數(shù) = 指向兒子的指針個數(shù)-1
6. 非葉子結(jié)點的關(guān)鍵字：K[1]
此坑待續(xù)~~~~
B+ 樹
B+樹是B-樹的變體，也是一種多路搜索樹：
1.其定義基本與B-樹同，除了：
2.非葉子結(jié)點的子樹指針與關(guān)鍵字個數(shù)相同；
3.非葉子結(jié)點的子樹指針P[i]，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹
5.為所有葉子結(jié)點增加一個鏈指針；
6.所有關(guān)鍵字都在葉子結(jié)點出現(xiàn)；
如：（M=3）
B+的搜索與B-樹也基本相同，區(qū)別是B+樹只有達到葉子結(jié)點才命中（B-樹可以在
非葉子結(jié)點命中），其性能也等價于在關(guān)鍵字全集做一次二分查找；
B+的特性：
1.所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點的鏈表中（稠密索引），且鏈表中的關(guān)鍵字恰好是有序的；
2.不可能在非葉子結(jié)點命中；
3.非葉子結(jié)點相當(dāng)于是葉子結(jié)點的索引（稀疏索引），葉子結(jié)點相當(dāng)于是存儲（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層；
4.更適合文件索引系統(tǒng)；
參考資料 http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html
