我們?cè)?a target="_blank">MySQL中的數(shù)據(jù)一般是放在磁盤中的尤蛮，讀取數(shù)據(jù)的時(shí)候肯定會(huì)有訪問(wèn)磁盤的操作，磁盤中有兩個(gè)機(jī)械運(yùn)動(dòng)的部分笙蒙，分別是盤片旋轉(zhuǎn)和磁臂移動(dòng)。盤片旋轉(zhuǎn)就是我們市面上所提到的多少轉(zhuǎn)每分鐘庆锦，而磁盤移動(dòng)則是在盤片旋轉(zhuǎn)到指定位置以后捅位，移動(dòng)磁臂后開始進(jìn)行數(shù)據(jù)的讀寫。那么這就存在一個(gè)定位到磁盤中的塊的過(guò)程搂抒，而定位是磁盤的存取中花費(fèi)時(shí)間比較大的一塊艇搀，畢竟機(jī)械運(yùn)動(dòng)花費(fèi)的時(shí)候要遠(yuǎn)遠(yuǎn)大于電子運(yùn)動(dòng)的時(shí)間。當(dāng)大規(guī)模數(shù)據(jù)存儲(chǔ)到磁盤中的時(shí)候求晶，顯然定位是一個(gè)非逞娴瘢花費(fèi)時(shí)間的過(guò)程，但是我們可以通過(guò)B樹進(jìn)行優(yōu)化芳杏，提高磁盤讀取時(shí)定位的效率矩屁。

為什么B類樹可以進(jìn)行優(yōu)化呢？我們可以根據(jù)B類樹的特點(diǎn)爵赵，構(gòu)造一個(gè)多階的B類樹吝秕，然后在盡量多的在結(jié)點(diǎn)上存儲(chǔ)相關(guān)的信息，保證層數(shù)（樹的高度）盡量的少空幻，以便后面我們可以更快的找到信息烁峭，磁盤的I/O操作也少一些，而且B類樹是平衡樹秕铛，每個(gè)結(jié)點(diǎn)到葉子結(jié)點(diǎn)的高度都是相同约郁，這也保證了每個(gè)查詢是穩(wěn)定的。

特別地：只有B-樹和B+樹但两，這里的B-樹是叫B樹鬓梅，不是B減樹。沒(méi)有B減樹的谨湘。

以下摘自【程序員小灰】

什么是B樹

一個(gè)m階的B樹具有如下幾個(gè)特征：

1姥宝、根結(jié)點(diǎn)至少有兩個(gè)子女。 2凳忙、每個(gè)中間節(jié)點(diǎn)都包含k-1個(gè)元素和k個(gè)孩子氧急，其中 m/2 <= k <= m 3、每一個(gè)葉子節(jié)點(diǎn)都包含k-1個(gè)元素欧募，其中 m/2 <= k <= m 4、所有的葉子結(jié)點(diǎn)都位于同一層。5赤拒、每個(gè)節(jié)點(diǎn)中的元素從小到大排列，節(jié)點(diǎn)當(dāng)中k-1個(gè)元素正好是k個(gè)孩子包含的元素的值域分劃诱鞠。

下面以3階B樹開始學(xué)習(xí)

這棵樹中挎挖，重點(diǎn)看（2,6）節(jié)點(diǎn)。該節(jié)點(diǎn)有兩個(gè)元素2和6航夺，又有三個(gè)孩子1蕉朵，（3,5），8阳掐。其中1小于元素2始衅，（3,5）在（2，6）之間缭保，8大于（3,5）汛闸，正好符合上面所列的特征。

B樹查詢的流程：

比如上面的3階B樹查詢數(shù)值5艺骂。

第1次IO:

第2次IO:

第3次IO:

第3次內(nèi)存比較:

總結(jié)：每次深度加1就會(huì)進(jìn)行一次磁盤IO的查詢诸老，將當(dāng)前高度的數(shù)據(jù)加到內(nèi)存中，再進(jìn)行數(shù)值比較钳恕。從中可以看出相比大部分的查詢時(shí)間是花費(fèi)在磁盤IO的速度上别伏，所以要想提高性能就是將樹的高度足夠低，IO次數(shù)足夠少忧额，這就是B樹的優(yōu)勢(shì)畸肆。

