二叉树算法之B 树（B-Tree）详细解读

B树（B-Tree）是一种自平衡的多路查找树，广泛用于数据库和文件系统等存储系统中。B树的每个节点可以有多个子节点，并且每个节点可以存储多个键值，从而减少树的高度，减少磁盘I/O操作，提高搜索效率。B树是对二叉搜索树（BST）的推广，使其适用于更大规模的数据存储和查找。

m0_61840987

1299人浏览 · 2024-10-19 08:00:00

m0_61840987 · 2024-10-19 08:00:00 发布

B树的设计目标是：

减少树的高度：通过允许每个节点存储多个键值，降低树的高度，从而减少访问节点的次数，特别适合外存（磁盘）场景。
提高磁盘访问效率：B树节点的大小通常与磁盘块的大小相匹配，使得每次访问都能加载一个完整的节点，减少不必要的磁盘I/O操作。

1. B树的定义与性质

B树是满足以下性质的多路平衡树：

每个节点可以有多个子节点。假设B树的阶数为 m，则：
- 每个节点最多可以有 m 个子节点。
- 每个非根节点至少有 ⌈m/2⌉ 个子节点。
每个节点可以存储多个键值。假设阶数为 m，则：
- 每个节点最多可以存储 m−1 个键值。
- 每个非根节点至少存储 ⌈m/2⌉−1 个键值。
所有叶子节点处于同一层。B树始终保持平衡，树的所有叶子节点位于同一层，保证了查找操作的时间复杂度为 O(log⁡n)。
节点中的键值按照递增顺序排列。对于每个节点 xxx，设其键值为 k1,k2,...,kt−1，且节点有 t个子节点，满足：
- 左子节点的所有键值小于 k1。
- 介于两个键值 ki和 ki+1 之间的子节点，其键值介于 ki 和 ki+1 之间。
- 右子节点的所有键值大于 kt−1。

2. B树的操作

B树中的查找、插入和删除操作与二叉搜索树相似，但由于B树的节点可以有多个子节点和多个键值，操作会稍微复杂一些。

2.1 查找操作

查找操作在B树中与二叉搜索树类似，都是基于比较键值的大小进行的。由于每个节点包含多个键值，查找时需要在节点内进行线性或二分查找，然后根据键值的大小决定是向左子树、右子树，还是当前节点中继续查找。

步骤：

从根节点开始，比较查找键值 k 与当前节点的键值集合。
如果 k 在当前节点中，则查找成功。
如果 k 小于某个键值，进入该键值对应的左子树。
重复上述过程，直到找到键值或到达叶子节点。

查找操作的时间复杂度为 O(log⁡n)，其中 n 是树中的总元素数量。

2.2 插入操作

B树的插入操作类似于二叉搜索树，但需要处理节点分裂的情况。插入新元素可能会导致某个节点的键值超过其最大容量（即存储超过 m−1 个键值），这时候需要将该节点分裂，并将中间的键值上移到父节点。若父节点也满了，则继续向上分裂，直到根节点。如果根节点也分裂，则树的高度增加。

步骤：

查找插入位置：首先按照查找操作找到适当的叶子节点插入键值。
插入键值：如果叶子节点未满，则直接插入键值到该节点，保持键值的排序。
节点分裂：如果节点满了，则将该节点分为两个节点，并将中间的键值上移到父节点。
若父节点也满了，重复分裂操作，直到不再需要分裂或处理到根节点。

插入操作的最坏时间复杂度为 O(log⁡n)，因为分裂操作最多向上递归到根节点。

2.3 删除操作

B树的删除操作比插入操作更复杂，删除一个键值可能导致某个节点的键值数量小于其最小容量（即少于 ⌈m/2⌉−1 个键值），此时需要进行合并或借位操作来保持B树的平衡。

步骤：

查找删除位置：首先按照查找操作找到要删除的键值。
删除键值：如果删除的是叶子节点中的键值，直接删除。如果删除的是内部节点的键值，则需要找到前驱或后继键值，并替换该键值，然后删除前驱或后继节点中的键值。
节点合并或借位：
- 如果删除后节点的键值数量小于最小容量，则需要从兄弟节点借一个键值（借位操作），或将当前节点与兄弟节点合并（合并操作）。
- 若父节点的键值数量也小于最小容量，则向上递归进行合并或借位操作。

