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