C# 實作平衡多路查找樹（B-Tree）完整指南

深耕 SQL Server 多年，對 B-Tree 的核心概念早已烂熟於心。網路上鮮少見到完整的 C# 或 Java 實作範例，索性親自動手打造一個，過程中更對許多底層細節有了更透徹的理解。

什麼是 B-Tree？

B-Tree 是 1970 年由 R. Bayer 與 E. McCreight 提出，專為輔助儲存（磁碟）設計的平衡多路查找樹。在檔案系統與資料庫索引中廣泛應用，核心目標是極大減少磁碟 I/O 操作。雖然發明者未說明「B」的由來，但學術界普遍將其解釋為 Balance（平衡）。國內常誤稱為「B-樹」，實則源自英文 B-Tree 的直譯。

B-Tree 的定義特徵

• 根節點約束：若根非葉節點，至少擁有兩棵子樹。
• 節點容量：每節點含 N 個鍵值與 N+1 個指標；鍵值數不得小於最大容量的 1/2（即最小度數 t 滿足 t-1 ≤ N ≤ 2t-1）。
• 完美平衡：所有葉節點位於同一層級，這正是「平衡樹」名稱的由來。
• 有序性：父節點鍵值左側指標指向的子樹鍵值均小於該鍵值，右側指標指向的均大於該鍵值（如圖 1 中 Q 的左指標 < Q，右指標 > Q）。

為何資料庫與檔案系統鍾愛 B-Tree？

電腦儲存體系分為主存（CPU 快取、RAM）與輔存（HDD、SSD）。主存速度極快（奈秒級）但單位成本高；輔存容量大、成本低，但存取速度受限於機械結構（毫秒級），兩者相差 10 萬倍以上。

磁碟包含多個高速旋轉的盤片（7200~15000 RPM），搖臂移動磁頭讀寫。一次完整旋轉尋找資料約需 8.33 ms（7200 RPM），遠慢於記憶體的 100 ns。為攤銷機械延遲，磁碟採用頁（Page）為最小讀寫單位（SQL Server 為 8 KB）。

B-Tree 將根節點常駐主存，其餘節點置於輔存。查找元素 Y 時：讀取根節點（主存）→ 依指標讀取一層子節點（1 次 I/O）→ 再讀取葉節點（第 2 次 I/O）即可定位。對比二元搜尋樹可能需數十次 I/O，B-Tree 將查詢延遲壓縮到極致。

B-Tree 高度與度數的關鍵關係

I/O 次數取決於樹高 h。對於最小度數 t、總鍵值數 N 的 B-Tree：

t 越大，樹高越低。SQL Server 節點固定 8092 位元組，鍵值越窄（如 INT vs GUID），單節點容納的鍵值越多，t 越大，樹高越矮，查詢效能越強——這就是建議聚集索引使用窄鍵的根本原因。

若 t=1（每節點僅 1 鍵值），樹高趨近無窮大，因此 B-Tree 強制每節點至少 2 個子節點（t ≥ 2）。

C# 完整實作核心程式碼

1. 節點定義

public class TreeNode<T> where T : IComparable<T> {
    public int ElementCount = 0;
    public IList<T> Elements = new List<T>();
    public IList<TreeNode<T>> Pointers = new List<TreeNode<T>>();
    public bool IsLeaf = true;
}

採用泛型 T 並限制 IComparable<T>，確保鍵值可比較。ElementCount 追蹤實際鍵值數，Pointers 長度恆為 ElementCount + 1。

2. 樹的初始化

public class BTree<T> where T : IComparable<T> {
    private const int MaxKeysPerNode = 4; // 最小度數 t = 3
    public TreeNode<T> Root { get; private set; }

    public BTree() {
        Root = new TreeNode<T> { ElementCount = 0, IsLeaf = true };
        // 模擬：將根節點寫入磁碟（1 次 I/O 寫）
    }
}

3. 節點分裂——B-Tree 增長的唯一機制

當節點鍵值達上限 MaxKeysPerNode 時插入新鍵值，必須分裂：

