本文主要以列表形式將B+樹的特點(diǎn)以及注意點(diǎn)等列出來蒙秒，主要參考《算法導(dǎo)論》悯森、維基百科、各大博客的內(nèi)容，結(jié)合自己的理解寫的摹量，如內(nèi)容有不當(dāng)之處，請各位雅正呻拌。 出處：http://blog.csdn.net/love_u_u12138 轉(zhuǎn)載請注明出處膀藐。

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é)點(diǎn)中零如，內(nèi)部節(jié)點(diǎn)只存放關(guān)鍵字和孩子指針躏将，因此最大化了內(nèi)部節(jié)點(diǎn)的分支因子，所以B+樹的遍歷也更加高效(B樹需要以中序的方式遍歷節(jié)點(diǎn)考蕾，而B+樹只需把所有葉子節(jié)點(diǎn)串成鏈表就可以從頭到尾遍歷)祸憋。

B+樹的圖示

2.定義

B+樹的定義我沒有找到官方的定義(如果有找到的人望告知我)蚯窥，有些定義在論壇還有爭議，但是這些并沒有多大影響塞帐，只是一點(diǎn)小小的差異拦赠，下面的定義中有涉及爭議的部分我會提及。

B+樹的定義如下：

每個節(jié)點(diǎn)node有下面的屬性： n個關(guān)鍵字key[1],key[2], … ,key[n]葵姥，以非降序存放荷鼠，使得key[1]≤key[2]≤…≤key[n]；
isRoot榔幸，一個布爾值颊咬，如果node是根節(jié)點(diǎn)务甥，則為TRUE；否則為FALSE喳篇；
isLeaf敞临，一個布爾值，如果node是葉子節(jié)點(diǎn)麸澜，則為TRUE挺尿；否則為FALSE；
Node*類型的parent指針炊邦，指向該節(jié)點(diǎn)的父節(jié)點(diǎn)

每個內(nèi)部節(jié)點(diǎn)還包含n個
指向其孩子children[0],children[1], … , children[n]编矾，葉子節(jié)點(diǎn)沒有孩子。（注：此處有爭議馁害，B+樹到底是與B 樹n-1個關(guān)鍵字有n棵子樹保持一致窄俏，還是B+樹n個關(guān)鍵字的結(jié)點(diǎn)中含有n棵子樹；兩種定義都可以碘菜，只要自己實現(xiàn)的時候統(tǒng)一用一種就行凹蜈。如無特殊說明，以下的都是后者：即n個關(guān)鍵字對應(yīng)n棵子樹）忍啸；
內(nèi)部節(jié)點(diǎn)的關(guān)鍵字對存儲在各子樹中的關(guān)鍵字范圍加以分割：如果key[i]為任意一個存儲在內(nèi)部節(jié)點(diǎn)中的關(guān)鍵字仰坦，childNum[i]為該節(jié)點(diǎn)的對應(yīng)下標(biāo)的子樹指針指向的節(jié)點(diǎn)的任意一個關(guān)鍵字，那么 key[1] ≤ childNum[1] < key[2] ≤ childNum[2] < key[3] ≤ childNum[3] < … < key[n] ≤ childNum[n]
內(nèi)部節(jié)點(diǎn)并不存儲真正的信息计雌，而是保存其葉子節(jié)點(diǎn)的最小值作為索引悄晃。比如下圖，標(biāo)注1和標(biāo)注2都是內(nèi)部節(jié)點(diǎn)凿滤，里面保存的并不是真正的信息妈橄，而是標(biāo)注3所示的節(jié)點(diǎn)中的最小值。(注：此處有爭議以最大值作為索引翁脆，同樣也是不影響的爭議)

內(nèi)部節(jié)點(diǎn)圖示

任何和關(guān)鍵字相聯(lián)系的**“衛(wèi)星數(shù)據(jù)(satellite information)” **將與關(guān)鍵字一樣存放在葉子節(jié)點(diǎn)中眷细，一般地，可能只是為每個關(guān)鍵字對應(yīng)的”衛(wèi)星數(shù)據(jù)”存放一個指針鹃祖，指針指向存放實際數(shù)據(jù)的磁盤頁，匹配了某個葉子節(jié)點(diǎn)的關(guān)鍵字即可通過該指針找到其他對應(yīng)數(shù)據(jù)普舆。

