1、概述

B+樹嗜价、B-樹.png

1.1艇抠、B-樹

1.1.1幕庐、B-樹概念

B-樹，即為B樹家淤。因為B樹的原英文名稱為B-tree异剥。B樹是一種自平衡樹數(shù)據(jù)結(jié)構(gòu)，它維護有序數(shù)據(jù)并允許以對數(shù)時間進行搜索絮重，順序訪問冤寿，插入和刪除。B樹是二叉搜索樹的一般化青伤，因為節(jié)點可以有兩個以上的子節(jié)點督怜。與其他自平衡二進制搜索樹不同，B樹非常適合讀取和寫入相對較大的數(shù)據(jù)塊（如光盤）的存儲系統(tǒng)狠角。它通常用于數(shù)據(jù)庫和文件系統(tǒng)号杠。

1.1.2、B-樹特點

B樹是一種平衡的多分樹丰歌，通常我們說m階的B樹姨蟋，它必須滿足如下條件：

• 每個節(jié)點最多只有m個子節(jié)點([3,6]算一個子節(jié)點，[13,16,19算一個子節(jié)點])立帖。
• 每個非葉子節(jié)點（除了根）具有至少? m/2?子節(jié)點眼溶。
• 如果根不是葉節(jié)點，則根至少有兩個子節(jié)點晓勇。
• 具有k個子節(jié)點的非葉節(jié)點包含k -1個鍵堂飞。
• 所有葉子都出現(xiàn)在同一水平，沒有任何信息（高度一致）绑咱。

B樹中一個節(jié)點的子節(jié)點數(shù)目的最大值绰筛，用m表示，假如最大值為10羡玛，則為10階别智，如圖:

image

所有節(jié)點中，節(jié)點【13,16,19】擁有的子節(jié)點數(shù)目最多稼稿，四個子節(jié)點（灰色節(jié)點），所以可以定義上面的圖片為4階B樹讳窟，現(xiàn)在懂什么是階了吧

什么是根節(jié)點 让歼？

節(jié)點【10】即為根節(jié)點，特征：根節(jié)點擁有的子節(jié)點數(shù)量的上限和內(nèi)部節(jié)點相同丽啡，如果根節(jié)點不是樹中唯一節(jié)點的話谋右，至少有倆個子節(jié)點（不然就變成單支了）。在m階B樹中（根節(jié)點非樹中唯一節(jié)點）补箍，那么有關(guān)系式2<= M <=m改执，M為子節(jié)點數(shù)量啸蜜；包含的元素數(shù)量 1<= K <=m-1,K為元素數(shù)量。

什么是內(nèi)部節(jié)點 辈挂？

節(jié)點【13,16,19】衬横、節(jié)點【3,6】都為內(nèi)部節(jié)點，特征：內(nèi)部節(jié)點是除葉子節(jié)點和根節(jié)點之外的所有節(jié)點终蒂，擁有父節(jié)點和子節(jié)點蜂林。假定m階B樹的內(nèi)部節(jié)點的子節(jié)點數(shù)量為M，則一定要符合（m/2）<= M <=m關(guān)系式拇泣，包含元素數(shù)量M-1噪叙；包含的元素數(shù)量 （m/2）-1<= K <=m-1,K為元素數(shù)量。m/2向上取整霉翔。

什么是葉子節(jié)點睁蕾？

節(jié)點【1,2】、節(jié)點【11,12】等最后一層都為葉子節(jié)點债朵，葉子節(jié)點對元素的數(shù)量有相同的限制惫霸，但是沒有子節(jié)點，也沒有指向子節(jié)點的指針葱弟。特征：在m階B樹中葉子節(jié)點的元素符合（m/2）-1<= K <=m-1壹店。

1.1.3、B-樹操作

插入

針對m階高度h的B樹芝加，插入一個元素時硅卢，首先在B樹中是否存在，如果不存在藏杖，即在葉子結(jié)點處結(jié)束将塑，然后在葉子結(jié)點中插入該新的元素。

