B+樹
B+樹是應(yīng)文件系統(tǒng)所需而出的一種B-樹的變型樹，性質(zhì)如下：
(1) 有n棵子樹的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵字凹耙。
(2) 所有葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字信息，且葉子結(jié)點(diǎn)中的關(guān)鍵字依順序存放肠仪。
(3) 所有葉子結(jié)點(diǎn)增加一個(gè)鏈接指針連接在一起肖抱，便于遍歷元素。
(4) 所有的非終端結(jié)點(diǎn)可以看成是索引部分异旧，其結(jié)點(diǎn)中僅包含其子樹中的最大或最小關(guān)鍵字意述。
(5) 若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)最少包含2個(gè)子結(jié)點(diǎn)和2個(gè)關(guān)鍵字。
(6) 除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有[m/2]棵子樹和關(guān)鍵字吮蛹。
B-樹與B+樹的差異
m階的B樹和B+樹的差異(以5階為例):
- B+樹由分塊查找進(jìn)化而來;B樹由二叉排序樹進(jìn)化而來荤崇。
- 在B+樹中，每個(gè)非根結(jié)點(diǎn)關(guān)鍵字的取值范圍是3≤n≤5潮针，有n棵子樹;在B樹中术荤，每個(gè)非根結(jié)點(diǎn)關(guān)鍵字的取值范圍是2≤n≤4，有n+1棵子樹每篷。
- 在B+樹中瓣戚，僅葉結(jié)點(diǎn)包含信息，非葉結(jié)點(diǎn)只起索引作用;在B樹中焦读，全部結(jié)點(diǎn)的關(guān)鍵字都包含信息子库。
- 在B+樹中，葉結(jié)點(diǎn)包含了全部的關(guān)鍵字吨灭，非葉結(jié)點(diǎn)中出現(xiàn)的關(guān)鍵字一定會出現(xiàn)在葉結(jié)點(diǎn)中;在B樹中刚照，任何結(jié)點(diǎn)中的關(guān)鍵字都不會重復(fù)刑巧。
- B+樹支持順序查找和多路查找;B樹只支持多路查找喧兄。
- 在B+樹中，查找成功或失敗都會到達(dá)最下一層;而在B樹中啊楚，查找成功時(shí)吠冤，可能停在任何一層結(jié)點(diǎn)。
