本文主要以列表形式將B+樹的特點以及注意點等列出來饺蔑，主要參考《算法導(dǎo)論》锌介、維基百科、各大博客的內(nèi)容膀钠，結(jié)合自己的理解寫的掏湾，如內(nèi)容有不當(dāng)之處裹虫，請各位雅正。融击。
1.前言
B樹是為磁盤或其他直接存取的輔助存儲設(shè)備而設(shè)計的一種平衡搜索樹筑公。B樹類似于紅黑樹，但它們在降低磁盤I/O操作數(shù)方面要更好一些∽鹄耍現(xiàn)在許多數(shù)據(jù)庫系統(tǒng)使用B樹或者B樹的變種(B+樹和B*樹)來存儲信息匣屡。B樹用的比較普遍，許多書籍拇涤、博客都有詳細(xì)的介紹捣作，對于B樹的嚴(yán)格定義也相對統(tǒng)一，在這里就不予贅述鹅士。 B+樹是B樹的一種變形券躁，它把所有的衛(wèi)星數(shù)據(jù)都存儲在葉節(jié)點中，內(nèi)部節(jié)點只存放關(guān)鍵字和孩子指針掉盅，因此最大化了內(nèi)部節(jié)點的分支因子也拜，所以B+樹的遍歷也更加高效(B樹需要以中序的方式遍歷節(jié)點，而B+樹只需把所有葉子節(jié)點串成鏈表就可以從頭到尾遍歷)趾痘。
2.定義
B+樹的定義我沒有找到官方的定義(如果有找到的人望告知我)慢哈，有些定義在論壇還有爭議，但是這些并沒有多大影響永票，只是一點小小的差異卵贱，下面的定義中有涉及爭議的部分我會提及。
B+樹的定義如下：
每個節(jié)點node有下面的屬性： n個關(guān)鍵字key[1],key[2], … ,key[n]侣集，以非降序存放键俱，使得key[1]≤key[2]≤…≤key[n]；isRoot肚吏，一個布爾值方妖，如果node是根節(jié)點，則為TRUE罚攀；否則為FALSE；isLeaf雌澄，一個布爾值斋泄，如果node是葉子節(jié)點，則為TRUE镐牺；否則為FALSE炫掐；Node類型的parent指針，指向該節(jié)點的父節(jié)點
每個內(nèi)部節(jié)點還包含n個指向其孩子children[0],children[1], … , children[n]睬涧，葉子節(jié)點沒有孩子募胃。（注：此處有爭議旗唁，B+樹到底是與B 樹n-1個關(guān)鍵字有n棵子樹保持一致，還是B+樹n個關(guān)鍵字的結(jié)點中含有n棵子樹痹束；兩種定義都可以检疫，只要自己實現(xiàn)的時候統(tǒng)一用一種就行。如無特殊說明祷嘶，以下的都是后者：即n個關(guān)鍵字對應(yīng)n棵子樹*）屎媳；內(nèi)部節(jié)點的關(guān)鍵字對存儲在各子樹中的關(guān)鍵字范圍加以分割：如果key[i]為任意一個存儲在內(nèi)部節(jié)點中的關(guān)鍵字，childNum[i]為該節(jié)點的對應(yīng)下標(biāo)的子樹指針指向的節(jié)點的任意一個關(guān)鍵字论巍，那么 key[1] ≤ childNum[1] < key[2] ≤ childNum[2] < key[3] ≤ childNum[3] < … < key[n] ≤ childNum[n]內(nèi)部節(jié)點并不存儲真正的信息烛谊，而是保存其葉子節(jié)點的最小值作為索引。比如下圖嘉汰，標(biāo)注1和標(biāo)注2都是內(nèi)部節(jié)點丹禀，里面保存的并不是真正的信息，而是標(biāo)注3所示的節(jié)點中的最小值鞋怀。(注：此處有爭議以最大值作為索引双泪，同樣也是不影響的爭議)
內(nèi)部節(jié)點圖示
任何和關(guān)鍵字相聯(lián)系的“衛(wèi)星數(shù)據(jù)(satellite information)” 將與關(guān)鍵字一樣存放在葉子節(jié)點中，一般地接箫，可能只是為每個關(guān)鍵字對應(yīng)的”衛(wèi)星數(shù)據(jù)”存放一個指針攒读，指針指向存放實際數(shù)據(jù)的磁盤頁，匹配了某個葉子節(jié)點的關(guān)鍵字即可通過該指針找到其他對應(yīng)數(shù)據(jù)辛友。
每個葉子節(jié)點還有指向下一個節(jié)點的指針next薄扁，方便遍歷整棵B+樹。每個葉子節(jié)點具有相同的深度废累，即樹的高度h邓梅。每個節(jié)點所包含的關(guān)鍵字個數(shù)有上界和下界，用一個被B+樹的最小度數(shù)(minmum degree)的固定整數(shù)t≥2來表示這些界： 除了根節(jié)點以外的每個節(jié)點必須至少有t個關(guān)鍵字邑滨。因此日缨，除了根節(jié)點以外的每個內(nèi)部節(jié)點至少有t個孩子每個節(jié)點至多有2t個關(guān)鍵字，因此掖看，一個內(nèi)部節(jié)點至多可有2t個孩子匣距。當(dāng)一個節(jié)點恰好有2t個關(guān)鍵字時，稱該節(jié)點是滿的哎壳。
結(jié)合以上的具體定義毅待，下面這張圖更加詳細(xì)的描述了一棵具體的B+樹
B+樹圖示
3.注意點
在B+樹的學(xué)習(xí)與實現(xiàn)過程中，也遇到不少的疑惑之處归榕，現(xiàn)記錄如下尸红，持續(xù)更新：內(nèi)部節(jié)點并不存儲真正的信息，而是保存其葉子節(jié)點的最小值作為索引。每次插入刪除都進行更新(此時用到parent指針)外里，保持最新狀態(tài)怎爵。關(guān)于所有葉子節(jié)點都處于同一深度是如何實現(xiàn)的？這與B+樹具體的插入和刪除算法有關(guān)盅蝗。簡單解釋一下插入時的情況鳖链，根據(jù)插入值的大小，逐步向下直到對應(yīng)的葉子節(jié)點风科。如果葉子節(jié)點關(guān)鍵字個數(shù)小于2t撒轮，則直接插入值或者更新衛(wèi)星數(shù)據(jù)；如果插入之前葉子節(jié)點已經(jīng)滿了贼穆，則分裂該葉子節(jié)點成兩半题山，并把中間值提上到父節(jié)點的關(guān)鍵字中，如果這導(dǎo)致父節(jié)點滿了的話故痊，則把該父節(jié)點分裂顶瞳，如此遞歸向上。所以樹高是一層層的增加的愕秫，葉子節(jié)點永遠(yuǎn)都在同一深度慨菱。下面是我實現(xiàn)的B+樹中的插入代碼的片段：
public void insert(Comparable key, Object obj, BPlusTree tree)
{
// 葉子節(jié)點則插入
if (isLeaf) {
// 不需要分裂直接插入
if (containsKeyword(key) || keywords.size() < tree.getDegree()) {
insertInNotFull(key, obj);
// 直接插入
if (parent != null) {
parent.updateAfterInsert(tree); // 更新父節(jié)點的信息(將最小的值存到父節(jié)點的關(guān)鍵字中作為索引)
}
} else { // 需要分裂成左右兩個節(jié)點
splitNode(key, obj, tree);
}
} else { // 如果不是葉子節(jié)點則繼續(xù)往下搜索
Node leafNode = downToLeaf(key); // 逐步向下到對應(yīng)的葉子節(jié)點
leafNode.insert(key, obj, tree);
}
}
4.結(jié)語
B+樹還有一個最大的好處，方便掃庫戴甩，B樹必須用中序遍歷的方法按序掃庫符喝，而B+樹直接從葉子結(jié)點挨個掃一遍就完了，B+樹支持range-query非常方便甜孤，而B樹不支持协饲。這是數(shù)據(jù)庫選用B+樹的最主要原因。
參考文獻(xiàn)[1].《算法導(dǎo)論》原書第3版中文版[2].維基百科B+樹條目 https://zh.wikipedia.org/wiki/B%2B%E6%A0%91[3].很詳細(xì)的一篇B樹缴川、B+樹茉稠、R樹的博客 http://blog.csdn.net/v_july_v/article/details/6530142[4].數(shù)據(jù)庫實現(xiàn)的扼要說明 http://www.ruanyifeng.com/blog/2014/07/database_implementation.html
