【B+树数据结构】

什么是B+树

B+ 树是一种 自平衡的多叉搜索树，常用于 数据库索引（如 MySQL）和文件系统。它是 B-树（B-tree）的变种，具有更高的磁盘读写效率和范围查询性能。
特点：
1 所有数据存储在叶子节点，非叶子节点仅存储索引键，不存数据。
2 叶子节点之间有指针相连，支持高效的区间查询。
3 多路平衡树（非二叉树），每个节点最多有 M 个子节点（M 阶 B+ 树）。
4 根节点到叶子节点的路径长度相同，保持树的平衡性。
5 非叶子节点不会存储数据，只作为索引，提高内存利用率。

B+树的实现

package com.dataStract;

import java.util.*;

public class BPlusTree<K extends Comparable<K>, V> {

    private static final int ORDER = 4; // B+树的阶数 (每个节点最多有 ORDER 个子节点)
    private Node<K, V> root;

    public BPlusTree() {
        root = new LeafNode<>();
    }

    // 插入键值对
    public void insert(K key, V value) {
        root.insert(key, value, this);
    }

    // 查找
    public V search(K key) {
        return root.search(key);
    }

    // 遍历
    public void traverse() {
        root.traverse();
    }

    // B+树的节点类型（抽象类）
    abstract static class Node<K extends Comparable<K>, V> {
        List<K> keys;

        Node() {
            keys = new ArrayList<>();
        }

        abstract void insert(K key, V value, BPlusTree<K, V> tree);

        abstract V search(K key);

        abstract void traverse();
    }

    // 内部节点
    static class InternalNode<K extends Comparable<K>, V> extends Node<K, V> {
        List<Node<K, V>> children;

        InternalNode() {
            children = new ArrayList<>();
        }

        @Override
        void insert(K key, V value, BPlusTree<K, V> tree) {
            // 找到合适的子节点插入
            int idx = Collections.binarySearch(keys, key);
            if (idx < 0) idx = -idx - 1;
            children.get(idx).insert(key, value, tree);

            // 处理分裂
            if (children.size() > ORDER) {
                split(tree);
            }
        }

        private void split(BPlusTree<K, V> tree) {
            int midIndex = keys.size() / 2;
            K midKey = keys.get(midIndex);

            InternalNode<K, V> sibling = new InternalNode<>();
            sibling.keys.addAll(keys.subList(midIndex + 1, keys.size()));
            sibling.children.addAll(children.subList(midIndex + 1, children.size()));

            keys.subList(midIndex, keys.size()).clear();
            children.subList(midIndex + 1, children.size()).clear();

            if (this == tree.root) {
                InternalNode<K, V> newRoot = new InternalNode<>();
                newRoot.keys.add(midKey);
                newRoot.children.add(this);
                newRoot.children.add(sibling);
                tree.root = newRoot;
            }
        }

        @Override
        V search(K key) {
            int idx = Collections.binarySearch(keys, key);
            if (idx < 0) idx = -idx - 1;
            return children.get(idx).search(key);
        }

        @Override
        void traverse() {
            for (Node<K, V> child : children) {
                child.traverse();
            }
        }
    }

    // 叶子节点
    static class LeafNode<K extends Comparable<K>, V> extends Node<K, V> {
        List<V> values;
        LeafNode<K, V> next;

        LeafNode() {
            values = new ArrayList<>();
        }

        @Override
        void insert(K key, V value, BPlusTree<K, V> tree) {
            int idx = Collections.binarySearch(keys, key);
            if (idx >= 0) {
                values.set(idx, value); // 更新已有值
            } else {
                idx = -idx - 1;
                keys.add(idx, key);
                values.add(idx, value);
            }

            if (keys.size() > ORDER - 1) {
                split(tree);
            }
        }

