當我們談論數據庫索引時，選擇合適的數據結構至關重要。不同的數據結構在性能、復雜度以及適用場景上都有所不同。本文將通過對比二叉樹、紅黑樹和B樹，探討它們如何影響數據庫索引的表現。

一、二叉樹

特性

• 定義：每個節點最多有兩個子節點。
• 應用場景：適合于小規模或靜態數據集的快速查找。

缺點

如果使用自增ID作為索引鍵值構建二叉查找樹（BST），隨著數據量的增長，特別是當插入順序是遞增或遞減時，這棵樹會退化成鏈表形式。在這種情況下，查找效率會降至O(n)，并且每次查找都會觸發一次磁盤IO操作，這對于大型數據庫來說是非常不利的。

二、紅黑樹

特性

• 定義：紅黑樹是一種自平衡二叉搜索樹，通過特定規則保持樹的近似平衡，確保最壞情況下的時間復雜度為O(log n)。
• 優點：即使在頻繁更新的情況下也能維持較高的查找效率。

局限性

盡管紅黑樹解決了二叉查找樹可能退化的問題，但由于其本質仍然是二叉樹，在大數據量下樹的高度仍然較高，導致查詢路徑較長。此外，維護平衡狀態需要額外的操作，增加了實現的復雜性。

三、B樹?：面向磁盤優化的多路搜索樹 📊

引入原因

為了克服上述兩種樹形結構的局限性，特別是在處理大規模數據時減少磁盤訪問次數的需求，B樹被設計出來。它允許每個節點存儲多個關鍵字，并擁有多個子節點，從而有效地降低了樹的高度。

特性

• 定義：B樹是一種多路搜索樹，特別適用于讀寫相對較大的數據塊，如磁盤存儲。
• 優點：通過擴展節點的寬度而非深度，顯著減少了查找路徑長度，提高了整體性能。
• 缺點：雖然B樹有更寬的橫軸（即每頁可以存儲更多的索引），但由于每頁同時存儲了數據和索引，因此一頁能存儲的數據量不如專門用于存儲索引的頁多。

四、B+樹 ：進一步優化以適應數據庫需求

B+樹的優勢

• 定義：B+樹是B樹的一種變體，所有數據記錄都存儲在葉子節點中，非葉子節點僅存儲索引信息。
• 優點：
  • 更高的扇出：由于非葉子節點只存儲索引，因此可以存儲更多的索引信息，進一步降低樹的高度。
  • 更適合范圍查詢：所有葉子節點【終端節點】通過雙向鏈表相連，使得范圍查詢變得非常高效。
  • 更好的磁盤利用：非葉子節點僅存儲索引，這意味著每頁可以容納更多的索引條目，從而減少磁盤I/O操作次數。

B+樹在索引中的應用

查找4為例：

• 判斷B+樹根節點的索引記錄，3<4,那么訪問右子樹，到索引頁3；
• 在索引頁3中判斷id大小，找到與4相同的索引記錄，最后加載對應的數據頁。