• 若該節(jié)點元素個數(shù)小于m-1蝌麸，直接插入点寥；
• 若該節(jié)點元素個數(shù)等于m-1，引起節(jié)點分裂来吩；以該節(jié)點中間元素為分界敢辩，取中間元素（偶數(shù)個數(shù)，中間兩個隨機選鹊芙）插入到父節(jié)點中戚长；
• 重復(fù)上面動作，直到所有節(jié)點符合B樹的規(guī)則怠苔；最壞的情況一直分裂到根節(jié)點同廉，生成新的根節(jié)點，高度增加1；

上面三段話為插入動作的核心迫肖，接下來以5階B樹為例锅劝，詳細(xì)講解插入的動作；

5階B樹關(guān)鍵點:

• 2<=根節(jié)點子節(jié)點個數(shù)<=5
• 3<=內(nèi)節(jié)點子節(jié)點個數(shù)<=5
• 1<=根節(jié)點元素個數(shù)<=4
• 2<=非根節(jié)點元素個數(shù)<=4

img

img

圖（1）插入元素【8】后變?yōu)閳D（2）蟆湖，此時根節(jié)點元素個數(shù)為5故爵，不符合 1<=根節(jié)點元素個數(shù)<=4，進行分裂（真實情況是先分裂帐姻，然后插入元素稠集，這里是為了直觀而先插入元素，下面的操作都一樣饥瓷，不再贅述）剥纷，取節(jié)點中間元素【7】，加入到父節(jié)點呢铆，左右分裂為2個節(jié)點晦鞋，如圖（3）

img

接著插入元素【5】，【11】棺克，【17】時悠垛，不需要任何分裂操作，如圖（4）

img

插入元素【13】

img

節(jié)點元素超出最大數(shù)量娜谊，進行分裂确买，提取中間元素【13】，插入到父節(jié)點當(dāng)中纱皆，如圖（6）