每個葉子節(jié)點(diǎn)還有指向下一個節(jié)點(diǎn)的指針next恬口，方便遍歷整棵B+樹。
每個葉子節(jié)點(diǎn)具有相同的深度沼侣，即樹的高度h祖能。
每個節(jié)點(diǎn)所包含的關(guān)鍵字個數(shù)有上界和下界，用一個被B+樹的最小度數(shù)(minmum degree)的固定整數(shù)t≥2來表示這些界： 除了根節(jié)點(diǎn)以外的每個節(jié)點(diǎn)必須至少有t個關(guān)鍵字蛾洛。因此养铸，除了根節(jié)點(diǎn)以外的每個內(nèi)部節(jié)點(diǎn)至少有t個孩子
每個節(jié)點(diǎn)至多有2t個關(guān)鍵字雁芙，因此，一個內(nèi)部節(jié)點(diǎn)至多可有2t個孩子钞螟。當(dāng)一個節(jié)點(diǎn)恰好有2t個關(guān)鍵字時兔甘，稱該節(jié)點(diǎn)是滿的。

結(jié)合以上的具體定義鳞滨，下面這張圖更加詳細(xì)的描述了一棵具體的B+樹

B+樹圖示

3.注意點(diǎn)

在B+樹的學(xué)習(xí)與實現(xiàn)過程中洞焙，也遇到不少的疑惑之處，現(xiàn)記錄如下拯啦，持續(xù)更新：
內(nèi)部節(jié)點(diǎn)并不存儲真正的信息澡匪，而是保存其葉子節(jié)點(diǎn)的最小值作為索引。每次插入刪除都進(jìn)行更新(此時用到parent指針)褒链，保持最新狀態(tài)唁情。
關(guān)于所有葉子節(jié)點(diǎn)都處于同一深度是如何實現(xiàn)的？這與B+樹具體的插入和刪除算法有關(guān)甫匹。簡單解釋一下插入時的情況甸鸟，根據(jù)插入值的大小，逐步向下直到對應(yīng)的葉子節(jié)點(diǎn)赛惩。如果葉子節(jié)點(diǎn)關(guān)鍵字個數(shù)小于2t哀墓，則直接插入值或者更新衛(wèi)星數(shù)據(jù)；如果插入之前葉子節(jié)點(diǎn)已經(jīng)滿了喷兼，則分裂該葉子節(jié)點(diǎn)成兩半篮绰，并把中間值提上到父節(jié)點(diǎn)的關(guān)鍵字中，如果這導(dǎo)致父節(jié)點(diǎn)滿了的話季惯，則把該父節(jié)點(diǎn)分裂吠各，如此遞歸向上。所以樹高是一層層的增加的勉抓，葉子節(jié)點(diǎn)永遠(yuǎn)都在同一深度贾漏。下面是我實現(xiàn)的B+樹中的插入代碼的片段：

public void insert(Comparable key, Object obj, BPlusTree tree)
{
    // 葉子節(jié)點(diǎn)則插入
    if (isLeaf) {
        // 不需要分裂直接插入
        if (containsKeyword(key) || keywords.size() < tree.getDegree()) {
            insertInNotFull(key, obj);
            // 直接插入
            if (parent != null) {
                parent.updateAfterInsert(tree);     // 更新父節(jié)點(diǎn)的信息(將最小的值存到父節(jié)點(diǎn)的關(guān)鍵字中作為索引)
            }
        } else {    // 需要分裂成左右兩個節(jié)點(diǎn)
            splitNode(key, obj, tree);
        }
    } else {        // 如果不是葉子節(jié)點(diǎn)則繼續(xù)往下搜索
        Node leafNode = downToLeaf(key); // 逐步向下到對應(yīng)的葉子節(jié)點(diǎn)
        leafNode.insert(key, obj, tree);
    }
}

4.結(jié)語

B+樹還有一個最大的好處，方便掃庫藕筋，B樹必須用中序遍歷的方法按序掃庫纵散，而B+樹直接從葉子結(jié)點(diǎn)挨個掃一遍就完了，B+樹支持range-query非常方便隐圾，而B樹不支持伍掀。這是數(shù)據(jù)庫選用B+樹的最主要原因。

歡迎各位大牛批評指正暇藏。PS：我實現(xiàn)了一個小型B+樹系統(tǒng)蜜笤，使用Java寫的，支持插入盐碱、搜索把兔、遍歷B+樹沪伙，有需要的同學(xué)可以去下載。鏈接奉上：http://download.csdn.net/detail/love_u_u12138/9355677

參考文獻(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