前言

當(dāng)你在遇到了一條慢?SQL?需要進(jìn)行優(yōu)化時(shí)，你第一時(shí)間能想到的優(yōu)化手段是什么？

大部分人第一反應(yīng)可能都是添加索引，在大多數(shù)情況下面，索引能夠?qū)⒁粭l?SQL?語(yǔ)句的查詢(xún)效率提高幾個(gè)數(shù)量級(jí)。

索引的本質(zhì)：用于快速查找記錄的一種數(shù)據(jù)結(jié)構(gòu)。

索引的常用數(shù)據(jù)結(jié)構(gòu)：

二叉樹(shù)

紅黑樹(shù)

Hash 表

B-tree?（B樹(shù)，并不叫什么B減樹(shù)）

B+tree

數(shù)據(jù)結(jié)構(gòu)圖形化網(wǎng)址：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

索引查詢(xún)

大家知道?select * from t where col = 88?這么一條?SQL?語(yǔ)句如果不走索引進(jìn)行查找的話，正常地查就是全表掃描：從表的第一行記錄開(kāi)始逐行找，把每一行的?col?字段的值和?88?進(jìn)行對(duì)比，這明顯效率是很低的。

而如果走索引的話，查詢(xún)的流程就完全不一樣了（假設(shè)現(xiàn)在用一棵平衡二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)我們的索引列）

此時(shí)該二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)（Key - Value）：Key 就是索引字段的數(shù)據(jù)，Value 就是索引所在行的磁盤(pán)文件地址。

當(dāng)最后找到了?88?的時(shí)候，就可以把它的 Value 對(duì)應(yīng)的磁盤(pán)文件地址拿出來(lái)，然后就直接去磁盤(pán)上去找這一行的數(shù)據(jù)，這時(shí)候的速度就會(huì)比全表掃描要快很多。

但實(shí)際上?MySQL?底層并沒(méi)有用二叉樹(shù)來(lái)存儲(chǔ)索引數(shù)據(jù)，是用的?B+tree（B+樹(shù)）。

為什么不采用二叉樹(shù)

假設(shè)此時(shí)用普通二叉樹(shù)記錄?id?索引列，我們?cè)诿坎迦胍恍杏涗浀耐瑫r(shí)還要維護(hù)二叉樹(shù)索引字段。

此時(shí)當(dāng)我要找?id = 7?的那條數(shù)據(jù)時(shí)，它的查找過(guò)程如下：

此時(shí)找?id = 7?這一行記錄時(shí)找了?7?次，和我們?nèi)頀呙枰矝](méi)什么很大區(qū)別。顯而易見(jiàn)，二叉樹(shù)對(duì)于這種依次遞增的數(shù)據(jù)列其實(shí)是不適合作為索引的數(shù)據(jù)結(jié)構(gòu)。

為什么不采用 Hash 表

“

Hash 表：一個(gè)快速搜索的數(shù)據(jù)結(jié)構(gòu)，搜索的時(shí)間復(fù)雜度 O(1)

Hash 函數(shù)：將一個(gè)任意類(lèi)型的 key，可以轉(zhuǎn)換成一個(gè) int 類(lèi)型的下標(biāo)

”

假設(shè)此時(shí)用 Hash 表記錄?id?索引列，我們?cè)诿坎迦胍恍杏涗浀耐瑫r(shí)還要維護(hù) Hash 表索引字段。

這時(shí)候開(kāi)始查找?id = 7?的樹(shù)節(jié)點(diǎn)僅找了?1?次，效率非常高了。

但?MySQL?的索引依然不采用能夠精準(zhǔn)定位的Hash 表。因?yàn)樗贿m用于范圍查詢(xún)。

為什么不采用紅黑樹(shù)

“

紅黑樹(shù)是一種特化的 AVL樹(shù)（平衡二叉樹(shù)），都是在進(jìn)行插入和刪除操作時(shí)通過(guò)特定操作保持二叉查找樹(shù)的平衡；

