B樹的搜刮，從根結點開端，若是查詢的關鍵字與結點的關鍵字相等，那麼就射中；不然，若是查詢關鍵字比結點關鍵字小，就進入左兒子；若是比結點關鍵字大，就進入右兒子；若是左兒子或右兒子的指針為空，則呈報找不到響應的關鍵字；若是B樹的所有非葉子結點的閣下子樹的結點數量均對峙差不久不多（均衡），那麼B樹的搜刮機能切近親近二分查找；但它比連氣兒記憶體空間的二分查找的長處是，改變B樹布局（插入與删除結點）不須要移動大段的記憶體資料，甚至凡是是常數開銷；
如：
但B樹在經過多次插入與删除後，有可能導緻不合的布局：
右邊也是一個B樹，但它的搜刮機能已經是線性的了；同樣的關鍵字湊集有可能導緻不合的樹布局索引；是以，應用B樹還要推敲盡可能讓B樹對峙左圖的布局，和避免右圖的布局，也就是所謂的“均衡”題目； 實際應用的B樹都是在原B樹的根蒂根基上加上均衡算法，即“均衡二叉樹”；如何對峙B樹結點分布均勻的均衡算法是均衡二叉樹的關鍵；均衡算法是一種在B樹中插入和删除結點的政策；
B-樹
是一種多路搜刮樹（并不是二叉的）：
1.定義随便率性非葉子結點最多隻有M個兒子；且M>2；
2.根結點的兒子數為[2， M]；
3.除根結點以外的非葉子結點的兒子數為[M/2， M]；
4.每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字）
5.非葉子結點的關鍵字個數=指向兒子的指針個數-1；
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.所有葉子結點位于同一層；
如：（M=3）
B-樹的搜刮，從根結點開端，對結點内的關鍵字（有序）序列進行二分查找，若是射中則停止，不然進入查詢關鍵字所屬局限的兒子結點；反複，直到所對應的兒子指針為空，或已經是葉子結點；
B-樹的特點：
1.關鍵字湊集分布在整顆樹中；
2.任何一個關鍵字呈現且隻呈如今一個結點中；
3.搜刮有可能在非葉子結點停止；
4.其搜刮機能等價于在關鍵字全集内做一次二分查找；
5.主動層次把握；
因為限制了除根結點以外的非葉子結點，至少含有M/2個兒子，確定了卻點的至少哄騙率，其最底搜刮機能為：
此中，M為設定的非葉子結點最多子樹個數，N為關鍵字總數；
是以B-樹的機能老是等價于二分查找（與M值無關），也就沒有B樹均衡的題目；
因為M/2的限制，在插入結點時，若是結點已滿，須要将結點割據為兩個各占M/2的結點；删除結點時，需将兩個不足M/2的兄弟結點歸并；
B+樹
B+樹是B-樹的變體，也是一種多路搜刮樹：
1.其定義根蒂根基與B-樹同，除了：
2.非葉子結點的子樹指針與關鍵字個數雷同；
3.非葉子結點的子樹指針P[i]，指向關鍵字值屬于[K[i]， K[i+1]）的子樹（B-樹是開區間）；
5.為所有葉子結點增長一個鍊指針；
6.所有關鍵字都在葉子結點呈現；
B+的特點：
1.所有關鍵字都呈如今葉子結點的連結清單中（稠密索引），且連結清單中的關鍵字正好是有序的；
2.不成能在非葉子結點射中；
3.非葉子結點相當于是葉子結點的索引（稀少索引），葉子結點相當于是存儲（關鍵字）資料的資料層；
4.更合适檔案索引體系；
B*樹
是B+樹的變體，在B+樹的非根和非葉子結點再增長指向兄弟的指針；
B+樹的割據：當一個結點滿時，分派一個新的結點，并将原結點中1/2的資料複制到新結點，最後在父結點中增長新結點的指針；B+樹的割據隻影響原結點和父結點，而不會影響兄弟結點，是以它不須要指向兄弟的指針；
B*樹的割據：當一個結點滿時，若是它的下一個兄弟結點未滿，那麼将一項目組資料移到兄弟結點中，再在原結點插入關鍵字，最後批改父結點中兄弟結點的關鍵字（因為兄弟結點的關鍵字局限改變了）；若是兄弟也滿了，則在原結點與兄弟結點之間增長新結點，并各複制1/3的資料到新結點，最後在父結點增長新結點的指針；
是以，B*樹分派新結點的機率比B+樹要低，空間應用率更高；
小結
B樹：二叉樹，每個結點隻存儲一個關鍵字，便是則射中，小于走左結點，大于走右結點；
B-樹：多路搜刮樹，每個結點存儲M/2到M個關鍵字，非葉子結點存儲指向關鍵字局限的子結點；
所有關鍵字在整顆樹中呈現，且隻呈現一次，非葉子結點可以射中；
B+樹：在B-樹根蒂根基上，為葉子結點增長連結清單指針，所有關鍵字都在葉子結點中呈現，非葉子結點作為葉子結點的索引；B+樹老是到葉子結點才射中；
B*樹：在B+樹根蒂根基上，為非葉子結點也增長連結清單指針，将結點的最低哄騙率從1/2進步到2/3；