摘要： B 樹是一種被設計成專門存儲在磁盤上的平衡查找樹。因為磁盤的操作速度要大大慢于隨機存取存儲器，所以在分析B 樹的性能時，不僅要看動態集合操作花了多少計算時間，還要看執行了多少次磁盤存儲操作。 B 樹與紅黑樹（下一篇介紹）類似，但在降低磁盤I/O 操作次數方面要更好一些。許多數據庫系統就使用 B 樹或 B 樹的變形來存儲信息，想象一下一棵每個節點包含 1001 個 key 的高度為 2 的 B 樹能容納多少數據啊，而在內存中我們只存儲了一個節點，在需要的時候再從磁盤中讀取所需的節點。 閱讀全文