![img](https://upload-images.jianshu.io/upload_images/17483701-580dc1b5123d6376.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

接著插入元素【6】湾趾，【12】，【20】派草，【23】時搀缠，不需要任何分裂操作，如圖（7）

img

插入【26】時近迁，最右的葉子結(jié)點空間滿了艺普，需要進行分裂操作，中間元素【20】上移到父節(jié)點中鉴竭，注意通過上移中間元素歧譬，樹最終還是保持平衡，分裂結(jié)果的結(jié)點存在2個關(guān)鍵字元素拓瞪。

img

插入【4】時缴罗，導(dǎo)致最左邊的葉子結(jié)點被分裂，【4】恰好也是中間元素祭埂，上移到父節(jié)點中，然后元素【16】,【18】,【24】,【25】陸續(xù)插入不需要任何分裂操作

img

最后，當(dāng)插入【19】時蛆橡，含有【14】,【16】,【17】,【18】的結(jié)點需要分裂舌界，把中間元素【17】上移到父節(jié)點中，但是情況來了泰演，父節(jié)點中空間已經(jīng)滿了呻拌，所以也要進行分裂，將父節(jié)點中的中間元素【13】上移到新形成的根結(jié)點中睦焕，這樣具體插入操作的完成藐握。

img

刪除

首先查找B樹中需刪除的元素,如果該元素在B樹中存在，則將該元素在其結(jié)點中進行刪除垃喊；刪除該元素后猾普，首先判斷該元素是否有左右孩子結(jié)點，如果有本谜，則上移孩子結(jié)點中的某相近元素(“左孩子最右邊的節(jié)點”或“右孩子最左邊的節(jié)點”)到父節(jié)點中初家，然后是移動之后的情況；如果沒有乌助，直接刪除溜在。

• 某結(jié)點中元素數(shù)目小于（m/2）-1,(m/2)向上取整，則需要看其某相鄰兄弟結(jié)點是否豐滿他托；
• 如果豐滿（結(jié)點中元素個數(shù)大于(m/2)-1）掖肋，則向父節(jié)點借一個元素來滿足條件；
• 如果其相鄰兄弟都不豐滿赏参，即其結(jié)點數(shù)目等于(m/2)-1志笼，則該結(jié)點與其相鄰的某一兄弟結(jié)點進行“合并”成一個結(jié)點；

接下來還以5階B樹為例登刺，詳細(xì)講解刪除的動作籽腕；

• 關(guān)鍵要領(lǐng)，元素個數(shù)小于 2（m/2 -1）就合并纸俭，大于4（m-1）就分裂

如圖依次刪除依次刪除【8】,【20】,【18】,【5】

img

首先刪除元素【8】皇耗，當(dāng)然首先查找【8】，【8】在一個葉子結(jié)點中揍很，刪除后該葉子結(jié)點元素個數(shù)為2郎楼，符合B樹規(guī)則，操作很簡單窒悔，咱們只需要移動【11】至原來【8】的位置呜袁，移動【12】至【11】的位置（也就是結(jié)點中刪除元素后面的元素向前移動）

img

下一步，刪除【20】,因為【20】沒有在葉子結(jié)點中简珠，而是在中間結(jié)點中找到阶界，咱們發(fā)現(xiàn)他的繼承者【23】(字母升序的下個元素)虹钮，將【23】上移到【20】的位置，然后將孩子結(jié)點中的【23】進行刪除膘融，這里恰好刪除后芙粱，該孩子結(jié)點中元素個數(shù)大于2，無需進行合并操作氧映。

img

下一步刪除【18】春畔，【18】在葉子結(jié)點中,但是該結(jié)點中元素數(shù)目為2，刪除導(dǎo)致只有1個元素岛都，已經(jīng)小于最小元素數(shù)目2,而由前面我們已經(jīng)知道：如果其某個相鄰兄弟結(jié)點中比較豐滿（元素個數(shù)大于ceil(5/2)-1=2）律姨，則可以向父結(jié)點借一個元素，然后將最豐滿的相鄰兄弟結(jié)點中上移最后或最前一個元素到父節(jié)點中臼疫，在這個實例中择份，右相鄰兄弟結(jié)點中比較豐滿（3個元素大于2），所以先向父節(jié)點借一個元素【23】下移到該葉子結(jié)點中多矮，代替原來【19】的位置缓淹，【19】前移；然【24】在相鄰右兄弟結(jié)點中上移到父結(jié)點中塔逃，最后在相鄰右兄弟結(jié)點中刪除【24】讯壶，后面元素前移。

img

最后一步刪除【5】湾盗， 刪除后會導(dǎo)致很多問題伏蚊，因為【5】所在的結(jié)點數(shù)目剛好達(dá)標(biāo)，剛好滿足最小元素個數(shù)（ceil(5/2)-1=2）,而相鄰的兄弟結(jié)點也是同樣的情況格粪，刪除一個元素都不能滿足條件躏吊，所以需要該節(jié)點與某相鄰兄弟結(jié)點進行合并操作；首先移動父結(jié)點中的元素（該元素在兩個需要合并的兩個結(jié)點元素之間）下移到其子結(jié)點中帐萎，然后將這兩個結(jié)點進行合并成一個結(jié)點比伏。所以在該實例中，咱們首先將父節(jié)點中的元素【4】下移到已經(jīng)刪除【5】而只有【6】的結(jié)點中疆导，然后將含有【4】和【6】的結(jié)點和含有【1】,【3】的相鄰兄弟結(jié)點進行合并成一個結(jié)點赁项。

img

也許你認(rèn)為這樣刪除操作已經(jīng)結(jié)束了，其實不然澈段，在看看上圖悠菜，對于這種特殊情況，你立即會發(fā)現(xiàn)父節(jié)點只包含一個元素【7】败富，沒達(dá)標(biāo)（因為非根節(jié)點包括葉子結(jié)點的元素K必須滿足于2=<K<=4悔醋，而此處的K=1），這是不能夠接受的兽叮。如果這個問題結(jié)點的相鄰兄弟比較豐滿芬骄，則可以向父結(jié)點借一個元素猾愿。而此時兄弟節(jié)點元素剛好為2，剛剛滿足德玫，只能進行合并匪蟀，而根結(jié)點中的唯一元素【13】下移到子結(jié)點椎麦，這樣宰僧，樹的高度減少一層。

img

1.2观挎、磁盤IO與預(yù)讀

計算機存儲設(shè)備一般分為兩種：內(nèi)存儲器(main memory)和外存儲器(external memory)琴儿。

內(nèi)存儲器為內(nèi)存，內(nèi)存存取速度快嘁捷，但容量小造成，價格昂貴，而且不能長期保存數(shù)據(jù)(在不通電情況下數(shù)據(jù)會消失)雄嚣。

外存儲器即為磁盤讀取晒屎，磁盤讀取數(shù)據(jù)靠的是機械運動，每次讀取數(shù)據(jù)花費的時間可以分為尋道時間缓升、旋轉(zhuǎn)延遲鼓鲁、傳輸時間三個部分：

尋道時間：指的是磁臂移動到指定磁道所需要的時間，主流磁盤一般在5ms以下港谊；

旋轉(zhuǎn)延遲：就是我們經(jīng)常聽說的磁盤轉(zhuǎn)速骇吭，比如一個磁盤7200轉(zhuǎn)，表示每分鐘能轉(zhuǎn)7200次歧寺，也就是說1秒鐘能轉(zhuǎn)120次燥狰，旋轉(zhuǎn)延遲就是1/120/2 = 4.17ms；

傳輸時間：指的是從磁盤讀出或?qū)?shù)據(jù)寫入磁盤的時間斜筐，一般在零點幾毫秒龙致，相對于前兩個時間可以忽略不計。

 那么訪問一次磁盤的時間顷链，即一次磁盤IO的時間約等于5+4.17 = 9ms左右目代，聽起來還挺不錯的，但要知道一臺500 -MIPS的機器每秒可以執(zhí)行5億條指令蕴潦，因為指令依靠的是電的性質(zhì)像啼，換句話說執(zhí)行一次IO的時間可以執(zhí)行40萬條指令，數(shù)據(jù)庫動輒十萬百萬乃至千萬級數(shù)據(jù)潭苞，每次9毫秒的時間忽冻，顯然是個災(zāi)難。

