B+樹是B-樹的一種變形，它和B-樹有很多相似之處，可以對比來記憶。
1、B+樹的概念
既然是B-樹的一種變形，我們首先來回顧一下一棵B-樹的定義：
B-樹中所有結(jié)點中孩子結(jié)點個數(shù)的最大值成為B-樹的階，通常用m表示，從查找效率考慮，一般要求m>=3。一棵m階B-樹或者是一棵空樹，或者是滿足以下條件的m叉樹。
1）每個結(jié)點最多有m個分支（子樹）；而最少分支數(shù)要看是否為根結(jié)點，如果是根結(jié)點且不是葉子結(jié)點，則至少要有兩個分支，非根非葉結(jié)點至少有ceil(m/2)個分支，這里ceil代表向上取整。
2）如果一個結(jié)點有n-1個關(guān)鍵字，那么該結(jié)點有n個分支。這n-1個關(guān)鍵字按照遞增順序排列。
3）每個結(jié)點的結(jié)構(gòu)為：
| n | k1 | k2 | ... | kn |
|---|---|---|---|---|
| p0 | p1 | p2 | ... | pn |
其中，n為該結(jié)點中關(guān)鍵字的個數(shù)；ki為該結(jié)點的關(guān)鍵字且滿足ki<ki+1；pi為該結(jié)點的孩子結(jié)點指針且滿足pi所指結(jié)點上的關(guān)鍵字大于ki且小于ki+1，p0所指結(jié)點上的關(guān)鍵字小于k1，pn所指結(jié)點上的關(guān)鍵字大于kn。
4）結(jié)點內(nèi)各關(guān)鍵字互不相等且按從小到大排列。
5）葉子結(jié)點處于同一層；可以用空指針表示，是查找失敗到達的位置。
在給出B+樹和B-樹的不同之前，我們先給出一個例子讓大家直觀感受下二者的不同：
可以看到，m階B+樹和B-樹的差別主要體現(xiàn)在：
1）在B+樹中，具有n個關(guān)鍵字的結(jié)點有n個分支，而在B-樹中，具有n個關(guān)鍵字的結(jié)點含有n+1個關(guān)鍵字。
2）在B+樹中，每個結(jié)點（除根結(jié)點外）中的關(guān)鍵字個數(shù)n的取值為ceil(m/2) <= n <=m,根結(jié)點的取值范圍為1<=n<=m，他們的取值范圍分別是ceil(m/2) -1<= n <=m-1和1<=n<=m-1。
3）在B+樹中葉子結(jié)點包含信息，并且包含了全部關(guān)鍵字，葉子結(jié)點引出的指針指向記錄。
4）在B+樹中的所有非葉子結(jié)點僅起到一個索引的作用，即結(jié)點中的每個索引項只含有對應(yīng)子樹的最大關(guān)鍵字和指向該子樹的指針，不含有該關(guān)鍵字對應(yīng)記錄的存儲地址，而在B-樹中，每個關(guān)鍵字對應(yīng)一個記錄的存儲地址。