1. 建立新節點，承接原節點後半部鍵值（約一半）。
2. 將中間鍵值上提至父節點。
3. 若為根節點分裂，樹高增加 1，產生新根。

private void SplitNode(TreeNode<T> parent, int childIndex, TreeNode<T> fullNode) {
    var newNode = new TreeNode<T> { IsLeaf = fullNode.IsLeaf };
    int mid = MaxKeysPerNode / 2;           // 中間索引
    int moveCount = MaxKeysPerNode - mid - 1; // 移往新節點的鍵值數

    // 1. 移動鍵值到新節點
    for (int i = 0; i < moveCount; i++)
        newNode.Elements.Add(fullNode.Elements[mid + 1 + i]);

    // 2. 若非葉節點，同步移動子指標
    if (!fullNode.IsLeaf) {
        for (int i = 0; i <= moveCount; i++)
            newNode.Pointers.Add(fullNode.Pointers[mid + 1 + i]);
    }

    // 3. 原節點保留前半部
    fullNode.ElementCount = mid;

    // 4. 父節點騰出位置，插入中間鍵值與新指標
    parent.Pointers.Insert(childIndex + 1, newNode);
    parent.Elements.Insert(childIndex, fullNode.Elements[mid]);
    parent.ElementCount++;

    // 模擬：父、原、新三節點寫回磁碟（3 次 I/O 寫）
}

4. 非滿節點插入遞迴邏輯

private void InsertNonFull(TreeNode<T> node, T key) {
    int i = node.ElementCount - 1;

    if (node.IsLeaf) {
        // 葉節點：直接插入並保持有序
        while (i >= 0 && key.CompareTo(node.Elements[i]) < 0) i--;
        node.Elements.Insert(i + 1, key);
        node.ElementCount++;
        // 模擬：寫入磁碟（1 次 I/O 寫）
    } else {
        // 內部節點：尋找下層子節點
        while (i >= 0 && key.CompareTo(node.Elements[i]) < 0) i--;
        int childIdx = i + 1;

        // 下層若已滿，先分裂再決定走左/右
        if (node.Pointers[childIdx].ElementCount == MaxKeysPerNode) {
            SplitNode(node, childIdx, node.Pointers[childIdx]);
            if (key.CompareTo(node.Elements[childIdx]) > 0) childIdx++;
        }
        InsertNonFull(node.Pointers[childIdx], key);
    }
}

5. 公開插入入口——處理根節點分裂特例

public void Insert(T key) {
    if (Root.ElementCount == MaxKeysPerNode) {
        var newRoot = new TreeNode<T> { ElementCount = 0, IsLeaf = false };
        SplitNode(newRoot, 0, Root); // 分裂舊根
        InsertNonFull(newRoot, key);
        Root = newRoot;              // 樹高 +1
    } else {
        InsertNonFull(Root, key);
    }
}

6. 查找操作——簡潔高效

public (TreeNode<T> Node, int Index) Search(T key) {
    return SearchRecursive(Root, key);
}

private (TreeNode<T>, int) SearchRecursive(TreeNode<T> node, T key) {
    int i = 0;
    while (i < node.ElementCount && key.CompareTo(node.Elements[i]) > 0) i++;

    if (i < node.ElementCount && key.CompareTo(node.Elements[i]) == 0)
        return (node, i);

    if (node.IsLeaf) return (null, -1);

    // 模擬：從磁碟讀取子節點（1 次 I/O 讀）
    return SearchRecursive(node.Pointers[i], key);
}

總結與啟示

B-Tree 以「多路、平衡、節點對齊磁碟頁」三大特性，成為關聯式資料庫與現代檔案系統的索引基石。透過親手實作，可深刻體會：

• 節點分裂即頁分裂，是寫入效能殺手——填充因子、避免 GUID 做叢集鍵皆為減少分裂。
• 樹高決定讀取 I/O 次數，窄鍵、大頁面、高扇出是優化鐵律。
• 根節點常駐記憶體，將「隨機 I/O」轉為「循序 I/O + 少量隨機 I/O」。

完整原始碼下載：BTreeCsharp.rar