考慮到磁盤IO是非常高昂的操作此疹，計算機操作系統(tǒng)做了一些優(yōu)化僧诚，當(dāng)一次IO時遮婶，不光把當(dāng)前磁盤地址的數(shù)據(jù)，而是把相鄰的數(shù)據(jù)也都讀取到內(nèi)存緩沖區(qū)內(nèi)湖笨，因為**局部預(yù)讀性**原理告訴我們旗扑，當(dāng)計算機訪問一個地址的數(shù)據(jù)的時候，與其相鄰的數(shù)據(jù)也會很快被訪問到慈省。**每一次IO讀取的數(shù)據(jù)我們稱之為一頁(page)**臀防。具體一頁有多大數(shù)據(jù)跟操作系統(tǒng)有關(guān)，一般為4k或8k边败，也就是我們讀取一頁內(nèi)的數(shù)據(jù)時候袱衷，實際上才發(fā)生了一次IO，這個理論對于索引的數(shù)據(jù)結(jié)構(gòu)設(shè)計非常有幫助笑窜。

事實1 ： 不同容量的存儲器致燥，訪問速度差異懸殊。

• 磁盤(ms級別) << 內(nèi)存(ns級別)排截， 100000倍
• 若內(nèi)存訪問需要1s嫌蚤，則一次外存訪問需要一天
• 為了避免1次外存訪問，寧愿訪問內(nèi)存100次...所以將最常用的數(shù)據(jù)存儲在最快的存儲器中

事實2 ： 從磁盤中讀 1 B断傲，與讀寫 1KB 的時間成本幾乎一樣

