作者：Vernon

說(shuō)明：本文主要以列表形式將B+樹(shù)的特點(diǎn)以及注意點(diǎn)等列出來(lái)，主要參考《算法導(dǎo)論》唆垃、維基百科、各大博客的內(nèi)容痘儡，結(jié)合自己的理解寫的辕万，如內(nèi)容有不當(dāng)之處，請(qǐng)各位雅正沉删。

出處：http://blog.csdn.net/love_u_u12138

轉(zhuǎn)載請(qǐng)注明出處蓄坏。

1.前言

B樹(shù)是為磁盤或其他直接存取的輔助存儲(chǔ)設(shè)備而設(shè)計(jì)的一種平衡搜索樹(shù)。B樹(shù)類似于紅黑樹(shù)丑念，但它們?cè)诮档痛疟PI/O操作數(shù)方面要更好一些∥写粒現(xiàn)在許多數(shù)據(jù)庫(kù)系統(tǒng)使用B樹(shù)或者B樹(shù)的變種(B+樹(shù)和B*樹(shù))來(lái)存儲(chǔ)信息。B樹(shù)用的比較普遍脯倚，許多書籍渔彰、博客都有詳細(xì)的介紹嵌屎，對(duì)于B樹(shù)的嚴(yán)格定義也相對(duì)統(tǒng)一，在這里就不予贅述恍涂。

B+樹(shù)是B樹(shù)的一種變形宝惰，它把所有的衛(wèi)星數(shù)據(jù)都存儲(chǔ)在葉節(jié)點(diǎn)中，內(nèi)部節(jié)點(diǎn)只存放關(guān)鍵字和孩子指針再沧，因此最大化了內(nèi)部節(jié)點(diǎn)的分支因子尼夺，所以B+樹(shù)的遍歷也更加高效(B樹(shù)需要以中序的方式遍歷節(jié)點(diǎn)，而B+樹(shù)只需把所有葉子節(jié)點(diǎn)串成鏈表就可以從頭到尾遍歷)炒瘸。

以下先放一張我所依據(jù)的B+樹(shù)的圖示(這張圖有所簡(jiǎn)化淤堵，下面講完定義后會(huì)貼一張更加詳細(xì)的圖，兩圖本質(zhì)并無(wú)差異)：

2.定義

B+樹(shù)的定義我沒(méi)有找到官方的定義(如果有找到的人望告知我)顷扩，有些定義在論壇還有爭(zhēng)議拐邪，但是這些并沒(méi)有多大影響，只是一點(diǎn)小小的差異隘截，下面的定義中有涉及爭(zhēng)議的部分我會(huì)提及扎阶。

B+樹(shù)的定義如下：

1，每個(gè)節(jié)點(diǎn)node有下面的屬性：

1婶芭，n個(gè)關(guān)鍵字key[1],key[2], … ,key[n]东臀，以非降序存放，使得key[1]≤key[2]≤…≤key[n]犀农；

2惰赋，isRoot，一個(gè)布爾值井赌，如果node是根節(jié)點(diǎn)谤逼，則為TRUE贵扰；否則為FALSE仇穗；

3，isLeaf戚绕，一個(gè)布爾值纹坐，如果node是葉子節(jié)點(diǎn)，則為TRUE舞丛；否則為FALSE耘子；

4，Node*類型的parent指針球切，指向該節(jié)點(diǎn)的父節(jié)點(diǎn)

2谷誓， 每個(gè)內(nèi)部節(jié)點(diǎn)還包含n個(gè)指向其孩子children[0],children[1], … , children[n]，葉子節(jié)點(diǎn)沒(méi)有孩子吨凑。（注：此處有爭(zhēng)議捍歪，B+樹(shù)到底是與B 樹(shù)n-1個(gè)關(guān)鍵字有n棵子樹(shù)保持一致户辱，還是B+樹(shù)n個(gè)關(guān)鍵字的結(jié)點(diǎn)中含有n棵子樹(shù)；兩種定義都可以糙臼，只要自己實(shí)現(xiàn)的時(shí)候統(tǒng)一用一種就行庐镐。如無(wú)特殊說(shuō)明，以下的都是后者：即n個(gè)關(guān)鍵字對(duì)應(yīng)n棵子樹(shù)）变逃；

3必逆，內(nèi)部節(jié)點(diǎn)的關(guān)鍵字對(duì)存儲(chǔ)在各子樹(shù)中的關(guān)鍵字范圍加以分割：如果key[i]為任意一個(gè)存儲(chǔ)在內(nèi)部節(jié)點(diǎn)中的關(guān)鍵字，childNum[i]為該節(jié)點(diǎn)的對(duì)應(yīng)下標(biāo)的子樹(shù)指針指向的節(jié)點(diǎn)的任意一個(gè)關(guān)鍵字揽乱，那么

key[1] ≤ childNum[1] < key[2] ≤ childNum[2] < key[3] ≤ childNum[3] < … < key[n] ≤ childNum[n]

4名眉，內(nèi)部節(jié)點(diǎn)并不存儲(chǔ)真正的信息，而是保存其葉子節(jié)點(diǎn)的最小值作為索引锤窑。比如下圖璧针，標(biāo)注1和標(biāo)注2都是內(nèi)部節(jié)點(diǎn)，里面保存的并不是真正的信息渊啰，而是標(biāo)注3所示的節(jié)點(diǎn)中的最小值探橱。(注：此處有爭(zhēng)議以最大值作為索引，同樣也是不影響的爭(zhēng)議)

