面試官：談談你對索引的認知系列之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樹一樣需要對每一層進行遍歷，這有利于數據庫做全表掃描。