若一棵二叉查找樹(shù)是紅黑樹(shù)，則它的任一子樹(shù)必為紅黑樹(shù)。

”

假設(shè)此時(shí)用紅黑樹(shù)記錄?id?索引列，我們?cè)诿坎迦胍恍杏涗浀耐瑫r(shí)還要維護(hù)紅黑樹(shù)索引字段。

插入過(guò)程中會(huì)發(fā)現(xiàn)它與普通二叉樹(shù)不同的是當(dāng)一棵樹(shù)的左右子樹(shù)高度差 > 1 時(shí)，它會(huì)進(jìn)行自旋操作，保持樹(shù)的平衡。

這時(shí)候開(kāi)始查找?id = 7?的樹(shù)節(jié)點(diǎn)只找了?3?次，比所謂的普通二叉樹(shù)還是要更快的。

但?MySQL?的索引依然不采用能夠精確定位和范圍查詢(xún)都優(yōu)秀的紅黑樹(shù)。

因?yàn)楫?dāng)?MySQL?數(shù)據(jù)量很大的時(shí)候，索引的體積也會(huì)很大，可能內(nèi)存放不下，所以需要從磁盤(pán)上進(jìn)行相關(guān)讀寫(xiě)，如果樹(shù)的層級(jí)太高，則讀寫(xiě)磁盤(pán)的次數(shù)（I/O交互）就會(huì)越多，性能就會(huì)越差。

B-tree

“

紅黑樹(shù)目前的唯一不足點(diǎn)就是樹(shù)的高度不可控，所以現(xiàn)在我們的切入點(diǎn)就是樹(shù)的高度。

目前一個(gè)節(jié)點(diǎn)是只分配了一個(gè)存儲(chǔ) 1 個(gè)元素，如果要控制高度，我們就可以把一個(gè)節(jié)點(diǎn)分配的空間更大一點(diǎn)，讓它橫向存儲(chǔ)多個(gè)元素，這個(gè)時(shí)候高度就可控了。這么個(gè)改造過(guò)程，就變成了?B-tree。

”

B-tree?是一棵絕對(duì)平衡的多路樹(shù)。它的結(jié)構(gòu)中還有兩個(gè)概念

“

度（Degree）：一個(gè)節(jié)點(diǎn)擁有的子節(jié)點(diǎn)（子樹(shù)）的數(shù)量。（有的地方是以度來(lái)說(shuō)明?B-tree?的，這里解釋一下）

階（order）：一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的最大個(gè)數(shù)。（通常用?m?表示）

關(guān)鍵字：數(shù)據(jù)索引。

”

一棵 m 階?B-tree?是一棵平衡的 m 路搜索樹(shù)。它可能是空樹(shù)，或者滿(mǎn)足以下特點(diǎn)：

除根節(jié)點(diǎn)和葉子節(jié)點(diǎn)外，其它每個(gè)節(jié)點(diǎn)至少有??個(gè)子節(jié)點(diǎn)；

為 m / 2 然后向上取整

每個(gè)非根節(jié)點(diǎn)所包含的關(guān)鍵字個(gè)數(shù) j 滿(mǎn)足：?- 1 ≤ j ≤ m - 1；

節(jié)點(diǎn)的關(guān)鍵字從左到右遞增排列，有 k 個(gè)關(guān)鍵字的非葉子節(jié)點(diǎn)正好有 (k + 1) 個(gè)子節(jié)點(diǎn)；

所有的葉子結(jié)點(diǎn)都位于同一層。

名字取義（題外話，放松一下）

以下摘自維基百科

魯?shù)婪颉ぐ轄枺≧udolf Bayer）和 艾華·M·麥克雷（Ed M. McCreight）于1972年在波音研究實(shí)驗(yàn)室（Boeing Research Labs）工作時(shí)發(fā)明了?B-tree，但是他們沒(méi)有解釋 B 代表什么意義（如果有的話）。

