[[403232]]

本文轉載自微信公眾號「架構精進之路」，作者架構精進之路。轉載本文請聯系架構精進之路公眾號。

寫在前面

前面一講我們介紹了B-樹的特性，以及與平衡二叉樹的對比得出B-樹這類數據結構的優勢。

《面試官：談談你對索引的認知》系列之B-樹

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

B+樹 簡介

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

從上圖B-樹的簡化圖，我們可以發現幾個顯著特點：

據只出現在葉子節點(非葉子節點并不存儲真正的 data)

所有葉子節點增加了一個鏈指針

B+樹 VS B-樹

1、數據實現結構不同，查詢復雜度不同

B+樹內節點不存儲數據，所有 data 存儲在葉節點導致查詢時間復雜度固定為 log n。而B-樹查詢時間復雜度不固定，與 key 在樹中的位置有關，最好為O(1)。

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

• B-樹

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

• B+樹

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

小結：

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

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

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

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

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

小結：

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

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

因為它內節點不存儲data，這樣一個節點就可以存儲更多的key。

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

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

小結：

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

總結

B-樹相對于B+樹的優點是，如果經常訪問的數據離根節點很近，而B樹的非葉子節點本身存有關鍵字其數據的地址，所以這種數據檢索的時候會要比B+樹快。

但是B+樹的優勢更加明顯：

• B+樹的層級更少

相較于B樹B+每個非葉子節點存儲的關鍵字數更多，樹的層級更少所以查詢數據更快;

• B+樹查詢速度更穩定

B+所有關鍵字數據地址都存在葉子節點上，所以每次查找的次數都相同所以查詢速度要比B樹更穩定;

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

B+樹所有的葉子節點數據構成了一個有序鏈表，在查詢大小區間的數據時候更方便，數據緊密性很高，緩存的命中率也會比B樹高。

• B+樹全節點遍歷更快

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