B樹添加的流程：

比如樹里添加數(shù)值4 自頂向下查找4的節(jié)點(diǎn)位置，發(fā)現(xiàn)4應(yīng)當(dāng)插入到節(jié)點(diǎn)元素3宙址，5之間

節(jié)點(diǎn)3轴脐，5已經(jīng)是兩元素節(jié)點(diǎn)，無(wú)法再增加抡砂。父親節(jié)點(diǎn) 2大咱， 6 也是兩元素節(jié)點(diǎn)，也無(wú)法再增加注益。根節(jié)點(diǎn)9是單元素節(jié)點(diǎn)碴巾，可以升級(jí)為兩元素節(jié)點(diǎn)。于是拆分節(jié)點(diǎn)3丑搔，5與節(jié)點(diǎn)2厦瓢，6提揍，讓根節(jié)點(diǎn)9升級(jí)為兩元素節(jié)點(diǎn)4，9煮仇。節(jié)點(diǎn)6獨(dú)立為根節(jié)點(diǎn)的第二個(gè)孩子劳跃。

從圖中可以看到，為了插入一個(gè)元素浙垫，幾乎全部的位置都變化了刨仑，這就是B樹的自平衡（始終維持多路平衡）。

B樹刪除的流程：

自頂向下查找元素11的節(jié)點(diǎn)位置夹姥。

刪除11后杉武，節(jié)點(diǎn)12只有一個(gè)孩子，不符合B樹規(guī)范辙售。因此找出12,13,15三個(gè)節(jié)點(diǎn)的中位數(shù)13轻抱，取代節(jié)點(diǎn)12，而節(jié)點(diǎn)12自身下移成為第一個(gè)孩子旦部。（這個(gè)過(guò)程稱為左旋）

B樹應(yīng)用

主要用于文件系統(tǒng)以及部分?jǐn)?shù)據(jù)庫(kù)索引（MongoDB） 而Mysql是用B+樹的祈搜。

什么是B+樹

一個(gè)m階的B+樹具有如下幾個(gè)特征：

1、有k個(gè)子樹的中間節(jié)點(diǎn)包含有k個(gè)元素（B樹中是k-1個(gè)元素）志鹃，每個(gè)元素不保存數(shù)據(jù)夭问，只用來(lái)索引泽西，所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)曹铃。 2、所有的葉子結(jié)點(diǎn)中包含了全部元素的信息捧杉，及指向含這些元素記錄的指針陕见，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。 3味抖、所有的中間節(jié)點(diǎn)元素都同時(shí)存在于子節(jié)點(diǎn)评甜，在子節(jié)點(diǎn)元素中是最大（或最小）元素仔涩。

從上圖可以發(fā)現(xiàn)每一個(gè)父節(jié)點(diǎn)的元素都出現(xiàn)在子節(jié)點(diǎn)中忍坷，并且是子節(jié)點(diǎn)的最大（或最小）

從圖中可以看到根節(jié)點(diǎn)元素8是字節(jié)點(diǎn)2,5,8的最大元素熔脂，也是葉子節(jié)點(diǎn)6佩研，8的最大元素。根節(jié)點(diǎn)15是子節(jié)點(diǎn)11,15的最大元素霞揉，也是葉子節(jié)點(diǎn)13,15的最大元素旬薯。

B+樹的最大元素始終位于根節(jié)點(diǎn)當(dāng)中。所有葉子節(jié)點(diǎn)包含了全量元素信息适秩，并且每一個(gè)葉子節(jié)點(diǎn)都帶有指向 下一個(gè)節(jié)點(diǎn)指針绊序，形成了一個(gè)有序鏈表硕舆。

B+樹查詢流程

單個(gè)查詢：查詢某個(gè)元素3

第一次磁盤IO：

第二次磁盤IO：

第三次磁盤IO：

這樣看起來(lái)跟B樹沒(méi)有什么區(qū)別。但其實(shí)有兩點(diǎn)是需要注意的：

