索引葉節點在磁碟上是任意順序存放的——實體位置與索引的邏輯順序毫無對應關係。這就像一本書頁被打亂的電話簿：你想找「Smith」，卻先翻到「Robinson」，完全不能保證 Smith 就在後面。

資料庫因此需要第二種結構，才能在這些「亂序的頁」中快速定位：平衡搜尋樹（balanced search tree），簡稱 B-tree。

B-tree 如何建構#

以一個含 30 個條目的索引為例：

• 雙向鏈結串列建立葉節點之間的邏輯順序。
• 根節點與分支節點則負責在葉節點之間快速搜尋。
• 每個分支節點的條目，對應其所指葉節點中的最大值。例如第一個葉節點的最大值是 46，分支節點的第一個條目就是 46；依此類推，該分支節點最終持有 46、53、57、83。
• 依此規則往上堆疊分支層，直到所有葉節點都被分支節點涵蓋。
• 下一層以同樣方式建在第一層分支節點之上，反覆進行，直到所有鍵值裝得進單一節點為止——那就是根節點。

之所以稱為「平衡」搜尋樹，是因為樹的深度在每個位置都相等：根節點到任一葉節點的距離處處相同。

B-tree 是平衡樹（balanced tree），不是二元樹（binary tree）。

索引一旦建立，資料庫就會自動維護它：每個 insert、delete、update 都會套用到索引上並維持樹的平衡，因此會為寫入操作帶來維護開銷。第 8 章「修改資料」會詳細說明。

樹的走訪#

走訪（tree traversal）從左側的根節點開始：

1. 依遞增順序逐一檢視條目，直到某個值大於或等於搜尋值（57）——圖中是條目 83。
2. 資料庫沿著該條目的參照走到對應的分支節點。
3. 重複同樣程序，直到走訪抵達葉節點。

B-tree 讓資料庫能夠快速找到葉節點。

樹的走訪是極有效率的操作——效率高到我稱它為索引的第一威力（the first power of indexing）。即使面對龐大的資料集，它幾乎是瞬時完成的。原因有二：

• 樹的平衡：存取任何元素所需的步數都相同。
• 樹深的對數成長：相較於葉節點數量，樹的深度成長得極為緩慢。現實世界中擁有數百萬筆記錄的索引，樹深也只有四或五層；深度六幾乎不曾見過。