        private void split(BPlusTree<K, V> tree) {
            int midIndex = keys.size() / 2;

            LeafNode<K, V> sibling = new LeafNode<>();
            sibling.keys.addAll(keys.subList(midIndex, keys.size()));
            sibling.values.addAll(values.subList(midIndex, values.size()));

            keys.subList(midIndex, keys.size()).clear();
            values.subList(midIndex, values.size()).clear();

            sibling.next = this.next;
            this.next = sibling;

            if (this == tree.root) {
                InternalNode<K, V> newRoot = new InternalNode<>();
                newRoot.keys.add(sibling.keys.get(0));
                newRoot.children.add(this);
                newRoot.children.add(sibling);
                tree.root = newRoot;
            } else {
                ((InternalNode<K, V>) tree.root).children.add(sibling);
            }
        }

        @Override
        V search(K key) {
            int idx = Collections.binarySearch(keys, key);
            if (idx >= 0) return values.get(idx);
            return null;
        }

        @Override
        void traverse() {
            System.out.println(keys + " -> " + values);
            if (next != null) next.traverse();
        }
    }

    public static void main(String[] args) {
        BPlusTree<Integer, String> tree = new BPlusTree<>();
        tree.insert(10, "A");
        tree.insert(20, "B");
        tree.insert(30, "C");
        tree.insert(40, "D");
        tree.insert(50, "E");
        tree.insert(60, "F");

        tree.traverse();

        System.out.println("Search 30: " + tree.search(30));
        System.out.println("Search 70: " + tree.search(70)); // 不存在
    }
}

(1) 插入
1 插入时，数据始终存储在叶子节点。
2 如果叶子节点满了，就需要分裂。
3 分裂后，非叶子节点需要插入新的索引键，可能导致递归分裂。
4 叶子节点分裂后，索引节点调整。
5 如果索引节点溢出，则需要递归分裂到更高层。
(2) B+ 树的查询
1 B+ 树查询路径始终从根节点到叶子节点（O(log N) 复杂度）。
2 非叶子节点只作为索引，不存数据，每次查询都要到叶子节点获取数据。
3 支持范围查询（因为叶子节点有指针连接）。

B+树叶子结点和非叶子节点分裂

叶子节点分裂触发条件

1 叶子节点存储满了（即存储的索引键值数量超过设定的上限），需要插入新的数据。
2 MySQL 的 InnoDB 存储引擎默认 每个数据页 16KB，叶子节点的键值填满后，新的键值无法插入，触发分裂。
分裂步骤：
叶子节点分裂步骤
1.创建新的叶子节点（右兄弟）。
2.数据拆分：
把一半的键值对 移动到新叶子节点（右节点）。
3.更新双向链表指针：
叶子节点存储着前后节点的指针，需要更新。
4.父节点插入新的索引键：
把 新叶子节点的最小键 插入 父节点，让父节点能够正确索引两个子节点。

非叶子节点（内部节点）分裂

触发条件：
1.叶子节点分裂后，会向 父节点插入一个新的索引键。
2.如果父节点的存储容量超出上限，则 非叶子节点也会分裂。
非叶子节点的分裂步骤:
1.创建新的内部节点（右兄弟）。
2.把父节点的一半键值移动到新内部节点。
3.修改原父节点的指针，使其指向新的内部节点。
4.把分裂点的索引键插入更上层的父节点。
5.如果根节点分裂，则创建新的根节点，使 B+树的高度增加。

叶子节点删除数据的影响

当 叶子节点中的某些数据被删除，其影响取决于当前叶子节点的剩余数据量是否仍然符合 B+ 树的约束条件。
1.删除后，叶子节点仍然超过最小容量（无影响 ）
2.直接删除数据，不影响树结构，不需要任何调整。
3.删除后，叶子节点的数据量低于最小容量（触发合并或借用操作 ）
4.如果兄弟叶子节点有足够多的数据，可以 从兄弟节点借数据（旋转）。
5.如果兄弟叶子节点数据也不足，则 合并叶子节点，并调整父节点的索引键。