Nic Lin's Blog

喜歡在地上打滾的 Rails Developer

什麼是 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 的範圍查詢就更簡單快速了,只要在最後的葉節點掃描有序鏈表就可以找到了。

參考來源

comments powered by Disqus