高阶数据结构--B树B+树实现原理B树模拟实现--Java

目录

一、B-树概念

二、B-树插入分析

1.用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下：

2.插入过程总结

三、B树插入实现

四、B+树

1.B+树概念

2.B+树的特性

 五、B+树应用

1.索引

 2.Mysql索引

3.InnoDB

一、B-树概念

二、B-树插入分析

1.用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下：

2.插入过程总结

三、B树插入实现

public class MyBTree {
    public static final int M=3;//三叉树
    static class BTreeNode {
        public int[] keys;//关键字
        public BTreeNode[] subs;//孩子节点
        public BTreeNode parent;//父节点
        public int UsedSize;//存储的关键字数量
        public BTreeNode() {
            //这里多给一个空间是为了分裂实现更容易
            keys=new int[M];
            subs=new BTreeNode[M+1];
        }
    }
    public BTreeNode root;

    /**
     * 插入一个元素
     * @param val
     */
    public boolean insert(int val) {
        //B树为空的时候
        if(root==null) {
            root=new BTreeNode();
            root.keys[0]=val;
            root.UsedSize=1;
            return true;
        }
        //当B树不为空的时候
        Pair<BTreeNode,Integer> pair=Find(val);
        if(pair.getVal()!=-1) {
            return false;
        }
        BTreeNode parent=pair.getKey();
        int index=parent.UsedSize-1;
        for(;index>=0;index--) {
            if(parent.keys[index]>=val) {
                parent.keys[index+1]=parent.keys[index];
            }else {
                break;
            }
        }
        parent.keys[index+1]=val;
        parent.UsedSize++;
        if(parent.UsedSize>=M) {
            split(parent);
            return true;
        }else {
            return true;
        }
    }

    /**
     * 分裂节点
     * @param cur
     */
    private void split(BTreeNode cur) {
        BTreeNode parent=cur.parent;
        BTreeNode newNode=new BTreeNode();
        int mid= cur.UsedSize>>1;
        int i=mid+1;
        int j=0;
        while (i<cur.UsedSize) {
            newNode.keys[j]=cur.keys[i];
            newNode.subs[j]=cur.subs[i];
            if(newNode.subs[j]!=null) {
                newNode.subs[j].parent=newNode;
            }
            i++;
            j++;
        }
        newNode.subs[j]=cur.subs[i];
        if(newNode.subs[j]!=null) {
            newNode.subs[j].parent=newNode;
        }
        newNode.UsedSize=j;
        cur.UsedSize=cur.UsedSize-j-1;
        if(cur==root) {
            root=new BTreeNode();
            root.keys[0]=cur.keys[mid];
            root.subs[0]=cur;
            root.subs[1]=newNode;
            root.UsedSize=1;
            cur.parent=root;
            newNode.parent=root;
            return;
        }
        newNode.parent=parent;

        int endT=parent.UsedSize-1;
        for (;endT>=0;endT--) {
            if(parent.keys[endT]>=cur.keys[mid]) {
                parent.keys[endT+1]=parent.keys[endT];
                parent.subs[endT+2]=parent.subs[endT+1];
            }else {
                break;
            }
        }
        parent.keys[endT+1]=cur.keys[mid];
        //将当前父亲节点的孩子节点更改为newNode
        parent.subs[endT+2]=newNode;
        parent.UsedSize++;
        if(parent.UsedSize>=M) {
            split(parent);
        }
    }

    /**
     * 查找B树中是否存在该元素
     * @param val
     * @return
     */
    private Pair<BTreeNode, Integer> Find(int val) {
        BTreeNode cur=root;
        BTreeNode parent = null;
        while (cur!=null) {
            int i=0;
            while (i<cur.UsedSize) {
                if(cur.keys[i]==val) {
                    return new Pair<>(cur,i);
                } else if (cur.keys[i]<val) {
                    i++;
                }else {
                    break;
                }
            }
            parent=cur;
            cur=cur.subs[i];
        }
        return new Pair<>(parent,-1);
    }

    /**
     * 验证B树，如果输出的是一个有序的结果则证明是B树
     * @param root
     */
    private void inorder(BTreeNode root){
        if(root == null)
            return;
        for(int i = 0; i < root.UsedSize; ++i){
            inorder(root.subs[i]);
            System.out.println(root.keys[i]);
        }
        inorder(root.subs[root.UsedSize]);
    }
}

B树验证

public static void main(String[] args) {
        MyBTree bTree=new MyBTree();
        int[] arrays={75,49,36,53,101,139,145};
        for (int i = 0; i < arrays.length; i++) {
            bTree.insert(arrays[i]);
        }
        bTree.inorder(bTree.root);
    }

输出结果 ：

36
49
53
75
101
139
145

四、B+树

1.B+树概念

2.B+树的特性

1. 所有关键字都出现在叶子节点的链表中(稠密索引)，且链表中的节点都是有序的。

2. 不可能在非叶子节点中命中。

 五、B+树应用

1.索引

 2.Mysql索引

3.InnoDB