您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

B 樹算法 Java 完整實現：從原理到可視化輸出

編輯：Java 相關知識

B 樹核心特性

多路平衡搜索樹：每個節點最多 M 個孩子（M 階），關鍵字數 = 孩子數 - 1。
自平衡：插入分裂、刪除合併/借用，保證樹高 O(log_M N)。
磁盤友好：節點大小匹配磁盤頁（通常 4KB~16KB），一次 I/O 讀取一個節點，極大減少磁盤訪問次數。
所有葉子同層：查詢路徑長度固定，性能穩定。

節點結構定義

public class BTree, Value> {
    private static final int M = 4; // 4階：每節點最多 3 個鍵，4 個孩子
    
    private static final class Node {
        int m;                     // 當前孩子數
        Entry[] children = new Entry[M];
        Node(int k) { m = k; }
    }
    
    private static class Entry {
        Comparable key;
        Object val;
        Node next;                 // 內部節點指向子樹；外部節點 val 存值
        Entry(Comparable key, Object val, Node next) { ... }
    }
    
    private Node root = new Node(0);
    private int height = 0;
    private int n = 0;             // 鍵值對總數
}

核心操作：查找

public Value get(Key key) {
    if (key == null) throw new NullPointerException();
    return search(root, key, height);
}

@SuppressWarnings("unchecked")
private Value search(Node x, Key key, int ht) {
    Entry[] children = x.children;
    if (ht == 0) { // 外部節點（葉子）：線性掃描
        for (int j = 0; j < x.m; j++)
            if (key.compareTo((Key) children[j].key) == 0)
                return (Value) children[j].val;
    } else { // 內部節點：二分查找定位孩子
        for (int j = 0; j < x.m; j++) {
            if (j + 1 == x.m || key.compareTo((Key) children[j+1].key) < 0)
                return search(children[j].next, key, ht - 1);
        }
    }
    return null;
}

核心操作：插入與分裂

public void put(Key key, Value val) {
    if (key == null) throw new NullPointerException();
    Node u = insert(root, key, val, height);
    n++;
    if (u == null) return; // 未分裂
    
    // 根節點分裂：創建新根，高度+1
    Node t = new Node(2);
    t.children[0] = new Entry(root.children[0].key, null, root);
    t.children[1] = new Entry(u.children[0].key, null, u);
    root = t;
    height++;
}

private Node insert(Node h, Key key, Value val, int ht) {
    Entry t = new Entry(key, val, null);
    int j = 0;
    
    if (ht == 0) { // 葉子：找到插入位置
        while (j < h.m && key.compareTo((Key) h.children[j].key) > 0) j++;
    } else { // 內部節點：遞歸插入子樹
        while (j < h.m) {
            if (j + 1 == h.m || key.compareTo((Key) h.children[j+1].key) < 0) {
                Node u = insert(h.children[j].next, key, val, ht - 1);
                if (u == null) return null;
                t.key = u.children[0].key; // 上浮分裂節點的最小鍵
                t.next = u;
                break;
            }
            j++;
        }
    }
    
    // 移位插入
    for (int i = h.m; i > j; i--) h.children[i] = h.children[i-1];
    h.children[j] = t;
    h.m++;
    
    // 滿了則分裂
    return (h.m < M) ? null : split(h);
}

private Node split(Node h) {
    Node t = new Node(M/2);
    h.m = M/2;
    for (int j = 0; j < M/2; j++)
        t.children[j] = h.children[M/2 + j];
    return t; // 返回右半部分，鍵已上浮至父節點
}

可視化輸出：樹結構打印

public String toString() {
    return toString(root, height, "") + "\n";
}

private String toString(Node h, int ht, String indent) {
    StringBuilder s = new StringBuilder();
    if (ht == 0) {
        for (int j = 0; j < h.m; j++)
            s.append(indent).append(h.children[j].key).append(" ").append(h.children[j].val).append("\n");
    } else {
        for (int j = 0; j < h.m; j++) {
            if (j > 0) s.append(indent).append("(").append(h.children[j].key).append(")\n");
            s.append(toString(h.children[j].next, ht - 1, indent + "  "));
        }
    }
    return s.toString();
}

測試驗證

public static void main(String[] args) {
    BTree st = new BTree<>();
    String[] domains = {
        "www.cs.princeton.edu", "www.princeton.edu", "www.yale.edu",
        "www.simpsons.com", "www.apple.com", "www.amazon.com",
        "www.ebay.com", "www.cnn.com", "www.谷歌.com", "www.nytimes.com",
        "www.microsoft.com", "www.dell.com", "www.slashdot.org",
        "www.espn.com", "www.weather.com", "www.yahoo.com"
    };
    for (int i = 0; i < domains.length; i++)
        st.put(domains[i], "128.112.136." + (10 + i));
    
    System.out.println("size: " + st.size());    // 16
    System.out.println("height: " + st.height()); // 2
    System.out.println(st); // 打印樹結構
}

輸出示例（M=4）

size: 16
height: 2
    www.amazon.com 128.112.136.12
    www.apple.com 128.112.136.13
    www.cnn.com 128.112.136.14
    (www.cs.princeton.edu)
      www.cs.princeton.edu 128.112.136.15
      www.cs.princeton.edu 128.112.136.16
      www.dell.com 128.112.136.17
    (www.ebay.com)
      www.ebay.com 128.112.136.18
      www.espn.com 128.112.136.19
      www.谷歌.com 128.112.136.20
    ...