B樹數(shù)據(jù)結(jié)構(gòu)

B樹示意圖

B＋樹的性質(zhì)
B+樹是B樹的變體，也是一種多路搜索樹，其定義基本與B樹同，除了：
１.　非葉子結(jié)點的子樹指針與關(guān)鍵字個數(shù)相同；
２.　非葉子結(jié)點的子樹指針P[i]，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹（B樹是開區(qū)間）；
３.　為所有葉子結(jié)點增加一個鏈指針；
４.　所有關(guān)鍵字都在葉子結(jié)點出現(xiàn)；

B＋樹與Ｂ樹的區(qū)別

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)；
　　 B+的搜索與B樹也基本相同，區(qū)別是B+樹只有達到葉子結(jié)點才命中（B樹可以在非葉子結(jié)點命中），其性能也等價于在關(guān)鍵字全集做一次二分查找；