[[403232]]

本文轉(zhuǎn)載自微信公眾號「架構(gòu)精進之路」，作者架構(gòu)精進之路。轉(zhuǎn)載本文請聯(lián)系架構(gòu)精進之路公眾號。

寫在前面

前面一講我們介紹了B-樹的特性，以及與平衡二叉樹的對比得出B-樹這類數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢。

《面試官：談?wù)勀銓λ饕恼J(rèn)知》系列之B-樹

那B+樹作為B樹的一個升級版，那它又有哪些優(yōu)勢呢?本講繼續(xù)為大家揭開B+樹的神秘面紗，讓它不再成為你前進的羈絆!

B+樹 簡介

B+樹是B-樹的一個升級版，也是一種多路搜索樹，相對于B樹來說B+樹更充分的利用了節(jié)點的空間，讓查詢速度更加穩(wěn)定，其速度完全接近于二分法查找。

從上圖B-樹的簡化圖，我們可以發(fā)現(xiàn)幾個顯著特點：

據(jù)只出現(xiàn)在葉子節(jié)點(非葉子節(jié)點并不存儲真正的 data)

所有葉子節(jié)點增加了一個鏈指針

B+樹 VS B-樹

1、數(shù)據(jù)實現(xiàn)結(jié)構(gòu)不同，查詢復(fù)雜度不同

B+樹內(nèi)節(jié)點不存儲數(shù)據(jù)，所有 data 存儲在葉節(jié)點導(dǎo)致查詢時間復(fù)雜度固定為 log n。而B-樹查詢時間復(fù)雜度不固定，與 key 在樹中的位置有關(guān)，最好為O(1)。

如我們分別查詢B-樹/B+樹節(jié)點 key 為 50 的 data。

• B-樹

key 為 50 的節(jié)點恰好就在第一層，B-樹只需要一次磁盤 IO 即可完成查找。所以說B-樹的查詢最好時間復(fù)雜度是 O(1)。

• B+樹

由于B+樹所有的 data 域都在根節(jié)點，所以查詢 key 為 50的節(jié)點必須從根節(jié)點索引到葉節(jié)點，時間復(fù)雜度固定為 O(log n)。

小結(jié)：

B樹的由于每個節(jié)點都有key和data，所以查詢的時候可能不需要O(logn)的復(fù)雜度，甚至最好的情況是O(1)就可以找到數(shù)據(jù)，而B+樹由于只有葉子節(jié)點保存了data，所以必須經(jīng)歷O(logn)復(fù)雜度才能找到數(shù)據(jù)。

2、B+樹可以更好的利用局部性原理

B+樹葉節(jié)點兩兩相連可大大增加區(qū)間訪問性，可使用在范圍查詢等，而B-樹每個節(jié)點 key 和 data 在一起，則無法區(qū)間查找。

空間局部性原理：如果一個存儲器的某個位置被訪問，那么將它附近的位置也會被訪問。

若我們訪問節(jié)點 key為 50，則 key 為 55、60、62 的節(jié)點將來也可能被訪問，我們可以利用磁盤預(yù)讀原理提前將這些數(shù)據(jù)讀入內(nèi)存，減少了磁盤 IO 的次數(shù)。當(dāng)然B+樹也能夠很好的完成范圍查詢。比如查詢 key 值在 50-70 之間的節(jié)點。

小結(jié)：

由于B+樹的葉子節(jié)點的數(shù)據(jù)都是使用鏈表連接起來的，而且他們在磁盤里是順序存儲的，所以當(dāng)讀到某個值的時候，磁盤預(yù)讀原理就會提前把這些數(shù)據(jù)都讀進內(nèi)存，使得范圍查詢和排序都很快。

3、B+樹每個節(jié)點能索引的范圍更大更精確

因為它內(nèi)節(jié)點不存儲data，這樣一個節(jié)點就可以存儲更多的key。

由于B-樹節(jié)點內(nèi)部每個 key 都帶著 data 域，而B+樹節(jié)點只存儲 key 的副本，真實的 key 和 data 域都在葉子節(jié)點存儲。前面說過磁盤是分 block 的，一次磁盤 IO 會讀取若干個 block，具體和操作系統(tǒng)有關(guān)，那么由于磁盤 IO 數(shù)據(jù)大小是固定的，在一次 IO 中，單個元素越小，量就越大。這就意味著B+樹單次磁盤 IO 的信息量大于B-樹，從這點來看B+樹相對B-樹磁盤 IO 次數(shù)少。

從上圖可以看出相同大小的區(qū)域，B-樹僅有 2 個 key，而B+樹有 3 個 key。

小結(jié)：

由于B樹的節(jié)點都存了key和data，而B+樹只有葉子節(jié)點存data，非葉子節(jié)點都只是索引值，沒有實際的數(shù)據(jù)，這就時B+樹在一次IO里面，能讀出的索引值更多。從而減少查詢時候需要的IO次數(shù)!

總結(jié)

B-樹相對于B+樹的優(yōu)點是，如果經(jīng)常訪問的數(shù)據(jù)離根節(jié)點很近，而B樹的非葉子節(jié)點本身存有關(guān)鍵字其數(shù)據(jù)的地址，所以這種數(shù)據(jù)檢索的時候會要比B+樹快。

但是B+樹的優(yōu)勢更加明顯：

• B+樹的層級更少

相較于B樹B+每個非葉子節(jié)點存儲的關(guān)鍵字?jǐn)?shù)更多，樹的層級更少所以查詢數(shù)據(jù)更快;

• B+樹查詢速度更穩(wěn)定

B+所有關(guān)鍵字?jǐn)?shù)據(jù)地址都存在葉子節(jié)點上，所以每次查找的次數(shù)都相同所以查詢速度要比B樹更穩(wěn)定;

• B+樹天然具備排序功能

B+樹所有的葉子節(jié)點數(shù)據(jù)構(gòu)成了一個有序鏈表，在查詢大小區(qū)間的數(shù)據(jù)時候更方便，數(shù)據(jù)緊密性很高，緩存的命中率也會比B樹高。

• B+樹全節(jié)點遍歷更快

B+樹遍歷整棵樹只需要遍歷所有的葉子節(jié)點即可，而不需要像B樹一樣需要對每一層進行遍歷，這有利于數(shù)據(jù)庫做全表掃描。