B +樹優於BST？

Question

我正在學習有關數據庫的類中的B +樹，我想知道B +樹在二叉搜索樹上會給出什麼具體優勢？

看起來他們對於大多數操作都有O（logN）平均複雜度，但B +樹在每個子節點也有額外的（可忽略的？）搜索時間，其中BST顯然只需要O（1）取出哪個子節點前進。

真實世界的優點是什麼讓B +樹在數據庫中比BST更受歡迎？

Answer 1

B +樹（和一般B樹）在二分搜索樹上的主要優點是它們在緩存中表現良好。如果你有一個二叉搜索樹，其節點在內存中的存儲方式或多或少隨機，那麼你每次跟隨一個指針時，機器將不得不將一塊新的內存拉入到處理器緩存中，訪問已經在緩存中的內存。

B +樹和B樹通過讓每個節點存儲大量的鍵或值並且有大量的子元素來工作。它們通常以一種可以使單個節點很好地適應緩存的方式打包在一起（或者，如果存儲在磁盤上，則可以在單次讀取操作中從磁盤中取出）。然後，您必須做更多的工作才能在節點中找到一個鍵或確定下一個要讀取哪個子節點，但是因爲在單個節點上完成的所有內存訪問都可以在不返回到磁盤的情況下完成，所以訪問時間非常短。這意味着即使原則上BST在內存訪問的號碼方面可能更好，但是B +樹和B樹可以在那些存儲器訪問的方面更好地執行。

B +樹或B樹的典型用例是在一個數據庫中，其中存在大量的信息並且數據太多以致於無法將它們全部放入主內存中。因此，數據可以存儲在某個硬盤上的B +樹或B樹中。這最大限度地減少了在查找過程中拉入數據所需的磁盤讀取次數。有些文件系統（如ext4，我相信）也出於同樣的原因使用B-樹 - 它們將所需的磁盤查找數量降至最低，這是真正的瓶頸。

希望這會有所幫助！

Answer 2

數據的實際存儲（例如，在數據庫中）需要存儲大量數據。由於數據檢索是所關注的基本操作，從磁盤讀取數據比RAM更耗時。

現在，這是鎖釦...中的一個節點

BST存儲較少的數據相比，B +樹。這導致BST的高度比B +樹高。所以它們存儲在磁盤上而不是RAM中。每當數據必須從樹中檢索時，磁盤中的數據必須加載到主內存中（這當然是一個耗時的過程），而在B +樹的情況下，數據已經存在於RAM中，並且直接獲取所需的節點，並且從可能包含許多子節點的節點檢索數據（但是在B +樹的情況下數據檢索的總時間較少，因爲不需要從磁盤加載數據到RAM）。