B樹（B-樹）
B樹又名平衡多路二叉樹，和平衡二叉樹的區(qū)別在于：
子數(shù)節(jié)點(diǎn)數(shù)不同:平衡二叉樹每個節(jié)點(diǎn)最多有兩個節(jié)點(diǎn)，而M階B樹代表每個節(jié)點(diǎn)最多可以有M個子樹
每個節(jié)點(diǎn)包含的數(shù)據(jù)量不同：平衡二叉樹每個節(jié)點(diǎn)最多包含一個關(guān)鍵字(當(dāng)前節(jié)點(diǎn))代表的值和兩個孩子（左右）指針。而對于B樹(M階)，一個節(jié)點(diǎn)可以最多擁有M-1個關(guān)鍵字，M個鏈表指針。對于B樹的每個中間節(jié)點(diǎn)有
k-1個關(guān)鍵字(數(shù)字?jǐn)?shù)據(jù))和k個子數(shù)(k介于階數(shù)M和M/2之間,M/2向上取整)。葉子節(jié)點(diǎn)的分布不同: B樹的所有葉子節(jié)點(diǎn)都在同一層，并且葉子節(jié)點(diǎn)只有關(guān)鍵字，指向孩子的指針都為null.
B樹的滿足條件
- 若根結(jié)點(diǎn)不是終端結(jié)點(diǎn)，則至少有2棵樹。
- 除根結(jié)點(diǎn)外所有的非葉子結(jié)點(diǎn)都至少有M/2課子樹，至多M個子樹(關(guān)鍵字?jǐn)?shù)目=子數(shù)數(shù)目-1)。
- 所有葉子節(jié)點(diǎn)都位于同一層。
正是由于這些限制(如何證明?)，使得B樹能夠?qū)崿F(xiàn)動態(tài)平衡。
B樹.png
B樹的每個節(jié)點(diǎn)可以表示的信息更多，因此整個樹更加的"矮胖"，這在從磁盤中查找數(shù)據(jù)（先讀取到內(nèi)存、后查找）的過程中，可以減少磁盤 IO 的次數(shù)，從而提升查找速度。
比較淺的根據(jù)博客總結(jié)了B樹的特點(diǎn)。
總結(jié)完B+樹后進(jìn)行對比分析
B+樹
B+樹是基于B-樹的一種變體，有著比B-樹更高的查詢性能。
B+樹的滿足條件
節(jié)點(diǎn)的子樹數(shù)目和關(guān)鍵字?jǐn)?shù)目相同(而B樹是子樹數(shù)目-1)
節(jié)點(diǎn)的關(guān)鍵字(叫做索引)表示的是子樹中的最大數(shù)據(jù)，在子樹中同樣含有這個數(shù)據(jù)。
葉子節(jié)點(diǎn)包含了全部的數(shù)據(jù)，同時符號從左到右，從小到大的順序，并用指針連接在一起。
B+樹.jpg
簡要解釋:
第一點(diǎn)，B+樹中，節(jié)點(diǎn)的每一個關(guān)鍵字代表一個子樹的最大值，因此子結(jié)點(diǎn)數(shù)目等于關(guān)鍵字?jǐn)?shù)目。第二點(diǎn)，葉子節(jié)點(diǎn)包含了全部的數(shù)據(jù)，并按照順序排列，B+樹使用鏈表將他們連起來，這樣在查詢時效率更快。
B+樹對比B樹1.層級更低(更加矮胖),IO次數(shù)更少。由于 B+ 樹的中間節(jié)點(diǎn)不含有實(shí)際數(shù)據(jù)，只有子樹的最大數(shù)據(jù)和子樹指針，因此磁盤頁中可以容納更多節(jié)點(diǎn)元素，也就是說同樣數(shù)據(jù)情況下，B+ 樹會 B 樹更加“矮胖”，因此查詢效率更快。
2.每次都需要查詢到葉子節(jié)點(diǎn)，查詢性能穩(wěn)定。B樹這時就能體現(xiàn)出優(yōu)勢，由于出現(xiàn)頻率較高的樹，在B樹中往往在上層(非葉子結(jié)點(diǎn)),查找到該結(jié)點(diǎn)就會成功并結(jié)束查詢，相對較快。而B+樹由于非葉子結(jié)點(diǎn)關(guān)鍵字只是代表索引，因此在B+樹中，無論查找成功與否，都是走了一條從根到葉子節(jié)點(diǎn)的路徑。
3.B+樹范圍查詢更加方便。 需要查詢某個范圍內(nèi)的數(shù)據(jù)時，由于 B+ 樹的葉子節(jié)點(diǎn)是一個有序鏈表，只需在葉子節(jié)點(diǎn)上遍歷即可，不用像 B 樹那樣挨個中序遍歷比較大小。