從以上數(shù)據(jù)中可以總結(jié)出一個道理空郊，索引查詢的數(shù)據(jù)主要受限于硬盤的I/O速度销部，查詢I/O次數(shù)越少，速度越快，所以B樹的結(jié)構(gòu)才應(yīng)需求而生驰怎；B樹的每個節(jié)點的元素可以視為一次I/O讀取瓷式，樹的高度表示最多的I/O次數(shù)根欧，在相同數(shù)量的總元素個數(shù)下恩敌，每個節(jié)點的元素個數(shù)越多，高度越低乔外，查詢所需的I/O次數(shù)越少床三；假設(shè)，一次硬盤一次I/O數(shù)據(jù)為8K杨幼，索引用int(4字節(jié))類型數(shù)據(jù)建立撇簿，理論上一個節(jié)點最多可以為2000個元素，80億條的數(shù)據(jù)只需3次I/O（理論值）差购，可想而知四瘫，B樹做為索引的查詢效率有多高；

1.3欲逃、B+樹

1.3.1找蜜、B+樹特點

B+樹是應(yīng)文件系統(tǒng)所需而產(chǎn)生的B樹的變形樹，那么可能一定會想到稳析，既然有了B樹洗做，又出一個B+樹弓叛，那B+樹必然是有很多優(yōu)點的:

• 關(guān)鍵字?jǐn)?shù)和子樹相同
• 非葉子節(jié)點僅用作索引，它的關(guān)鍵字和子節(jié)點有重復(fù)元素
• 葉子節(jié)點用指針連在一起

補充：B樹的范圍查找用的是中序遍歷诚纸，而B+樹用的是在鏈表上遍歷撰筷；

img

從上圖可以看出，不但節(jié)點之間含有重復(fù)元素畦徘，而且葉子結(jié)點還用指針連接在一起毕籽。這正是B+樹的幾個特征，首先旧烧，每個元素都出現(xiàn)子節(jié)點中影钉，是子節(jié)點的最大（或者最小）元素掘剪。

1.3.2、衛(wèi)星數(shù)據(jù)

至于葉子節(jié)點奈虾，由于父節(jié)點的元素都出現(xiàn)在子節(jié)點夺谁，因此葉子結(jié)點包含了全部元素的信息。并且每個葉子節(jié)點都帶有指向下一個節(jié)點的指針肉微，形成了一個有序鏈表匾鸥。

image

B+樹還具有一個重要的特點，這個特點是在索引之外碉纳，確實至關(guān)重要的特點勿负。那就是【衛(wèi)星數(shù)據(jù)】，

所謂衛(wèi)星數(shù)據(jù)劳曹，指的就是索引元素所指向的數(shù)據(jù)記錄奴愉，比如數(shù)據(jù)庫中的某一行。在B-樹中铁孵，無論是中間節(jié)點還是葉子結(jié)點都帶有衛(wèi)星數(shù)據(jù)锭硼，而在B+樹當(dāng)中，只有葉子節(jié)點帶有衛(wèi)星數(shù)據(jù)蜕劝，其余中間節(jié)點僅僅是索引檀头，沒有任何數(shù)據(jù)關(guān)聯(lián)。

B-樹中的衛(wèi)星數(shù)據(jù)（Satellite Information）：

image

B+樹中的衛(wèi)星數(shù)據(jù)（Satellite Information）：

image

需要補充的是岖沛，在數(shù)據(jù)庫的聚集索引（Clustered Index）中暑始，葉子節(jié)點直接包含衛(wèi)星數(shù)據(jù)。在非聚集索引（NonClustered Index）中婴削，葉子節(jié)點帶有指向衛(wèi)星數(shù)據(jù)的指針廊镜。

2、拓展

2.1馆蠕、B樹的優(yōu)點

B+樹的優(yōu)點：

• B+樹的中間節(jié)點沒有衛(wèi)星數(shù)據(jù)期升，所以同樣大小的磁盤頁可以容納更多的節(jié)點元素惊奇，這就意味著在數(shù)據(jù)量相同的情況下，B+樹更加的矮胖播赁，因此IO的次數(shù)也就較少
• 所有查詢都要查找到葉子節(jié)點颂郎，查詢性能穩(wěn)定。
• 所有葉子節(jié)點形成有序鏈表容为，便于范圍查詢,遠(yuǎn)遠(yuǎn)高于B-樹