1骤公、B+樹的中間節(jié)點(diǎn)沒(méi)有衛(wèi)星數(shù)據(jù)的抚官。所以同樣大小的磁盤頁(yè)可以容納更多的節(jié)點(diǎn)元素。（這就意味著B+會(huì)更加矮胖淋样，查詢的IO次數(shù)會(huì)更少）

B樹的衛(wèi)星數(shù)據(jù)

B+樹的衛(wèi)星數(shù)據(jù)

2耗式、B樹查找性能是不穩(wěn)定的（如果要查找的數(shù)據(jù)分別在根節(jié)點(diǎn)和葉子節(jié)點(diǎn)，他們的性能就會(huì)不同）趁猴。但B+樹的每一次都是穩(wěn)定的刊咳，為啥呢，看下面的范圍查詢儡司。

范圍查詢：查找到范圍的下限（3）

B樹的范圍查詢：

自頂向下娱挨，查找到范圍的下限（3），最多6條：

中序遍歷到元素6：

中序遍歷到元素8：

中序遍歷到元素9：

中序遍歷到元素11捕犬，遍歷結(jié)束：

B+樹的范圍查詢：

自頂向下跷坝，查找到范圍的下限（3），最多6條：

通過(guò)鏈表指針碉碉，遍歷到元素6, 8：

通過(guò)鏈表指針柴钻，遍歷到元素9, 11，遍歷結(jié)束：

從上面的流程比較垢粮，可以得出以下B+樹的優(yōu)勢(shì)：

1.單一節(jié)點(diǎn)存儲(chǔ)更多的元素贴届，使得查詢的IO次數(shù)更少。

2.所有查詢都要查找到葉子節(jié)點(diǎn)蜡吧，查詢性能穩(wěn)定毫蚓。

3.所有葉子節(jié)點(diǎn)形成有序鏈表，便于范圍查詢昔善。

面試題

問(wèn)題1：MySQL中存儲(chǔ)索引用到的數(shù)據(jù)結(jié)構(gòu)是B+樹元潘，B+樹的查詢時(shí)間跟樹的高度有關(guān)，是log(n)君仆，如果用hash存儲(chǔ)翩概，那么查詢時(shí)間是O(1)。既然hash比B+樹更快返咱，為什么mysql用B+樹來(lái)存儲(chǔ)索引呢钥庇？

答：一、從內(nèi)存角度上說(shuō)洛姑，數(shù)據(jù)庫(kù)中的索引一般時(shí)在磁盤上上沐，數(shù)據(jù)量大的情況可能無(wú)法一次性裝入內(nèi)存，B+樹的設(shè)計(jì)可以允許數(shù)據(jù)分批加載楞艾。

二参咙、從業(yè)務(wù)場(chǎng)景上說(shuō)龄广，如果只選擇一個(gè)數(shù)據(jù)那確實(shí)是hash更快，但是數(shù)據(jù)庫(kù)中經(jīng)常會(huì)選中多條這時(shí)候由于B+樹索引有序蕴侧，并且又有鏈表相連择同，它的查詢效率比hash就快很多了。

問(wèn)題2：為什么不用紅黑樹或者二叉排序樹净宵？

答：樹的查詢時(shí)間跟樹的高度有關(guān)敲才，B+樹是一棵多路搜索樹可以降低樹的高度，提高查找效率

問(wèn)題3：既然增加樹的路數(shù)可以降低樹的高度择葡，那么無(wú)限增加樹的路數(shù)是不是可以有最優(yōu)的查找效率紧武？

答：這樣會(huì)形成一個(gè)有序數(shù)組，文件系統(tǒng)和數(shù)據(jù)庫(kù)的索引都是存在硬盤上的敏储，并且如果數(shù)據(jù)量大的話阻星，不一定能一次性加載到內(nèi)存中。有序數(shù)組沒(méi)法一次性加載進(jìn)內(nèi)存已添，這時(shí)候B+樹的多路存儲(chǔ)威力就出來(lái)了妥箕，可以每次加載B+樹的一個(gè)結(jié)點(diǎn)，然后一步步往下找更舞，