道格拉斯·科默爾（Douglas Comer）解釋說(shuō)：兩位作者從來(lái)都沒(méi)解釋過(guò)?B-tree?的原始意義。我們可能覺(jué)得 balanced, broad 或 bushy 可能適合。其他人建議字母 B 代表 Boeing。源自于他的贊助，不過(guò)，看起來(lái)把?B-tree?當(dāng)作 Bayer 樹(shù)更合適些。

高德納（Donald Knuth）在他1980年5月發(fā)表的題為 "CS144C classroom lecture about disk storage and B-trees" 的論文中推測(cè)了?B-tree?的名字取義，提出 B 可能意味 Boeing 或者 Bayer 的名字。

查找

B-tree?的查找其實(shí)和二叉樹(shù)很相似：

二叉樹(shù)是每個(gè)節(jié)點(diǎn)上有一個(gè)關(guān)鍵字和兩個(gè)分支，B-tree?上每個(gè)節(jié)點(diǎn)有 k 個(gè)關(guān)鍵字和 (k + 1) 個(gè)分支。

二叉樹(shù)的查找只考慮向左還是向右走，而?B-tree?中需要由多個(gè)分支決定。

B-tree?的查找分兩步：

首先查找節(jié)點(diǎn)，由于?B-tree?通常是在磁盤(pán)上存儲(chǔ)的所以這步需要進(jìn)行磁盤(pán)IO操作；

查找關(guān)鍵字，當(dāng)找到某個(gè)節(jié)點(diǎn)后將該節(jié)點(diǎn)讀入內(nèi)存中然后通過(guò)順序或者折半查找來(lái)查找關(guān)鍵字。若沒(méi)有找到關(guān)鍵字，則需要判斷大小來(lái)找到合適的分支繼續(xù)查找。

操作流程

現(xiàn)在需要查找元素：88

第一次：磁盤(pán)IO

第二次：磁盤(pán)IO

第三次：磁盤(pán)IO

然后這有一次內(nèi)存比對(duì)，分別跟 70 與 88 比對(duì)，最后找到 88。

從查找過(guò)程中發(fā)現(xiàn)，B-tree?比對(duì)次數(shù)和磁盤(pán)IO的次數(shù)其實(shí)和二叉樹(shù)相差不了多少，這么看來(lái)并沒(méi)有什么優(yōu)勢(shì)。

但是仔細(xì)一看會(huì)發(fā)現(xiàn)，比對(duì)是在內(nèi)存中完成中，不涉及到磁盤(pán)IO，耗時(shí)可以忽略不計(jì)。

另外?B-tree?中一個(gè)節(jié)點(diǎn)中可以存放很多的關(guān)鍵字（個(gè)數(shù)由階決定），相同數(shù)量的關(guān)鍵字在?B-tree?中生成的節(jié)點(diǎn)要遠(yuǎn)遠(yuǎn)少于二叉樹(shù)中的節(jié)點(diǎn)，相差的節(jié)點(diǎn)數(shù)量就等同于磁盤(pán)IO的次數(shù)。這樣到達(dá)一定數(shù)量后，性能的差異就顯現(xiàn)出來(lái)了。

插入

當(dāng)?B-tree?要進(jìn)行插入關(guān)鍵字時(shí)，都是直接找到葉子節(jié)點(diǎn)進(jìn)行操作。

根據(jù)要插入的關(guān)鍵字查找到待插入的葉子節(jié)點(diǎn)；

