每日算法 — 使用java实现B树：多路平衡搜索与数据库索引优化

引言

B树（B-Tree）是一种自平衡的多路搜索树，由Rudolf Bayer和Edward McCreight于1972年发明。与二叉搜索树不同，B树的每个节点可以拥有多个子节点，这使得它非常适合磁盘存储系统。数据库系统如MySQL的InnoDB引擎、文件系统如NTFS和HFS+都广泛采用B树及其变种（如B+树）作为索引结构。本文将深入讲解B树的核心原理，并用Java实现一个完整的B树数据结构。

B树的核心性质

一棵阶数为 ( m ) 的B树满足以下性质：

• 每个节点最多包含 ( m-1 ) 个关键字和 ( m ) 个子节点
• 除根节点外，每个节点至少包含 ( \lceil m/2
  ceil – 1 ) 个关键字
• 根节点至少包含1个关键字（除非树为空）
• 所有叶子节点位于同一层
• 节点内的关键字按升序排列

这些性质保证了B树的高度始终维持在 ( O(\log_m n) )，使得查找、插入和删除操作都具有稳定的对数时间复杂度。

Java实现

节点定义

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * B树节点类
 * 每个节点维护一个有序的关键字列表和一个子节点列表
 */
public class BTreeNode {
    // 关键字列表，保持升序
    List<Integer> keys;
    // 子节点列表，keys.size() + 1 == children.size()
    List<BTreeNode> children;
    // 是否为叶子节点
    boolean isLeaf;

    public BTreeNode(boolean isLeaf) {
        this.keys = new ArrayList<>();
        this.children = new ArrayList<>();
        this.isLeaf = isLeaf;
    }

    /**
     * 在节点内查找关键字的插入位置
     * 返回第一个大于等于key的索引
     */
    public int findKeyIndex(int key) {
        int idx = 0;
        while (idx < keys.size() && keys.get(idx) < key) {
            idx++;
        }
        return idx;
    }
}

B树核心类

/**
 * B树实现类
 * 支持查找、插入操作，阶数m决定了节点的容量上限
 */
public class BTree {
    // B树的阶数，即每个节点最多有m个子节点
    private int m;
    // 根节点
    private BTreeNode root;

    public BTree(int m) {
        if (m < 3) {
            throw new IllegalArgumentException("B树阶数至少为3");
        }
        this.m = m;
        this.root = new BTreeNode(true);
    }

    /**
     * 查找关键字
     * 从根节点开始，沿着正确的子节点路径向下搜索
     */
    public boolean search(int key) {
        return searchNode(root, key);
    }

    private boolean searchNode(BTreeNode node, int key) {
        int idx = node.findKeyIndex(key);

        // 如果当前节点包含该关键字
        if (idx < node.keys.size() && node.keys.get(idx) == key) {
            return true;
        }

        // 如果是叶子节点且未找到，则不存在
        if (node.isLeaf) {
            return false;
        }

        // 递归搜索对应的子节点
        return searchNode(node.children.get(idx), key);
    }

    /**
     * 插入关键字
     * 先找到合适的叶子节点插入，如果节点满则进行分裂
     */
    public void insert(int key) {
        BTreeNode rootNode = root;

        // 如果根节点已满，需要分裂根节点
        if (rootNode.keys.size() == m - 1) {
            BTreeNode newRoot = new BTreeNode(false);
            newRoot.children.add(rootNode);
            splitChild(newRoot, 0, rootNode);
            root = newRoot;
        }

        insertNonFull(root, key);
    }

    /**
     * 向非满节点中插入关键字
     */
    private void insertNonFull(BTreeNode node, int key) {
        int idx = node.findKeyIndex(key);

        // 如果是叶子节点，直接插入
        if (node.isLeaf) {
            node.keys.add(idx, key);
            return;
        }

        // 如果子节点已满，先分裂
        BTreeNode child = node.children.get(idx);
        if (child.keys.size() == m - 1) {
            splitChild(node, idx, child);
            // 分裂后，检查key应该插入哪个子节点
            if (key > node.keys.get(idx)) {
                idx++;
            }
        }

        insertNonFull(node.children.get(idx), key);
    }

