什麼是 B+ Tree

上一篇學習 什麼是 B-Tree 這篇就來補 B+ Tree 囉

B+ Tree 特徵

• 每個葉子節點都帶有指向下一個節點的指針，形成有序鏈表，加速範圍查詢
• 只有葉子節點帶衛星數據，父節點只帶關鍵字與指針，單一節點更省空間，讓查詢 I/O 變小
• 所有查詢都會查到葉子節點，查詢性能穩定

B+ Tree 更加矮胖

B+ Tree 中的內部節點，只存放關鍵字與子節點的指針，不存其他的 Satellite Information，因此最大化了內部節點的分支因子，所以說以同樣大小的硬碟分頁可以容納更多的節點元素。

換句話說，以數據量相同的情況下， B+ Tree 會比 B-Tree 來的更加矮胖，有效的節省硬碟 I/O 次數。

比對 B-Tree 和 B+Tree 中的 Satellite Information

B-Tree

B+Tree

可以從第三層的葉子節點發現，每個節點的最右邊也就是最大的元素都是母節點的元素

範圍查詢效率更佳

先來看一下 B-Tree 的範圍查詢，以範例要找到 3 至 11 的元素，遍歷過程如下：

反觀 B+ Tree 的範圍查詢就更簡單快速了，只要在最後的葉節點掃描有序鏈表就可以找到了。

參考來源

• 漫画：什么是 B+ 树？
  好文轉自作者Nic Lin’s Blog–喜歡在地上打滾的 Rails Developer
  如果你喜歡他的文章，歡迎回到他的部落格觀看更多:)12/4 晚上由他擔任分享者的小聚活動，開放早鳥報名中，活動資訊請看下方連結：
  學程式主題小聚 x Devstars Lighthouse｜2個月擁有6000用戶，SideProject這樣做｜Nic