因?yàn)橐粋€(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的最大個(gè)數(shù)（階）為 m，所以需要判斷當(dāng)前節(jié)點(diǎn)關(guān)鍵字的個(gè)數(shù)是否小于 (m - 1)。

是：直接插入

否：發(fā)生節(jié)點(diǎn)分裂，以節(jié)點(diǎn)的中間的關(guān)鍵字將該節(jié)點(diǎn)分為左右兩部分，中間的關(guān)鍵字放到父節(jié)點(diǎn)中即可。

操作流程

比如我們現(xiàn)在需要在 Max Degree（階）為 3 的?B-tree插入元素：72

查找待插入的葉子節(jié)點(diǎn)

節(jié)點(diǎn)分裂：本來(lái)應(yīng)該和 [70,88] 在同一個(gè)磁盤(pán)塊上，但是當(dāng)一個(gè)節(jié)點(diǎn)有 3 個(gè)關(guān)鍵字的時(shí)候，它就有可能有 4 個(gè)子節(jié)點(diǎn)，就超過(guò)了我們所定義限制的最大度數(shù) 3，所以此時(shí)必須進(jìn)行分裂：以中間關(guān)鍵字為界將節(jié)點(diǎn)一分為二，產(chǎn)生一個(gè)新節(jié)點(diǎn)，并把中間關(guān)鍵字上移到父節(jié)點(diǎn)中。

Tip?: 當(dāng)中間關(guān)鍵字有兩個(gè)時(shí)，通常將左關(guān)鍵字進(jìn)行上移分裂。

刪除

刪除操作就會(huì)比查找和插入要麻煩一些，因?yàn)橐粍h除的關(guān)鍵字可能在葉子節(jié)點(diǎn)上，也可能不在，而且刪除后還可能導(dǎo)致?B-tree?的不平衡，又要進(jìn)行合并、旋轉(zhuǎn)等操作去保持整棵樹(shù)的平衡。

隨便拿棵樹(shù)（5 階）舉例子

情況一：直接刪除葉子節(jié)點(diǎn)的元素

刪除目標(biāo)：50

查找元素 50 位置

在 [36, 50, 63] 節(jié)點(diǎn)移除 50 后，依然符合?B-tree?對(duì)節(jié)點(diǎn)內(nèi)關(guān)鍵字的要求：

┌m/2┐?-?1?≤?關(guān)鍵字個(gè)數(shù)?≤?m?-?1

┌5/2┐?-?1?≤?3?-?1?≤?5?-?1

2?≤?2?≤?4?

?

?

刪除完成

情況二：刪除葉子節(jié)點(diǎn)的元素后合并+旋轉(zhuǎn)

刪除目標(biāo)：11

查找元素 11 位置

在 [10, 11] 節(jié)點(diǎn)移除 11 后，違背?B-tree?對(duì)節(jié)點(diǎn)內(nèi)關(guān)鍵字的要求：

?

?

┌m/2┐?-?1?≤?關(guān)鍵字個(gè)數(shù)?≤?m?-?1

┌5/2┐?-?1?≤?2?-?1?≤?5?-?1

2?≤?1?≤?4?

?

?

在它只剩1個(gè)關(guān)鍵字后，需要向兄弟節(jié)點(diǎn)借元素，這時(shí)候右兄弟有多的，它說(shuō)：我愿意把14借給你

但不可能讓11和14放一起，因?yàn)?14 > 12?，這時(shí)候就要進(jìn)行旋轉(zhuǎn)~

首先，將父節(jié)點(diǎn)的元素 12 移到該節(jié)點(diǎn)，然后 12 就讓位給14

這整個(gè)過(guò)程就是刪除葉子節(jié)點(diǎn)元素后的合并、旋轉(zhuǎn)操作

下面再來(lái)道菜

接著刪除 10

在 [10, 12] 節(jié)點(diǎn)移除 10 后，違背?B-tree?對(duì)節(jié)點(diǎn)內(nèi)關(guān)鍵字的要求

在它只剩1個(gè)關(guān)鍵字后，需要向兄弟節(jié)點(diǎn)借元素，這時(shí)候沒(méi)有兄弟有多的該怎么辦呢

首先，將父節(jié)點(diǎn)的元素 8 移到該節(jié)點(diǎn)，這時(shí)候 3、6、8、12 都小于14，就先把它們放一起

結(jié)果又發(fā)現(xiàn)父節(jié)點(diǎn)只剩個(gè)14了，它又違背了?B-tree?對(duì)節(jié)點(diǎn)內(nèi)關(guān)鍵字的要求，接著造?。?！