5绘证，任何和關(guān)鍵字相聯(lián)系的“衛(wèi)星數(shù)據(jù)(satellite information)” 將與關(guān)鍵字一樣存放在葉子節(jié)點(diǎn)中隧膏，一般地，可能只是為每個(gè)關(guān)鍵字對(duì)應(yīng)的”衛(wèi)星數(shù)據(jù)”存放一個(gè)指針嚷那，指針指向存放實(shí)際數(shù)據(jù)的磁盤頁(yè)胞枕，匹配了某個(gè)葉子節(jié)點(diǎn)的關(guān)鍵字即可通過(guò)該指針找到其他對(duì)應(yīng)數(shù)據(jù)。

6魏宽，每個(gè)葉子節(jié)點(diǎn)還有指向下一個(gè)節(jié)點(diǎn)的指針next腐泻，方便遍歷整棵B+樹(shù)。

7队询，每個(gè)葉子節(jié)點(diǎn)具有相同的深度派桩，即樹(shù)的高度h。

8蚌斩，每個(gè)節(jié)點(diǎn)所包含的關(guān)鍵字個(gè)數(shù)有上界和下界铆惑，用一個(gè)被B+樹(shù)的最小度數(shù)(minmum degree)的固定整數(shù)t≥2來(lái)表示這些界：

1，除了根節(jié)點(diǎn)以外的每個(gè)節(jié)點(diǎn)必須至少有t個(gè)關(guān)鍵字送膳。因此员魏，除了根節(jié)點(diǎn)以外的每個(gè)內(nèi)部節(jié)點(diǎn)至少有t個(gè)孩子

2，每個(gè)節(jié)點(diǎn)至多有2t個(gè)關(guān)鍵字叠聋，因此撕阎，一個(gè)內(nèi)部節(jié)點(diǎn)至多可有2t個(gè)孩子。當(dāng)一個(gè)節(jié)點(diǎn)恰好有2t個(gè)關(guān)鍵字時(shí)碌补，稱該節(jié)點(diǎn)是滿的虏束。

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

3.注意點(diǎn)

在B+樹(shù)的學(xué)習(xí)與實(shí)現(xiàn)過(guò)程中，也遇到不少的疑惑之處魄眉，現(xiàn)記錄如下砰盐，持續(xù)更新：

內(nèi)部節(jié)點(diǎn)并不存儲(chǔ)真正的信息，而是保存其葉子節(jié)點(diǎn)的最小值作為索引坑律。每次插入刪除都進(jìn)行更新(此時(shí)用到parent指針)岩梳，保持最新?tīng)顟B(tài)。

關(guān)于所有葉子節(jié)點(diǎn)都處于同一深度是如何實(shí)現(xiàn)的晃择？這與B+樹(shù)具體的插入和刪除算法有關(guān)冀值。簡(jiǎn)單解釋一下插入時(shí)的情況，根據(jù)插入值的大小宫屠，逐步向下直到對(duì)應(yīng)的葉子節(jié)點(diǎn)列疗。如果葉子節(jié)點(diǎn)關(guān)鍵字個(gè)數(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)分裂，如此遞歸向上缰猴。所以樹(shù)高是一層層的增加的产艾，葉子節(jié)點(diǎn)永遠(yuǎn)都在同一深度。下面是我實(shí)現(xiàn)的B+樹(shù)中的插入代碼的片段：

/** 插入關(guān)鍵字key */

? ? 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)鍵字中作為索引)

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? // 需要分裂成左右兩個(gè)節(jié)點(diǎn)

? ? ? ? ? ? } else {

? ? ? ? ? ? ? ? splitNode(key, obj, tree);

? ? ? ? ? ? }

? ? ? ? ? ? // 如果不是葉子節(jié)點(diǎn)則繼續(xù)往下搜索

? ? ? ? } else {

? ? ? ? ? ? Node leafNode = downToLeaf(key);? ? ? ? // 逐步向下到對(duì)應(yīng)的葉子節(jié)點(diǎn)

? ? ? ? ? ? leafNode.insert(key, obj, tree);

? ? ? ? }

}

4.結(jié)語(yǔ)

B+樹(shù)還有一個(gè)最大的好處滑绒，方便掃庫(kù)闷堡，B樹(shù)必須用中序遍歷的方法按序掃庫(kù)，而B+樹(shù)直接從葉子結(jié)點(diǎn)挨個(gè)掃一遍就完了疑故，B+樹(shù)支持range-query非常方便杠览，而B樹(shù)不支持。這是數(shù)據(jù)庫(kù)選用B+樹(shù)的最主要原因焰扳。 –梁斌

歡迎各位大牛批評(píng)指正倦零。PS：我實(shí)現(xiàn)了一個(gè)小型B+樹(shù)系統(tǒng)误续，使用Java寫的吨悍，支持插入、搜索蹋嵌、遍歷B+樹(shù)育瓜，有需要的同學(xué)可以去下載。鏈接奉上：http://download.csdn.net/detail/love_u_u12138/9355677

參考文獻(xiàn)

[1].《算法導(dǎo)論》原書第3版中文版

[2].https://zh.wikipedia.org/wiki/B%2B%E6%A0%91(維基百科B+樹(shù)條目)

[3].http://blog.csdn.net/v_july_v/article/details/6530142(很詳細(xì)的一篇B樹(shù)栽烂、B+樹(shù)躏仇、R樹(shù)的博客)

[4].http://www.ruanyifeng.com/blog/2014/07/database_implementation.html(數(shù)據(jù)庫(kù)實(shí)現(xiàn)的扼要說(shuō)明)

---------------------

作者：_Love_U_U_

來(lái)源：CSDN

原文：https://blog.csdn.net/love_u_u12138/article/details/50285655

版權(quán)聲明：本文為博主原創(chuàng)文章恋脚，轉(zhuǎn)載請(qǐng)附上博文鏈接！