    /**
     * 分裂满子节点
     * 将parent的第childIdx个子节点分裂为两个节点
     */
    private void splitChild(BTreeNode parent, int childIdx, BTreeNode fullChild) {
        int mid = (m - 1) / 2;  // 中间关键字的位置
        int midKey = fullChild.keys.get(mid);

        // 创建新节点，包含右半部分
        BTreeNode newNode = new BTreeNode(fullChild.isLeaf);

        // 将fullChild右半部分的关键字移到newNode
        for (int i = mid + 1; i < fullChild.keys.size(); i++) {
            newNode.keys.add(fullChild.keys.get(i));
        }

        // 如果不是叶子节点，还需要移动子节点
        if (!fullChild.isLeaf) {
            for (int i = mid + 1; i < fullChild.children.size(); i++) {
                newNode.children.add(fullChild.children.get(i));
            }
        }

        // 移除fullChild中已移走的关键字和子节点
        while (fullChild.keys.size() > mid) {
            fullChild.keys.remove(fullChild.keys.size() - 1);
        }
        if (!fullChild.isLeaf) {
            while (fullChild.children.size() > mid + 1) {
                fullChild.children.remove(fullChild.children.size() - 1);
            }
        }

        // 将中间关键字提升到父节点
        parent.keys.add(childIdx, midKey);
        parent.children.add(childIdx + 1, newNode);
    }

    /**
     * 中序遍历B树，输出有序序列
     */
    public void inorderTraversal() {
        inorder(root);
        System.out.println();
    }

    private void inorder(BTreeNode node) {
        if (node == null) return;

        for (int i = 0; i < node.keys.size(); i++) {
            if (!node.isLeaf) {
                inorder(node.children.get(i));
            }
            System.out.print(node.keys.get(i) + " ");
        }

        if (!node.isLeaf) {
            inorder(node.children.get(node.keys.size()));
        }
    }

    /**
     * 获取树的高度
     */
    public int height() {
        return height(root);
    }

    private int height(BTreeNode node) {
        if (node == null) return 0;
        if (node.isLeaf) return 1;
        return 1 + height(node.children.get(0));
    }
}

测试与演示

public class BTreeDemo {
    public static void main(String[] args) {
        // 创建一个阶数为5的B树
        BTree btree = new BTree(5);

        // 插入一批数据
        int[] data = {10, 20, 5, 6, 12, 30, 7, 17, 3, 1, 15, 25, 35, 40};
        System.out.println("插入序列: ");
        for (int key : data) {
            System.out.print(key + " ");
            btree.insert(key);
        }
        System.out.println("\n");

        // 中序遍历输出有序序列
        System.out.print("中序遍历结果: ");
        btree.inorderTraversal();

        // 查找测试
        System.out.println("\n查找测试:");
        int[] searchKeys = {15, 100, 7, 50};
        for (int key : searchKeys) {
            System.out.println("查找 " + key + ": " + (btree.search(key) ? "找到" : "未找到"));
        }

        System.out.println("\nB树高度: " + btree.height());
    }
}

复杂度分析

其中 ( n ) 为关键字总数，( m ) 为B树阶数，( h ) 为树高。B树的高度 ( h \leq \log_{\lceil m/2
ceil}((n+1)/2) + 1 )，因此即使数据量很大，树高也能保持在很小的范围内。

B树与B+树的区别

B+树是B树的变种，主要区别在于：
– B+树的所有数据都存储在叶子节点，内部节点只存储索引键
– B+树的叶子节点通过指针链接形成有序链表，便于范围查询
– B+树的内部节点可以容纳更多键，进一步降低树高

MySQL InnoDB存储引擎使用的就是B+树索引，因为它更适合磁盘I/O场景和范围查询。

总结

B树通过多路分支和自平衡机制，将树高控制在极低的水平，极大地减少了磁盘I/O次数。本文实现的Java版B树包含了完整的插入和查找逻辑，展示了分裂操作如何维持B树的平衡性质。理解B树是掌握数据库索引原理的关键一步。