首先，還是將父節(jié)點(diǎn)的元素 20 移到該節(jié)點(diǎn)，這時(shí)候根節(jié)點(diǎn)都直接沒(méi)了，直接合并 14、20、26、72 關(guān)鍵字

在這整個(gè)過(guò)程包括刪除葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)的合并、旋轉(zhuǎn)操作

情況三：刪除非葉子節(jié)點(diǎn)的元素后合并+旋轉(zhuǎn)

刪除目標(biāo)：12

查找元素 12 位置

移除 12 后，違背?B-tree?對(duì)節(jié)點(diǎn)內(nèi)關(guān)鍵字的要求

對(duì)于非葉子節(jié)點(diǎn)元素的刪除，我們需要用后繼元素覆蓋要被刪除的元素，然后在后繼元素所在的葉子中刪除該后繼元素。

小總結(jié)

“

B-tree 主要用于文件系統(tǒng)以及部分?jǐn)?shù)據(jù)庫(kù)索引，例如：MongoDB。

從查找效率考慮一般要求 B-tree 的階數(shù) m ≥ 3

B-tree 上算法的執(zhí)行時(shí)間主要由讀、寫(xiě)磁盤(pán)的次數(shù)來(lái)決定，故一次I/O操作應(yīng)讀寫(xiě)盡可能多的信息。

因此 B-tree 的節(jié)點(diǎn)規(guī)模一般以一個(gè)磁盤(pán)頁(yè)為單位。一個(gè)結(jié)點(diǎn)包含的關(guān)鍵字及其孩子個(gè)數(shù)取決于磁盤(pán)頁(yè)的大小。

”

B+tree

上面這些例子相信大家對(duì)?B-tree?已經(jīng)有一定了解了，而?MySQL?底層用的索引數(shù)據(jù)結(jié)構(gòu)正是在?B-tree?上面做了一些改造，變成了?B+tree。

B+tree?和?B-tree?區(qū)別：

所有的子節(jié)點(diǎn)，一定會(huì)出現(xiàn)在葉子節(jié)點(diǎn)上

相鄰的葉子節(jié)點(diǎn)之間，會(huì)用一個(gè)雙向鏈表連接起來(lái)（關(guān)鍵）

非葉子節(jié)點(diǎn)只存儲(chǔ)索引，不存儲(chǔ)數(shù)據(jù)，就為放更多索引

相比?B-tree?來(lái)說(shuō)，進(jìn)行范圍查找時(shí)只需要查找兩個(gè)節(jié)點(diǎn)，進(jìn)行遍歷就行。而?B-tree?需要獲取所有節(jié)點(diǎn)，相比之下?B+tree?效率更高。

這里其實(shí)這個(gè)數(shù)據(jù)結(jié)構(gòu)可視化網(wǎng)頁(yè)畫(huà)的?B+tree?還是不夠清晰，只是畫(huà)了個(gè)大概，下面我們就來(lái)看看它底層實(shí)際具體的數(shù)據(jù)結(jié)構(gòu)

每個(gè)節(jié)點(diǎn)都被稱(chēng)作一個(gè)磁盤(pán)頁(yè)

B+tree 的葉子節(jié)點(diǎn)包含所有索引數(shù)據(jù)，在非葉子節(jié)點(diǎn)會(huì)存儲(chǔ)不存儲(chǔ)數(shù)據(jù)，只存儲(chǔ)索引，從而來(lái)組成一棵 B+tree。

查找

B+tree?最大的優(yōu)勢(shì)就在查找上，主要是范圍查詢(xún)更加明顯。

“

B-tree 節(jié)點(diǎn)中的每個(gè)關(guān)鍵字都有數(shù)據(jù)，而 B+tree 中間節(jié)點(diǎn)沒(méi)有數(shù)據(jù)，只有索引；這就意味著相同大小的磁盤(pán)頁(yè)可以放更多的節(jié)點(diǎn)元素，也就是在相同的數(shù)據(jù)量下，I/O 操作更少

在范圍查詢(xún)上，B-tree 需要先找到指定范圍內(nèi)的下限，再找到上限，有了這兩個(gè)過(guò)程后再取出它們之間的元素。