删除操作的最坏时间复杂度同样为 O(log⁡n)，因为合并或借位操作最多向上递归到根节点。

3. B树的优势与应用

优势

高效的磁盘I/O：B树节点通常较大，能够一次性读取大量数据，减少磁盘访问次数，特别适合大规模数据存储。
自平衡：B树始终保持平衡，确保查找、插入和删除操作的时间复杂度为 O(log⁡n)。
更少的树高度：与二叉搜索树相比，B树通过允许每个节点存储多个键值，大大减少了树的高度，从而减少了查找路径。

应用

B树广泛应用于需要大量数据存储和查找的场景，特别是涉及外存的场景：

数据库索引：大多数现代数据库系统使用B树或B+树作为索引结构，以支持高效的数据查找。
文件系统：许多文件系统（如NTFS、FAT）使用B树来管理磁盘上的文件和目录。
键值存储：一些键值存储系统使用B树来组织和查找数据，以支持快速的数据存取。

4. B树的Java实现

以下是一个简单的B树的Java实现，展示了插入操作和查找操作的基本逻辑。

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

class BTreeNode {
    int t;  // B树的最小度数（阶数的半数）
    ArrayList<Integer> keys;  // 节点中的键值
    ArrayList<BTreeNode> children;  // 子节点
    boolean isLeaf;  // 是否是叶子节点

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

    // 插入非满节点
    public void insertNonFull(int key) {
        int i = keys.size() - 1;

        if (isLeaf) {
            // 如果是叶子节点，直接插入
            keys.add(0);  // 占位
            while (i >= 0 && keys.get(i) > key) {
                keys.set(i + 1, keys.get(i));
                i--;
            }
            keys.set(i + 1, key);  // 插入新键值
        } else {
            // 如果不是叶子节点，找到合适的子节点递归插入
            while (i >= 0 && keys.get(i) > key) {
                i--;
            }
            i++;

            if (children.get(i).keys.size() == 2 * t - 1) {
                // 如果子节点已满，需要分裂
                splitChild(i, children.get(i));

                if (keys.get(i) < key) {
                    i++;
                }
            }
            children.get(i).insertNonFull(key);
        }
    }

    // 分裂子节点
    public void splitChild(int i, BTreeNode y) {
        BTreeNode z = new BTreeNode(y.t, y.isLeaf);
        for (int j = 0; j < t - 1; j++) {
            z.keys.add(y.keys.remove(t));
        }

        if (!y.isLeaf) {
            for (int j = 0; j < t; j++) {
                z.children.add(y.children.remove(t));
            }
        }

        children.add(i + 1, z);
        keys.add(i, y.keys.remove(t - 1));
    }

    // 查找键值
    public boolean search(int key) {
        int i = 0;
        while (i < keys.size() && key > keys.get(i)) {
            i++;
        }

        if (i < keys.size() && key == keys.get(i)) {
            return true;
        }

        if (isLeaf) {
            return false;
        }

        return children.get(i).search(key);
    }
}

class BTree {
    BTreeNode root;
    int t;

    public BTree(int t) {
        this.t = t;
        root = new BTreeNode(t, true);
    }

    public void insert(int key) {
        BTreeNode r = root;
        if (r.keys.size() == 2 * t - 1) {
            BTreeNode s = new BTreeNode(t, false);
            s.children.add(r);
            s.splitChild(0, r);
            root = s;
        }
        root.insertNonFull(key);
    }

    public boolean search(int key) {
        return root.search(key);
    }
}

public class Main {
    public static void main(String[] args) {
        BTree btree = new BTree(3);
        int[] keys = {10, 20, 5, 6, 12, 30, 7, 17};

        for (int key : keys) {
            btree.insert(key);
        }

        System.out.println("查找键值 12: " + btree.search(12));
        System.out.println("查找键值 25: " + btree.search(25));
    }
}