Java数据结构与算法(B+树)

前言

B+树（B+ Tree）是一种平衡树数据结构，广泛用于数据库和文件系统中。它是一种自平衡的树结构，每个节点包含多个键，并且所有键都是排序的。B+树的叶子节点包含指向相邻叶子节点的指针，这使得范围查询非常高效。

B+树的优点

1.由于B+树在非叶子结点上不包含真正的数据，只当做索引使用，因此在内存相同的情况下，能够存放更多的key；

2.B+树的叶子结点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。

3、B+树与B树相比最明显的其实就是寻址向内存传输这个过程，磁盘向内存中推送数据，每次只能推送一页(4KB）的数据，B树中每一个节点都带有value值，可能一页只能存储一个节点，甚至如果value值过大，可能需要多页，然而，B+树中只有非叶子结点存储value值，上面的节点只存储索引，占用内存就小的多了，可能一次就可以传输完成。

动画过程

B+ Tree Visualization

具体代码实现

package test11;

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

class BPlusTreeNode<T extends Comparable<T>> {
    private boolean isLeaf;
    private List<T> keys;
    private List<BPlusTreeNode<T>> children;
    private BPlusTreeNode<T> next;

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

    public boolean isLeaf() {
        return isLeaf;
    }

    public List<T> getKeys() {
        return keys;
    }

    public List<BPlusTreeNode<T>> getChildren() {
        return children;
    }

    public BPlusTreeNode<T> getNext() {
        return next;
    }

    public void setNext(BPlusTreeNode<T> next) {
        this.next = next;
    }
}


public class BPlusTree<T extends Comparable<T>> {
    private int order;
    private BPlusTreeNode<T> root;

    public BPlusTree(int order) {
        if (order < 3) {
            throw new IllegalArgumentException("Order of B+ tree must be at least 3");
        }
        this.order = order;
        this.root = new BPlusTreeNode<>(true);
    }

    public void insert(T key) {
        BPlusTreeNode<T> root = this.root;
        if (root.getKeys().size() == order - 1) {
            BPlusTreeNode<T> newRoot = new BPlusTreeNode<>(false);
            newRoot.getChildren().add(root);
            splitChild(newRoot, 0, root);
            this.root = newRoot;
        }
        insertNonFull(this.root, key);
    }

    private void splitChild(BPlusTreeNode<T> parent, int index, BPlusTreeNode<T> child) {
        BPlusTreeNode<T> newChild = new BPlusTreeNode<>(child.isLeaf());
        int mid = order / 2;
        parent.getKeys().add(index, child.getKeys().get(mid));
        parent.getChildren().add(index + 1, newChild);

        newChild.getKeys().addAll(child.getKeys().subList(mid + 1, child.getKeys().size()));
        child.getKeys().subList(mid, child.getKeys().size()).clear();

        if (!child.isLeaf()) {
            newChild.getChildren().addAll(child.getChildren().subList(mid + 1, child.getChildren().size()));
            child.getChildren().subList(mid + 1, child.getChildren().size()).clear();
        } else {
            newChild.setNext(child.getNext());
            child.setNext(newChild);
        }
    }

    private void insertNonFull(BPlusTreeNode<T> node, T key) {
        if (node.isLeaf()) {
            int pos = Collections.binarySearch(node.getKeys(), key);
            if (pos < 0) {
                pos = -(pos + 1);
            }
            node.getKeys().add(pos, key);
        } else {
            int pos = Collections.binarySearch(node.getKeys(), key);
            if (pos < 0) {
                pos = -(pos + 1);
            } else {
                pos++;
            }
            BPlusTreeNode<T> child = node.getChildren().get(pos);
            if (child.getKeys().size() == order - 1) {
                splitChild(node, pos, child);
                if (key.compareTo(node.getKeys().get(pos)) > 0) {
                    pos++;
                }
            }
            insertNonFull(node.getChildren().get(pos), key);
        }
    }

    public boolean search(T key) {
        return search(root, key);
    }

    private boolean search(BPlusTreeNode<T> node, T key) {
        int pos = Collections.binarySearch(node.getKeys(), key);
        if (pos >= 0) {
            return true;
        } else if (node.isLeaf()) {
            return false;
        } else {
            pos = -(pos + 1);
            return search(node.getChildren().get(pos), key);
        }
    }

    public void print() {
        print(root, "", true);
    }

    private void print(BPlusTreeNode<T> node, String indent, boolean last) {
        System.out.print(indent);
        if (last) {
            System.out.print("└─");
            indent += "  ";
        } else {
            System.out.print("├─");
            indent += "| ";
        }
        System.out.println(node.getKeys());
        if (!node.isLeaf()) {
            for (int i = 0; i < node.getChildren().size(); i++) {
                print(node.getChildren().get(i), indent, i == node.getChildren().size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        BPlusTree<Integer> bPlusTree = new BPlusTree<>(3);
        bPlusTree.insert(1);
        bPlusTree.insert(2);
        bPlusTree.insert(3);
        bPlusTree.insert(4);
        bPlusTree.insert(5);

        bPlusTree.print();

        System.out.println("Search 3: " + bPlusTree.search(3));
        System.out.println("Search 6: " + bPlusTree.search(6));
    }
}

QA:待定