B+tree 因?yàn)槿~子節(jié)點(diǎn)通過(guò)雙向鏈表進(jìn)行連接，找到指定范圍內(nèi)的下限后，直接通過(guò)鏈表順序遍歷就行，這樣就方便很多了。

”

在查詢(xún)單個(gè)關(guān)鍵字上，和?B-tree?差不多：先把通過(guò)磁盤(pán) I/O 找到節(jié)點(diǎn)，再把節(jié)點(diǎn)加載到內(nèi)存中進(jìn)行內(nèi)部關(guān)鍵字比對(duì)，然后通過(guò)大小關(guān)系再?zèng)Q定接下來(lái)走哪個(gè)分支。

但是差別就在于?B+tree?的高度更加可控一些。MySQL?默認(rèn)給一個(gè)磁盤(pán)頁(yè)數(shù)據(jù)分配的大小是?16KB，也就是 16 × 1024 = 16384 字節(jié)

官網(wǎng)說(shuō)明：https://dev.mysql.com/doc/refman/5.7/en/innodb-physical-structure.html

證明：直接在數(shù)據(jù)庫(kù)中通過(guò)?SQL?語(yǔ)句?show GLOBAL STATUS LIKE 'INNODB_page_size'進(jìn)行驗(yàn)證

當(dāng)我們的葉子節(jié)點(diǎn)全部撐滿(mǎn)之后，可以來(lái)算一算它樹(shù)的高度。

我們拿阿里的《Java 開(kāi)發(fā)手冊(cè)》嵩山版中對(duì)表主鍵的要求進(jìn)行舉例

bigint?大概占?8Byte，索引旁邊放指向下一節(jié)點(diǎn)的磁盤(pán)文件地址那塊是6Byte，是?MySQL?底層寫(xiě)死了的。

通過(guò)計(jì)算：16384 Byte / (8+6) Byte ≈ 1170，也就是說(shuō)一個(gè)節(jié)點(diǎn)設(shè)置?16KB?大小的話可以放 1170個(gè)索引。

葉子節(jié)點(diǎn)一個(gè)關(guān)鍵字占用1KB時(shí)，那一個(gè)節(jié)點(diǎn)就可以放16個(gè)元素，當(dāng)整棵樹(shù)葉子節(jié)點(diǎn)全部都被撐滿(mǎn)時(shí)，通過(guò)計(jì)算?1170 × 1170 × 16 = 21902400

最后結(jié)果為2千多萬(wàn)，樹(shù)的高度才為3，也就是我們要的高度可控。這也就是為什么?MySQL?的表有上千萬(wàn)數(shù)據(jù)的情況下，查詢(xún)效率依然快的原因。

插入

插入還是挺簡(jiǎn)單的：當(dāng)節(jié)點(diǎn)內(nèi)元素?cái)?shù)量大于 (m-1) 時(shí)，按中間元素分裂成左右兩部分，中間元素分裂到父節(jié)點(diǎn)當(dāng)做索引存儲(chǔ)，本身中間元素也還會(huì)分裂右邊這一部分的。

下面以5階(m)舉

操作流程

第一次在空樹(shù)中插入 1

再依次插入 2,3,4

插入 5

當(dāng)插入關(guān)鍵字 5 時(shí)，此時(shí)節(jié)點(diǎn)內(nèi)元素?cái)?shù)量大于 (5-1) ，即超過(guò)了4個(gè)，這時(shí)候就要進(jìn)行分裂；

以中間元素分裂，中間元素分裂到父節(jié)點(diǎn)當(dāng)做索引存儲(chǔ)，由于葉子節(jié)點(diǎn)包含所有索引數(shù)據(jù)，所以本身它還會(huì)分裂至右邊部分。

這個(gè)過(guò)程是在葉子節(jié)點(diǎn)上進(jìn)行分裂操作

下面再來(lái)個(gè)插入后的非葉子節(jié)點(diǎn)分裂操作（大差不差）

