剛開(kāi)始學(xué)習(xí)的時(shí)候睡扬，百度去查谬哀，但發(fā)現(xiàn)好多說(shuō)得太復(fù)雜不好理解，結(jié)合各個(gè)文章總結(jié)一下（建議大概看文字绽族，不理解不要緊姨涡，然后再看圖的執(zhí)行步驟然后在結(jié)合文字，這樣一切就清晰好多）
B-tree吧慢，B是balance涛漂，一般用于數(shù)據(jù)庫(kù)的索引。使用B-tree結(jié)構(gòu)可以顯著減少定位記錄時(shí)所經(jīng)歷的中間過(guò)程，從而加快存取速度匈仗。而B(niǎo)+tree是B-tree的一個(gè)變種瓢剿，大名鼎鼎的MySQL就普遍使用B+tree實(shí)現(xiàn)其索引結(jié)構(gòu)。
那數(shù)據(jù)庫(kù)為什么使用這種結(jié)構(gòu)悠轩？
一般來(lái)說(shuō)间狂，索引本身也很大，不可能全部存儲(chǔ)在內(nèi)存中火架，因此索引往往以索引文件的形式存儲(chǔ)的磁盤(pán)上鉴象。這樣的話，索引查找過(guò)程中就要產(chǎn)生磁盤(pán)I/O消耗何鸡，相對(duì)于內(nèi)存存取炼列，I/O存取的消耗要高幾個(gè)數(shù)量級(jí)，所以評(píng)價(jià)一個(gè)數(shù)據(jù)結(jié)構(gòu)作為索引的優(yōu)劣最重要的指標(biāo)就是在查找過(guò)程中磁盤(pán)I/O操作次數(shù)的漸進(jìn)復(fù)雜度音比。換句話說(shuō)，索引的結(jié)構(gòu)組織要盡量減少查找過(guò)程中磁盤(pán)I/O的存取次數(shù)氢惋。
為了達(dá)到這個(gè)目的洞翩，磁盤(pán)按需讀取，要求每次都會(huì)預(yù)讀的長(zhǎng)度一般為頁(yè)的整數(shù)倍焰望。而且數(shù)據(jù)庫(kù)系統(tǒng)將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁(yè)骚亿，這樣每個(gè)節(jié)點(diǎn)只需要一次I/O就可以完全載入。每次新建節(jié)點(diǎn)時(shí)熊赖，直接申請(qǐng)一個(gè)頁(yè)的空間来屠，這樣就保證一個(gè)節(jié)點(diǎn)物理上也存儲(chǔ)在一個(gè)頁(yè)里，加之計(jì)算機(jī)存儲(chǔ)分配都是按頁(yè)對(duì)齊的震鹉，就實(shí)現(xiàn)了一個(gè)node只需一次I/O俱笛。并把B-tree中的m值設(shè)的非常大，就會(huì)讓樹(shù)的高度降低传趾，有利于一次完全載入
m-way查找樹(shù)（重點(diǎn)看步驟圖）
首先介紹一下m-way查找樹(shù)迎膜，顧名思義就是一棵樹(shù)的每個(gè)節(jié)點(diǎn)的度小于等于m。
故浆兰，它的性質(zhì)如下：
- 每個(gè)節(jié)點(diǎn)的鍵值數(shù)小于m
- 每個(gè)節(jié)點(diǎn)的度小于等于m
- 鍵值按順序排列
- 子樹(shù)的鍵值要完全小于或大于或介于父節(jié)點(diǎn)之間的鍵值
B-tree
B-tree又叫平衡多路查找樹(shù)磕仅。一棵m階的B-tree (m叉樹(shù))的特性如下：
（其中ceil(x)是一個(gè)取上限的函數(shù)）
- 樹(shù)中每個(gè)結(jié)點(diǎn)至多有m個(gè)孩子；
- 除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外簸呈，其它每個(gè)結(jié)點(diǎn)至少有有ceil(m / 2)個(gè)孩子榕订；
- 若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有2個(gè)孩子（特殊情況：沒(méi)有孩子的根結(jié)點(diǎn)蜕便，即根結(jié)點(diǎn)為葉子結(jié)點(diǎn)劫恒，整棵樹(shù)只有一個(gè)根節(jié)點(diǎn)）；
- 所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層轿腺，葉子結(jié)點(diǎn)不包含任何關(guān)鍵字信息(可以看做是外部結(jié)點(diǎn)或查詢失敗的結(jié)點(diǎn)兼贸，實(shí)際上這些結(jié)點(diǎn)不存在段直，指向這些結(jié)點(diǎn)的指針都為null)；
- 每個(gè)非終端結(jié)點(diǎn)中包含有n個(gè)關(guān)鍵字信息： (n溶诞，P0鸯檬，K1，P1螺垢，K2喧务，P2，......枉圃，Kn功茴，Pn)。其中：
- Ki (i=1...n)為關(guān)鍵字孽亲，且關(guān)鍵字按順序排序K(i-1)< Ki坎穿。
- Pi為指向子樹(shù)根的接點(diǎn)，且指針P(i-1)指向子樹(shù)種所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki返劲，但都大于K(i-1)玲昧。
- 關(guān)鍵字的個(gè)數(shù)n必須滿足： ceil(m / 2)-1 <= n <= m-1。
B-tree中的每個(gè)結(jié)點(diǎn)根據(jù)實(shí)際情況可以包含大量的關(guān)鍵字信息和分支(當(dāng)然是不能超過(guò)磁盤(pán)塊的大小篮绿，根據(jù)磁盤(pán)驅(qū)動(dòng)(disk drives)的不同孵延，一般塊的大小在1k~4k左右)；這樣樹(shù)的深度降低了亲配，這就意味著查找一個(gè)元素只要很少結(jié)點(diǎn)從外存磁盤(pán)中讀入內(nèi)存尘应，很快訪問(wèn)到要查找的數(shù)據(jù)。
下面以一棵5階B-tree實(shí)例進(jìn)行講解(如下圖所示)：（重點(diǎn)看以下圖）
其滿足上述條件：除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外吼虎，其它每個(gè)結(jié)點(diǎn)至少有ceil(5/2)=3個(gè)孩子（至少2個(gè)關(guān)鍵字）犬钢；當(dāng)然最多5個(gè)孩子（最多4個(gè)關(guān)鍵字）。下圖中關(guān)鍵字為大寫(xiě)字母思灰，順序?yàn)樽帜干颉?/p>
插入（insert）操作：插入一個(gè)元素時(shí)娜饵，首先在B-tree中是否存在，如果不存在官辈，即在葉子結(jié)點(diǎn)處結(jié)束箱舞，然后在葉子結(jié)點(diǎn)中插入該新的元素，注意：如果葉子結(jié)點(diǎn)空間足夠拳亿，這里需要向右移動(dòng)該葉子結(jié)點(diǎn)中大于新插入關(guān)鍵字的元素晴股，如果空間滿了以致沒(méi)有足夠的空間去添加新的元素，則將該結(jié)點(diǎn)進(jìn)行“分裂”肺魁，將一半數(shù)量的關(guān)鍵字元素分裂到新的其相鄰右結(jié)點(diǎn)中电湘，中間關(guān)鍵字元素上移到父結(jié)點(diǎn)中（當(dāng)然，如果父結(jié)點(diǎn)空間滿了，也同樣需要“分裂”操作）寂呛，而且當(dāng)結(jié)點(diǎn)中關(guān)鍵元素向右移動(dòng)了怎诫，相關(guān)的指針也需要向右移。如果在根結(jié)點(diǎn)插入新元素贷痪，空間滿了幻妓，則進(jìn)行分裂操作，這樣原來(lái)的根結(jié)點(diǎn)中的中間關(guān)鍵字元素向上移動(dòng)到新的根結(jié)點(diǎn)中劫拢，因此導(dǎo)致樹(shù)的高度增加一層肉津。
咱們通過(guò)一個(gè)實(shí)例來(lái)逐步講解下。插入以下字符字母到空的5階B-tree中：C N G A H E K Q M F W L T Z D P R X Y S舱沧，5序意味著一個(gè)結(jié)點(diǎn)最多有5個(gè)孩子和4個(gè)關(guān)鍵字妹沙，除根結(jié)點(diǎn)外其他結(jié)點(diǎn)至少有2個(gè)關(guān)鍵字，首先熟吏，結(jié)點(diǎn)空間足夠距糖，4個(gè)字母插入相同的結(jié)點(diǎn)中，如下圖：
當(dāng)咱們?cè)囍迦際時(shí)牵寺，結(jié)點(diǎn)發(fā)現(xiàn)空間不夠悍引，以致將其分裂成2個(gè)結(jié)點(diǎn)，移動(dòng)中間元素G上移到新的根結(jié)點(diǎn)中缸剪，在實(shí)現(xiàn)過(guò)程中，咱們把A和C留在當(dāng)前結(jié)點(diǎn)中东亦，而H和N放置新的其右鄰居結(jié)點(diǎn)中杏节。如下圖：
當(dāng)咱們插入E,K,Q時(shí)，不需要任何分裂操作
插入M需要一次分裂典阵，注意M恰好是中間關(guān)鍵字元素奋渔，以致向上移到父節(jié)點(diǎn)中
插入F,W,L,T不需要任何分裂操作
插入Z時(shí)，最右的葉子結(jié)點(diǎn)空間滿了壮啊，需要進(jìn)行分裂操作嫉鲸，中間元素T上移到父節(jié)點(diǎn)中，注意通過(guò)上移中間元素歹啼，樹(shù)最終還是保持平衡玄渗，分裂結(jié)果的結(jié)點(diǎn)存在2個(gè)關(guān)鍵字元素。
插入D時(shí)狸眼，導(dǎo)致最左邊的葉子結(jié)點(diǎn)被分裂藤树，D恰好也是中間元素，上移到父節(jié)點(diǎn)中拓萌，然后字母P,R,X,Y陸續(xù)插入不需要任何分裂操作岁钓。
最后，當(dāng)插入S時(shí)，含有N,P,Q,R的結(jié)點(diǎn)需要分裂屡限，把中間元素Q上移到父節(jié)點(diǎn)中品嚣，但是情況來(lái)了，父節(jié)點(diǎn)中空間已經(jīng)滿了钧大，所以也要進(jìn)行分裂翰撑，將父節(jié)點(diǎn)中的中間元素M上移到新形成的根結(jié)點(diǎn)中，注意以前在父節(jié)點(diǎn)中的第三個(gè)指針在修改后包括D和G節(jié)點(diǎn)中拓型。這樣具體插入操作的完成额嘿，下面介紹刪除操作，刪除操作相對(duì)于插入操作要考慮的情況多點(diǎn)劣挫。
刪除(delete)操作：首先查找B-tree中需刪除的元素,如果該元素在B-tree中存在册养，則將該元素在其結(jié)點(diǎn)中進(jìn)行刪除，如果刪除該元素后压固，首先判斷該元素是否有左右孩子結(jié)點(diǎn)球拦，如果有，則上移孩子結(jié)點(diǎn)中的某相近元素到父節(jié)點(diǎn)中帐我，然后是移動(dòng)之后的情況坎炼；如果沒(méi)有，直接刪除后拦键，移動(dòng)之后的情況.谣光。
刪除元素，移動(dòng)相應(yīng)元素之后芬为，如果某結(jié)點(diǎn)中元素?cái)?shù)目小于ceil(m/2)-1萄金，則需要看其某相鄰兄弟結(jié)點(diǎn)是否豐滿（結(jié)點(diǎn)中元素個(gè)數(shù)大于ceil(m/2)-1），如果豐滿媚朦，則向父節(jié)點(diǎn)借一個(gè)元素來(lái)滿足條件氧敢；如果其相鄰兄弟都剛脫貧，即借了之后其結(jié)點(diǎn)數(shù)目小于ceil(m/2)-1询张，則該結(jié)點(diǎn)與其相鄰的某一兄弟結(jié)點(diǎn)進(jìn)行“合并”成一個(gè)結(jié)點(diǎn)孙乖，以此來(lái)滿足條件。那咱們通過(guò)下面實(shí)例來(lái)詳細(xì)了解吧份氧。
以上述插入操作構(gòu)造的一棵5階B-tree為例唯袄，依次刪除H,T,R,E。
首先刪除元素H蜗帜，當(dāng)然首先查找H越妈，H在一個(gè)葉子結(jié)點(diǎn)中，且該葉子結(jié)點(diǎn)元素?cái)?shù)目3大于最小元素?cái)?shù)目ceil(m/2)-1=2钮糖，則操作很簡(jiǎn)單梅掠，咱們只需要移動(dòng)K至原來(lái)H的位置酌住，移動(dòng)L至K的位置（也就是結(jié)點(diǎn)中刪除元素后面的元素向前移動(dòng)）
下一步，刪除T,因?yàn)門沒(méi)有在葉子結(jié)點(diǎn)中阎抒，而是在中間結(jié)點(diǎn)中找到酪我，咱們發(fā)現(xiàn)他的繼承者W(字母升序的下個(gè)元素)，將W上移到T的位置且叁，然后將原包含W的孩子結(jié)點(diǎn)中的W進(jìn)行刪除都哭，這里恰好刪除W后，該孩子結(jié)點(diǎn)中元素個(gè)數(shù)大于2逞带，無(wú)需進(jìn)行合并操作欺矫。
下一步刪除R，R在葉子結(jié)點(diǎn)中,但是該結(jié)點(diǎn)中元素?cái)?shù)目為2展氓，刪除導(dǎo)致只有1個(gè)元素穆趴，已經(jīng)小于最小元素?cái)?shù)目ceil(5/2)-1=2,如果其某個(gè)相鄰兄弟結(jié)點(diǎn)中比較豐滿（元素個(gè)數(shù)大于ceil(5/2)-1=2），則可以向父結(jié)點(diǎn)借一個(gè)元素遇汞，然后將最豐滿的相鄰兄弟結(jié)點(diǎn)中上移最后或最前一個(gè)元素到父節(jié)點(diǎn)中未妹，在這個(gè)實(shí)例中，右相鄰兄弟結(jié)點(diǎn)中比較豐滿（3個(gè)元素大于2）空入，所以先向父節(jié)點(diǎn)借一個(gè)元素W下移到該葉子結(jié)點(diǎn)中络它，代替原來(lái)S的位置，S前移歪赢；然后X在相鄰右兄弟結(jié)點(diǎn)中上移到父結(jié)點(diǎn)中化戳，最后在相鄰右兄弟結(jié)點(diǎn)中刪除X，后面元素前移埋凯。
最后一步刪除E点楼，刪除后會(huì)導(dǎo)致很多問(wèn)題，因?yàn)镋所在的結(jié)點(diǎn)數(shù)目剛好達(dá)標(biāo)递鹉，剛好滿足最小元素個(gè)數(shù)（ceil(5/2)-1=2）,而相鄰的兄弟結(jié)點(diǎn)也是同樣的情況盟步，刪除一個(gè)元素都不能滿足條件藏斩，所以需要該節(jié)點(diǎn)與某相鄰兄弟結(jié)點(diǎn)進(jìn)行合并操作躏结；首先移動(dòng)父結(jié)點(diǎn)中的元素（該元素在兩個(gè)需要合并的兩個(gè)結(jié)點(diǎn)元素之間）下移到其子結(jié)點(diǎn)中，然后將這兩個(gè)結(jié)點(diǎn)進(jìn)行合并成一個(gè)結(jié)點(diǎn)狰域。所以在該實(shí)例中媳拴，咱們首先將父節(jié)點(diǎn)中的元素D下移到已經(jīng)刪除E而只有F的結(jié)點(diǎn)中，然后將含有D和F的結(jié)點(diǎn)和含有A,C的相鄰兄弟結(jié)點(diǎn)進(jìn)行合并成一個(gè)結(jié)點(diǎn)兆览。
也許你認(rèn)為這樣刪除操作已經(jīng)結(jié)束了屈溉，其實(shí)不然，在看看上圖抬探，對(duì)于這種特殊情況子巾，你立即會(huì)發(fā)現(xiàn)父節(jié)點(diǎn)只包含一個(gè)元素G帆赢，沒(méi)達(dá)標(biāo)，這是不能夠接受的线梗。如果這個(gè)問(wèn)題結(jié)點(diǎn)的相鄰兄弟比較豐滿椰于，則可以向父結(jié)點(diǎn)借一個(gè)元素。假設(shè)這時(shí)右兄弟結(jié)點(diǎn)（含有Q,X）有一個(gè)以上的元素（Q右邊還有元素）仪搔，然后咱們將M下移到元素很少的子結(jié)點(diǎn)中瘾婿，將Q上移到M的位置，這時(shí)烤咧，Q的左子樹(shù)將變成M的右子樹(shù)偏陪，也就是含有N，P結(jié)點(diǎn)被依附在M的右指針上煮嫌。所以在這個(gè)實(shí)例中笛谦，咱們沒(méi)有辦法去借一個(gè)元素，只能與兄弟結(jié)點(diǎn)進(jìn)行合并成一個(gè)結(jié)點(diǎn)立膛，而根結(jié)點(diǎn)中的唯一元素M下移到子結(jié)點(diǎn)揪罕，這樣，樹(shù)的高度減少一層宝泵。
為了進(jìn)一步詳細(xì)討論刪除的情況好啰。再舉另外一個(gè)實(shí)例：
這里是一棵不同的5階B-tree，那咱們?cè)囍鴦h除C
于是將刪除元素C的右子結(jié)點(diǎn)中的D元素上移到C的位置儿奶，但是出現(xiàn)上移元素后框往，只有一個(gè)元素的結(jié)點(diǎn)的情況。
又因?yàn)楹蠩的結(jié)點(diǎn)闯捎，其相鄰兄弟結(jié)點(diǎn)才剛脫貧（最少元素個(gè)數(shù)為2）椰弊，不可能向父節(jié)點(diǎn)借元素，所以只能進(jìn)行合并操作瓤鼻，于是這里將含有A,B的左兄弟結(jié)點(diǎn)和含有E的結(jié)點(diǎn)進(jìn)行合并成一個(gè)結(jié)點(diǎn)秉版。
這樣又出現(xiàn)只含有一個(gè)元素F結(jié)點(diǎn)的情況，這時(shí)茬祷，其相鄰的兄弟結(jié)點(diǎn)是豐滿的（元素個(gè)數(shù)為3>最小元素個(gè)數(shù)2）清焕，這樣就可以想父結(jié)點(diǎn)借元素了，把父結(jié)點(diǎn)中的J下移到該結(jié)點(diǎn)中祭犯，相應(yīng)的如果結(jié)點(diǎn)中J后有元素則前移秸妥，然后相鄰兄弟結(jié)點(diǎn)中的第一個(gè)元素（或者最后一個(gè)元素）上移到父節(jié)點(diǎn)中，后面的元素（或者前面的元素）前移（或者后移）沃粗；注意含有K粥惧，L的結(jié)點(diǎn)以前依附在M的左邊，現(xiàn)在變?yōu)橐栏皆贘的右邊最盅。這樣每個(gè)結(jié)點(diǎn)都滿足B-tree結(jié)構(gòu)性質(zhì)突雪。
