B+樹
B+樹是B樹的一種變體贝淤，也屬于平衡多路查找樹系羞，大體結(jié)構(gòu)與B樹相同郭计，包含根節(jié)點(diǎn)、內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)椒振。多用于數(shù)據(jù)庫和操作系統(tǒng)的文件系統(tǒng)中昭伸，由于B+樹內(nèi)部節(jié)點(diǎn)不保存數(shù)據(jù)，所以能在內(nèi)存中存放更多索引澎迎，增加緩存命中率勋乾。另外因?yàn)槿~子節(jié)點(diǎn)相連遍歷操作很方便，而且數(shù)據(jù)也具有順序性嗡善，便于區(qū)間查找辑莫。
B+樹特點(diǎn)
1.B+樹可以定義一個(gè)m值作為預(yù)定范圍，即m路(階)B+樹罩引。
根節(jié)點(diǎn)可能是葉子節(jié)點(diǎn)各吨，也可能是包含兩個(gè)或兩個(gè)以上子節(jié)點(diǎn)的節(jié)點(diǎn)。
2.內(nèi)部節(jié)點(diǎn)如果擁有k個(gè)關(guān)鍵字則有k+1個(gè)子節(jié)點(diǎn)袁铐。
3.非葉子節(jié)點(diǎn)不保存數(shù)據(jù)揭蜒，只保存關(guān)鍵字用作索引，所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)中剔桨。
4.非葉子節(jié)點(diǎn)有若干子樹指針屉更，如果非葉子節(jié)點(diǎn)關(guān)鍵字為k1,k2,...kn，其中n=m-1洒缀，那么第一個(gè)子樹關(guān)鍵字判斷條件為小于k1瑰谜，第二個(gè)為大于等于k1而小于k2，以此類推树绩，最后一個(gè)為大于等于kn萨脑，總共可以劃分出m個(gè)區(qū)間，即可以有m個(gè)分支饺饭。（判斷條件其實(shí)沒有嚴(yán)格的要求渤早，只要能實(shí)現(xiàn)對(duì)B+樹的數(shù)據(jù)進(jìn)行定位劃分即可，有些實(shí)現(xiàn)使用了m個(gè)關(guān)鍵字來劃分區(qū)間瘫俊，也是可以的）
5.所有葉子節(jié)點(diǎn)通過指針鏈相連鹊杖，且葉子節(jié)點(diǎn)本身按關(guān)鍵字的大小從小到大順序排列。
6.自然插入而不進(jìn)行刪除操作時(shí)扛芽，葉子節(jié)點(diǎn)項(xiàng)的個(gè)數(shù)范圍為[floor(m/2),m-1]骂蓖，內(nèi)部節(jié)點(diǎn)項(xiàng)的個(gè)數(shù)范圍為[ceil(m/2)-1,m-1]。
7.另外通常B+樹有兩個(gè)頭指針胸哥，一個(gè)指向根節(jié)點(diǎn)一個(gè)指向關(guān)鍵字最小的葉子節(jié)點(diǎn)涯竟。
8.在進(jìn)行刪除操作時(shí)，涉及到索引節(jié)點(diǎn)填充因子和葉子節(jié)點(diǎn)填充因子，一般可設(shè)葉子節(jié)點(diǎn)和索引節(jié)點(diǎn)的填充因子都不少于50%庐船。
以下是一棵4階B+樹银酬，
插入操作
假設(shè)現(xiàn)在構(gòu)建一棵四階B+樹，開始插入“A”筐钟，直接作為根節(jié)點(diǎn)揩瞪，
插入“B”，大于“A”篓冲，放右邊李破，
插入“C”，按順序排到最后壹将，
繼續(xù)插入“D”嗤攻，直接添加的結(jié)果如下圖，此時(shí)超過了節(jié)點(diǎn)可以存放容量诽俯，對(duì)于四階B+樹每個(gè)節(jié)點(diǎn)最多存放3個(gè)項(xiàng)妇菱，此時(shí)需要執(zhí)行分裂操作，
分裂操作為暴区，先選取待分裂節(jié)點(diǎn)中間位置的項(xiàng)闯团，這里選“C”，然后將“C”項(xiàng)放到父節(jié)點(diǎn)中仙粱，因?yàn)檫@里還沒有父節(jié)點(diǎn)房交，那么直接創(chuàng)建一個(gè)新的父節(jié)點(diǎn)存放“C”，而原來小于“C”的那些項(xiàng)作為左子樹伐割，原來大于等于“C”的那些項(xiàng)作為右子樹候味。這里注意下非葉子節(jié)點(diǎn)存放的都是關(guān)鍵字，用作索引的口猜，所以父節(jié)點(diǎn)存放的“C”項(xiàng)不包括數(shù)據(jù)负溪，數(shù)據(jù)仍然存放在右子樹。此外济炎，還需要添加一個(gè)指針，由左子樹指向右子樹辐真。
繼續(xù)插入“M”须尚，“M”大于“C”，往右子節(jié)點(diǎn)侍咱，
分別與“C”“D”比較耐床，大于它們，放到最右邊楔脯，
插入“L”撩轰，“L”大于“B”，往右子樹，
“L”逐一與節(jié)點(diǎn)內(nèi)項(xiàng)的值比較堪嫂，根據(jù)大小放到指定位置偎箫，此時(shí)觸發(fā)分裂操作，
選取待分裂節(jié)點(diǎn)中間位置的項(xiàng)“L”皆串，然后將“L”項(xiàng)放到父節(jié)點(diǎn)中淹办，按大小順序?qū)ⅰ癓”放到指定位置，而原來小于“L”的那些項(xiàng)作為左子樹恶复，原來大于等于“L”的那些項(xiàng)作為右子樹怜森。父節(jié)點(diǎn)存放的“L”項(xiàng)不包括數(shù)據(jù)，數(shù)據(jù)仍然存放在右子樹谤牡。此外副硅，還需要在左子樹中添加一個(gè)指向右子樹的指針。
繼續(xù)插入“K”翅萤，從根節(jié)點(diǎn)開始查找恐疲，逐一比較關(guān)鍵字，“K”大于“C”而小于“L”断序，往第二個(gè)分支流纹，
在子節(jié)點(diǎn)中逐一比較，“K”最終落在最右邊违诗，
繼續(xù)插入“J”漱凝，從根節(jié)點(diǎn)開始查找，逐一比較關(guān)鍵字诸迟，“J”大于“C”而小于“L”茸炒，往第二個(gè)分支，
在子節(jié)點(diǎn)中找到“J”的相應(yīng)位置阵苇，此時(shí)超過了節(jié)點(diǎn)的容量壁公，需要進(jìn)行分裂操作，
選取待分裂節(jié)點(diǎn)中間位置的項(xiàng)“J”绅项，然后將“J”項(xiàng)放到父節(jié)點(diǎn)中紊册，按大小順序?qū)ⅰ癑”放到指定位置，而原來小于“J”的那些項(xiàng)作為左子樹快耿，原來大于等于“J”的那些項(xiàng)作為右子樹囊陡。父節(jié)點(diǎn)存放的“J”項(xiàng)不包括數(shù)據(jù)，數(shù)據(jù)仍然存放在右子樹掀亥。此外撞反，還需要在左子樹中添加一個(gè)指向右子樹的指針。
繼續(xù)插入“I”搪花，從根節(jié)點(diǎn)開始查找遏片，逐一比較關(guān)鍵字嘹害，“I”大于“C”而小于“J”“L”，往第二個(gè)分支吮便，
逐一比較找到“I”的插入位置笔呀，
繼續(xù)插入“H”，從根節(jié)點(diǎn)開始查找线衫，逐一比較關(guān)鍵字凿可，“H”大于“C”而小于“J”“L”，往第二個(gè)分支授账，
“H”逐一與節(jié)點(diǎn)內(nèi)的值比較枯跑，根據(jù)大小放到指定位置，此時(shí)觸發(fā)分裂操作白热，
選取待分裂節(jié)點(diǎn)中間位置的項(xiàng)“H”敛助，然后將“H”項(xiàng)放到父節(jié)點(diǎn)中，按大小順序?qū)ⅰ癏”放到指定位置屋确，而原來小于“H”的那些項(xiàng)作為左子樹纳击，原來大于等于“H”的那些項(xiàng)作為右子樹。父節(jié)點(diǎn)存放的“H”項(xiàng)不包括數(shù)據(jù)攻臀，數(shù)據(jù)仍然存放在右子樹焕数。此外，還需要在左子樹中添加一個(gè)指向右子樹的指針刨啸。
但此時(shí)父節(jié)點(diǎn)超出了容量堡赔，父節(jié)點(diǎn)需要繼續(xù)分裂操作，
選取待分裂節(jié)點(diǎn)中間位置的項(xiàng)“J”设联，然后將“J”項(xiàng)放到父節(jié)點(diǎn)中善已，但還不存在父節(jié)點(diǎn)，需要?jiǎng)?chuàng)建一個(gè)作為父節(jié)點(diǎn)离例。原來小于“J”的那些項(xiàng)作為左子樹换团，原來大于“J”的那些項(xiàng)作為右子樹。這是非葉子節(jié)點(diǎn)的分裂宫蛆，操作對(duì)象都是用作索引的關(guān)鍵字艘包，不必考慮數(shù)據(jù)存放問題。
插入“G”耀盗，從根節(jié)點(diǎn)開始查找辑甜，“G”小于“J”，往第一個(gè)分支袍冷，
逐一比較節(jié)點(diǎn)內(nèi)項(xiàng)的值，“G”大于“C”小于“H”猫牡，往第二個(gè)分支胡诗，
逐一比較節(jié)點(diǎn)內(nèi)項(xiàng)的值，找到“G”的位置并插入，
插入“F”煌恢，從根節(jié)點(diǎn)開始查找骇陈，“F”小于“J”，往第一個(gè)分支瑰抵，
逐一比較節(jié)點(diǎn)內(nèi)項(xiàng)的值你雌，“F”大于“C”小于“H”，往第二個(gè)分支二汛，
逐一比較節(jié)點(diǎn)內(nèi)項(xiàng)的值婿崭，找到“F”的位置并插入，此時(shí)觸發(fā)分裂操作肴颊，
選取待分裂節(jié)點(diǎn)中間位置的項(xiàng)“F”氓栈，然后將“F”項(xiàng)放到父節(jié)點(diǎn)中，按大小順序?qū)ⅰ癋”放到指定位置婿着，而原來小于“F”的那些項(xiàng)作為左子樹授瘦，原來大于等于“F”的那些項(xiàng)作為右子樹。父節(jié)點(diǎn)存放的“F”項(xiàng)不包括數(shù)據(jù)竟宋，數(shù)據(jù)仍然存放在右子樹提完。此外，還需要在左子樹中添加一個(gè)指向右子樹的指針丘侠。
最后插入“E”徒欣，從根節(jié)點(diǎn)開始查找，“E”小于“J”婉陷，往第一個(gè)分支帚称，
逐一比較節(jié)點(diǎn)內(nèi)項(xiàng)的值，“E”大于“C”小于“F”秽澳，往第二個(gè)分支闯睹，
逐一比較節(jié)點(diǎn)內(nèi)項(xiàng)的值，找打“E”適當(dāng)?shù)奈恢貌⒉迦搿?/p>
從上面插入操作可以總結(jié)担神，插入主要就是涉及到分裂操作楼吃，而且要注意到非節(jié)點(diǎn)只保存了關(guān)鍵字作為索引，而數(shù)據(jù)都保存在葉子節(jié)點(diǎn)上妄讯，此外還需要使用指針將葉子節(jié)點(diǎn)連接起來孩锡。最終我們可以看到葉子節(jié)點(diǎn)的項(xiàng)按從小到大排列，因?yàn)橛辛酥羔樖沟每梢院芊奖惚闅v數(shù)據(jù)亥贸。
查找操作
對(duì)B+樹的查找與B樹的查找差不多躬窜，從根節(jié)點(diǎn)開始查找，通過比較項(xiàng)的值找到對(duì)應(yīng)的分支炕置，然后繼續(xù)往子樹上查找荣挨。
比如查找“H”男韧，“H”小于“J”，往第一個(gè)分支默垄，
逐一比較節(jié)點(diǎn)中的項(xiàng)此虑，發(fā)現(xiàn)應(yīng)該往第四個(gè)分支，
逐一比較口锭，找到“H”朦前。
遍歷操作
遍歷操作首先是要先找到樹最左邊的葉子節(jié)點(diǎn)，然后就可以通過指針完成整棵樹的遍歷了鹃操。
從根節(jié)點(diǎn)開始韭寸，一直往第一個(gè)分支走，
繼續(xù)往第一個(gè)分支走组民，
發(fā)現(xiàn)已經(jīng)到葉子節(jié)點(diǎn)了棒仍，這就是要找的遍歷的開端，
第一個(gè)葉子節(jié)點(diǎn)有兩個(gè)項(xiàng)臭胜，接著根據(jù)指針跳到第二個(gè)葉子節(jié)點(diǎn)莫其，
第二個(gè)節(jié)點(diǎn)有三個(gè)項(xiàng)，根據(jù)指針繼續(xù)往下一個(gè)節(jié)點(diǎn)耸三，
該節(jié)點(diǎn)有兩個(gè)項(xiàng)乱陡，根據(jù)指針繼續(xù)往下一個(gè)節(jié)點(diǎn)，
不斷根據(jù)指針往下仪壮，
往下憨颠，
完成整棵樹的遍歷。
轉(zhuǎn)自：https://blog.csdn.net/wangyangzhizhou/article/details/82453443