在以下的基礎(chǔ)上插入關(guān)鍵字：13

關(guān)鍵字13 插入到 [9, 10, 11, 12, 13] 后節(jié)點(diǎn)內(nèi)元素?cái)?shù)量超過(guò)了4個(gè)，準(zhǔn)備進(jìn)行分裂；

以中間元素(11)分裂，中間元素分裂到父節(jié)點(diǎn)當(dāng)做索引存儲(chǔ)，本身它也還會(huì)分裂右邊部分。

關(guān)鍵字11 被挪到父節(jié)點(diǎn)去之后，節(jié)點(diǎn)內(nèi)元素?cái)?shù)量超過(guò)了4個(gè)，又要準(zhǔn)備進(jìn)行分裂

以中間元素(7)分裂，中間元素分裂到父節(jié)點(diǎn)當(dāng)做（冗余）索引存儲(chǔ)。

插入完畢

刪除

在對(duì)應(yīng)節(jié)點(diǎn)刪除目標(biāo)關(guān)鍵字后，一樣需要看看節(jié)點(diǎn)內(nèi)剩余關(guān)鍵字是否符合：?- 1 ≤ 關(guān)鍵字個(gè)數(shù) ≤ m - 1

符合直接刪除就行，不符合就和?B-tree?一樣需要向兄弟節(jié)點(diǎn)借元素，不過(guò)會(huì)比?B-tree?稍簡(jiǎn)單一點(diǎn)點(diǎn)

因?yàn)槿~子節(jié)點(diǎn)（雙向鏈表）之間有指針關(guān)聯(lián)著，可以不需要再找它們的父節(jié)點(diǎn)了，直接通過(guò)兄弟節(jié)點(diǎn)進(jìn)行移動(dòng)，然后再更新父節(jié)點(diǎn)；

如果兄弟節(jié)點(diǎn)內(nèi)元素沒(méi)有多余的關(guān)鍵字，那就直接將當(dāng)前節(jié)點(diǎn)和兄弟節(jié)點(diǎn)合并，再刪除父節(jié)點(diǎn)中的關(guān)鍵字。

操作流程

目標(biāo)刪除元素：14

刪除 14 關(guān)鍵字后，它所在的節(jié)點(diǎn)只剩 13 一個(gè)關(guān)鍵字了

?

?

┌m/2┐?-?1?≤?關(guān)鍵字個(gè)數(shù)?≤?m?-?1

┌5/2┐?-?1?≤?2?-?1?≤?5?-?1

2?≤?1?≤?4?

?

?

準(zhǔn)備借元素！

直接通過(guò)右兄弟節(jié)點(diǎn)（只有它有富余）進(jìn)行移動(dòng)，然后再更新父節(jié)點(diǎn)的索引

刪除成功后

接著刪除元素：16

刪除 16 關(guān)鍵字后，它所在的節(jié)點(diǎn)只剩 17 一個(gè)關(guān)鍵字了，又要準(zhǔn)備借元素；

這時(shí)候兄弟節(jié)點(diǎn)都沒(méi)有多的，就直接把它和兄弟節(jié)點(diǎn)合并，再刪除父節(jié)點(diǎn)中的關(guān)鍵字

合并關(guān)鍵字 [13, 15, 17] ，在刪除父節(jié)點(diǎn)中的關(guān)鍵字 16

刪除成功后

總 結(jié)

“

單個(gè)節(jié)點(diǎn)存儲(chǔ)越多的元素，自然在整個(gè)過(guò)程中的磁盤(pán)I/O交互就越少；

相對(duì) B-tree 來(lái)說(shuō)，所有的查詢(xún)最終都會(huì)找到葉子節(jié)點(diǎn)，這也是 B+tree 性能穩(wěn)定的一個(gè)體現(xiàn)；

所有葉子節(jié)點(diǎn)通過(guò)雙向鏈表相連，范圍查詢(xún)非常方便，這也是 B+tree 最明顯的優(yōu)勢(shì)。

”

編輯：黃飛

?