問(wèn)題4：在內(nèi)存中畦幢，紅黑樹比B樹更優(yōu)，但是涉及到磁盤操作B樹就更優(yōu)了缆蝉，那么你能講講B+樹嗎宇葱？

B+樹是在B樹的基礎(chǔ)上進(jìn)行改造，它的數(shù)據(jù)都在葉子結(jié)點(diǎn)返奉，同時(shí)葉子結(jié)點(diǎn)之間還加了指針形成鏈表贝搁。

下面是一個(gè)4路B+樹吗氏，它的數(shù)據(jù)都在葉子結(jié)點(diǎn)芽偏，并且有鏈表相連。

問(wèn)題5：為什么B+樹要這樣設(shè)計(jì)弦讽？

答：這個(gè)跟它的使用場(chǎng)景有關(guān)污尉，B+樹在數(shù)據(jù)庫(kù)的索引中用得比較多，數(shù)據(jù)庫(kù)中select數(shù)據(jù)往产，不一定只選一條被碗，很多時(shí)候會(huì)選中多條，比如按照id進(jìn)行排序后選100條仿村。如果是多條的話锐朴，B+樹需要做局部的中序遍歷，可能要跨層訪問(wèn)蔼囊。而B+樹由于所有數(shù)據(jù)都在葉子結(jié)點(diǎn)不用跨層焚志，同時(shí)由于有鏈表結(jié)構(gòu)衣迷，只需要找到首尾，通過(guò)鏈表就能把所有數(shù)據(jù)取出來(lái)了酱酬。

比如選出7到19只需要在葉子結(jié)點(diǎn)中就能找到壶谒。

數(shù)據(jù)庫(kù)索引為什么要用 B+ 樹而不用紅黑樹呢？

AVL 樹和紅黑樹這些二叉樹結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)可以達(dá)到最高的查詢效率這是毋庸置疑的膳沽。

既然如此汗菜，那么數(shù)據(jù)庫(kù)索引為什么不用 AVL 樹或者紅黑樹呢？

這就牽扯到一個(gè)問(wèn)題了挑社，不考慮每種數(shù)據(jù)結(jié)構(gòu)的前提條件而選擇數(shù)據(jù)結(jié)構(gòu)都是在耍流氓陨界。

AVL 數(shù)和紅黑樹基本都是存儲(chǔ)在內(nèi)存中才會(huì)使用的數(shù)據(jù)結(jié)構(gòu)，那磁盤中會(huì)有什么不同呢痛阻？

這就要牽扯到磁盤的存儲(chǔ)原理了

操作系統(tǒng)讀寫磁盤的基本單位是扇區(qū)普碎，而文件系統(tǒng)的基本單位是簇(Cluster)。

也就是說(shuō)录平，磁盤讀寫有一個(gè)最少內(nèi)容的限制麻车，即使我們只需要這個(gè)簇上的一個(gè)字節(jié)的內(nèi)容，我們也要含著淚把一整個(gè)簇上的內(nèi)容讀完斗这。

那么动猬，現(xiàn)在問(wèn)題就來(lái)了

一個(gè)父節(jié)點(diǎn)只有 2 個(gè)子節(jié)點(diǎn)，并不能填滿一個(gè)簇上的所有內(nèi)容氨砑赁咙？那多余的內(nèi)容豈不是要浪費(fèi)了？我們?cè)趺床拍馨牙速M(fèi)的這部分內(nèi)容利用起來(lái)呢免钻？哈哈彼水，答案就是 B+ 樹。

由于 B+ 樹分支比二叉樹更多极舔，所以相同數(shù)量的內(nèi)容凤覆，B+ 樹的深度更淺，深度代表什么拆魏？代表磁盤 io 次數(shù)岸㈣搿！數(shù)據(jù)庫(kù)設(shè)計(jì)的時(shí)候 B+ 樹有多少個(gè)分支都是按照磁盤一個(gè)簇上最多能放多少節(jié)點(diǎn)設(shè)計(jì)的安橙小拥峦！

所以，涉及到磁盤上查詢的數(shù)據(jù)結(jié)構(gòu)卖子，一般都用 B+ 樹啦略号。