B+树的设计步骤

 说起b+树索引，就不得不提二叉查找树，平衡二叉树和b树这三种数据结构。b+树就是从他们仨演化来的。

在mysql中，b+树索引按照存储方式的不同分为聚集索引和非聚集索引。

1. 聚集索引（聚簇索引）：以innodb作为存储引擎的表，表中的数据都会有一个主键，即使你不创建主键，系统也会帮你创建一个隐式的主键。这是因为innodb是把数据存放在b+树中的，而b+树的键值就是主键，在b+树的叶子节点中，存储了表中所有的数据。这种以主键作为b+树索引的键值而构建的b+树索引，我们称之为聚集索引。 

2. 非聚集索引（非聚簇索引）：以主键以外的列值作为键值构建的b+树索引，我们称之为非聚集索引。非聚集索引与聚集索引的区别在于非聚集索引的叶子节点不存储表中的数据，而是存储该列对应的主键，想要查找数据我们还需要根据主键再去聚集索引中进行查找，这个再根据聚集索引查找数据的过程，我们称为回表。  
明白了聚集索引和非聚集索引的定义，我们应该明白这样一句话：数据即索引，索引即数据。

利用聚集索引和非聚集索引查找数据

前面我们讲解b+树索引的时候并没有去说怎么在b+树中进行数据的查找，主要就是因为还没有引出聚集索引和非聚集索引的概念。下面我们通过讲解如何通过聚集索引以及非聚集索引查找数据表中数据的方式介绍一下b+树索引查找数据方法。

利用聚集索引查找数据

现在假设我们要查找id>=18并且id<40的用户数据。对应的sql语句为select * from user where id>=18 and id <40，其中id为主键。具体的查找过程如下：

• 1. 一般根节点都是常驻内存的，也就是说页1已经在内存中了，此时不需要到磁盘中读取数据，直接从内存中读取即可。

  从内存中读取到页1，要查找这个id>=18 and id <40或者范围值，我们首先需要找到id=18的键值。

  从页1中我们可以找到键值18，此时我们需要根据指针p2，定位到页3。

• 2. 要从页3中查找数据，我们就需要拿着p2指针去磁盘中进行读取页3。

  从磁盘中读取页3后将页3放入内存中，然后进行查找，我们可以找到键值18，然后再拿到页3中的指针p1，定位到页8。

• 3. 同样的页8页不在内存中，我们需要再去磁盘中将页8读取到内存中。

  将页8读取到内存中后。

  因为页中的数据是链表进行连接的，而且键值是按照顺序存放的，此时可以根据二分查找法定位到键值18。

  此时因为已经到数据页了，此时我们已经找到一条满足条件的数据了，就是键值18对应的数据。

  因为是范围查找，而且此时所有的数据又都存在叶子节点，并且是有序排列的，那么我们就可以对页8中的键值依次进行遍历查找并匹配满足条件的数据。

  我们可以一直找到键值为22的数据，然后页8中就没有数据了，此时我们需要拿着页8中的p指针去读取页9中的数据。

• 4. 因为页9不在内存中，就又会加载页9到内存中，并通过和页8中一样的方式进行数据的查找，直到将页12加载到内存中，发现41大于40，此时不满足条件。

  那么查找到此终止。

  最终我们找到满足条件的所有数据为：

  (18,kl),(19,kl),(22,hj),(24,io),(25,vg),(29,jk),(31,jk),(33,rt),(34,ty),(35,yu),(37,rt),(39,rt)。

  总共12条记录。

下面看下具体的查找流程图：

 利用非聚集索引查找数据

查找的流程跟聚集索引一样，这里就不详细介绍了。我们最终会找到主键值47，找到主键后我们需要再到聚集索引中查找具体对应的数据信息，此时又回到了聚集索引的查找流程。  

下面看下具体的查找流程图：

java代码实现b+树的效果

实现思路

 1.节点的结构（如下图）

        （1）键值对--key是标识；value是存储的具体数据

        （2）节点的子节点--存储的是具体的子节点

        （3）节点的后节点--标记后一个节点

        （4）节点的前节点--标记前一个节点

        （5）节点的父节点--标记父节点是哪个

2.存储的规则

2.1存储第一条数据，并标记根节点和头结点。

2.2单个节点

2.2.1.没有超过设定的阶数

2.2.2.超过阶数（分裂）

2.3一夫二子

2.3.1.没有超过设定的阶数

     因此会有下图这两种情况

结果如下图两种情况

        2.3.2超过设定的阶数

2.4一父三子

                2.4.1 三个子节点的数，要么都满，要么部分满         

2.5一父四子 

      2.5.1 四个子节点的数，要么都满，要么部分满   

具体代码实现

1、创建一个b+树的容器对象node.java

package com.bsh.test.btree;

import java.util.list;

 /*节点类*/
 public class node {

     //children
     //节点的子节点
     private list<node> nodes;
     //节点的键值对
     private list<keyandvalue> keyandvalue;
     //节点的后节点
     private node nextnode;
     //节点的前节点
     private node previousnode;
     //节点的父节点
     private node parantnode;


     public node( list<node> nodes, list<keyandvalue> keyandvalue, node nextnode,node previousnode, node parantnode) {
         this.nodes = nodes;
         this.keyandvalue = keyandvalue;
         this.nextnode = nextnode;
         this.parantnode = parantnode;
         this.previousnode = previousnode;
     }

      boolean isleaf() {
         return nodes==null;
     }

      boolean ishead() {
         return previousnode == null;
     }

      boolean istail() {
         return nextnode == null;
     }

      boolean isroot() {
         return parantnode == null;
     }


      list<node> getnodes() {
         return nodes;
     }

      void setnodes(list<node> nodes) {
         this.nodes = nodes;
     }


     list<keyandvalue> getkeyandvalue() {
         return keyandvalue;
     }


     node getnextnode() {
         return nextnode;
     }

      void setnextnode(node nextnode) {
         this.nextnode = nextnode;
     }

      node getparantnode() {
         return parantnode;
     }

      void setparantnode(node parantnode) {
         this.parantnode = parantnode;
     }

      node getpreviousnode() {
         return previousnode;
     }

      void setpreviousnode(node previousnode) {
         this.previousnode = previousnode;
     }
 }

2.创建一个数据存储对象

package com.bsh.test.btree;

import java.util.arraylist;
import java.util.collections;

public class keyandvalue implements comparable<keyandvalue>{
     /*存储索引关键字*/
     private int key;
     /*存储数据*/
     private object value;


     @override
     public int compareto(keyandvalue o) {
         //根据key的值升序排列 从小到大
         //  1  3 4 6
         //  0  1 2 3
         return this.key - o.key;
     }

     public int getkey() {
         return key;
     }

     public void setkey(int key) {
         this.key = key;
     }

     public object getvalue() {
         return value;
     }

     public void setvalue(object value) {
         this.value = value;
     }

      keyandvalue(int key, object value) {
         this.key = key;
         this.value = value;
     }
 }

3.逻辑代码

package com.bsh.test.btree;

import java.util.*;


public class btree {
    private static final string node = "node";
    static final string int = "int";
    private static final string prenode = "prenode";
    private static final string nextnode = "nextnode";
    //b+树的阶数
    private int rank;
    //根节点
    private node root;
    //头结点
    private node head;

    btree(int rank) {
        this.rank = rank;
    }

    public node getroot() {
        return root;
    }

    public void insert(keyandvalue entry) {
        list<keyandvalue> keyandvalues1 = new arraylist<>();
        //插入第一个节点
        if (head == null) {
            keyandvalues1.add(entry);
            head = new node(null, keyandvalues1, null, null, null);
            root = new node(null, keyandvalues1, null, null, null);
        } else {
            node node = head;
            //遍历链表，找到插入键值对对应的节点
            while (node != null) {
                list<keyandvalue> keyandvalues = node.getkeyandvalue();
                //   如果插入的键的值和当前节点键值对集合中的某个键的值相等，则直接替换value（相当于更新数据）
                for (keyandvalue kv : keyandvalues) {
                    if (kv.getkey() == entry.getkey()) {
                        kv.setvalue(entry.getvalue());
                        return;
                    }
                }

                //如果当前节点是最后一个节点或者要插入的键值对的键的值小于下一个节点的键的最小值，则直接插入当前节点
                if (node.getnextnode() == null || node.getnextnode().getkeyandvalue().get(0).getkey() >= entry.getkey()) {
                    splidnode(node, entry);
                    break;
                }
                //移动指针
                node = node.getnextnode();
            }
        }
    }


    //判断是否需要拆分节点
    private void splidnode(node node, keyandvalue addkeyandvalue) {
        list<keyandvalue> keyandvalues = node.getkeyandvalue();

        if (keyandvalues.size() == rank - 1) {
            //先插入待添加的节点
            keyandvalues.add(addkeyandvalue);
            //排序
            collections.sort(keyandvalues);
            //取出当前节点的键值对集合
            //取出原来的key-value集合中间位置的下标
            int mid = keyandvalues.size() / 2;
            //取出原来的key-value集合中间位置的键
            int midkey = keyandvalues.get(mid).getkey();
            //构造一个新的键值对，不是叶子节点的节点不存储value的信息
            keyandvalue midkeyandvalue = new keyandvalue(midkey, "");
            //将中间位置左边的键值对封装成集合对象
            list<keyandvalue> leftkeyandvalues = new arraylist<>();
            for (int i = 0; i < mid; i++) {
                leftkeyandvalues.add(keyandvalues.get(i));
            }
            //将中间位置右边边的键值对封装成集合对象
            list<keyandvalue> rightkeyandvalues = new arraylist<>();
            //如果是叶子节点则在原节点中保留上移的key-value，否则原节点删除上移的key-value
            int k;
            if (node.isleaf()) {
                k = mid;
            } else {
                k = mid + 1;
            }
            for (int i = k; i < rank; i++) {
                rightkeyandvalues.add(keyandvalues.get(i));
            }
            //对左右两边的元素重排序
            collections.sort(leftkeyandvalues);
            collections.sort(rightkeyandvalues);
            //以mid为界限将当前节点分列成两个节点，维护前指针和后指针
            node rightnode;
            node leftnode;
          
            //如果是叶子节点维护前后指针
            rightnode = new node(null, rightkeyandvalues, node.getnextnode(), null, node.getparantnode());
            leftnode = new node(null, leftkeyandvalues, rightnode, node.getpreviousnode(), node.getparantnode());
            rightnode.setpreviousnode(leftnode);
           
            //如果当前分裂的节点有孩子节点,设置分裂后节点和孩子节点的关系
            if (node.getnodes() != null) {
                //取得所有地孩子节点
                list<node> nodes = node.getnodes();
                list<node> leftnodes = new arraylist<>();
                list<node> rightnodes = new arraylist<>();
                for (node childnode : nodes) {
                    //取得当前孩子节点的最大键值
                    int max = childnode.getkeyandvalue().get(childnode.getkeyandvalue().size() - 1).getkey();
                    if (max < midkeyandvalue.getkey()) {
                        //小于mid处的键的数是左节点的子节点
                        leftnodes.add(childnode);
                        childnode.setparantnode(leftnode);
                    } else {
                        //大于mid处的键的数是右节点的子节点
                        rightnodes.add(childnode);
                        childnode.setparantnode(rightnode);
                    }
                }
                leftnode.setnodes(leftnodes);
                rightnode.setnodes(rightnodes);
            }

            //当前节点的前节点
            node prenode = node.getpreviousnode();
            //分裂节点后将分裂节点的前节点的后节点设置为左节点
            if (prenode != null) {
                prenode.setnextnode(leftnode);
            }

            //当前节点的后节点
            node nextnode = node.getnextnode();
            //分裂节点后将分裂节点的后节点的前节点设置为右节点
            if (nextnode != null) {
                nextnode.setpreviousnode(rightnode);
            }

            //如果由头结点分裂，则分裂后左边的节点为头节点
            if (node == head) {
                head = leftnode;
            }

            //父节点的子节点
            list<node> childnodes = new arraylist<>();
            childnodes.add(rightnode);
            childnodes.add(leftnode);
            //分裂
            //当前节点无父节点
            if (node.getparantnode() == null) {
                //父节点的键值对
                list<keyandvalue> parentkeyandvalues = new arraylist<>();
                parentkeyandvalues.add(midkeyandvalue);
                //构造父节点
                node parentnode = new node(childnodes, parentkeyandvalues, null, null, null);
                //将子节点与父节点关联
                rightnode.setparantnode(parentnode);
                leftnode.setparantnode(parentnode);
                //当前节点为根节点
                root = parentnode;
            } else {
                node parentnode = node.getparantnode();
                //将原来的孩子节点（除了被拆分的节点）和新的孩子节点（左孩子和右孩子）合并之后与父节点关联
                childnodes.addall(parentnode.getnodes());
                //移除正在被拆分的节点
                childnodes.remove(node); // 为什么要移除node？
                //将子节点与父节点关联
                parentnode.setnodes(childnodes);
                rightnode.setparantnode(parentnode);
                leftnode.setparantnode(parentnode);
                if (parentnode.getparantnode() == null) {
                    root = parentnode;
                }
                //当前节点有父节点,递归调用拆分的方法,将父节点拆分
                splidnode(parentnode, midkeyandvalue);

            }
        } else {
            keyandvalues.add(addkeyandvalue);
            //排序
            collections.sort(keyandvalues);
        }
    }


    //打印b+树
    void printbtree(node root) {
        if (root == this.root) {
            //打印根节点内的元素
            printnode(root);
            system.out.println();
        }
        if (root == null) {
            return;
        }

        //打印子节点的元素
        if (root.getnodes() != null) {
            //找到最左边的节点
            node leftnode = null;
            node tmpnode = null;
            list<node> childnodes = root.getnodes();
            for (node node : childnodes) {
                if (node.getpreviousnode() == null) {
                    leftnode = node;
                    tmpnode = node;
                }
            }

            while (leftnode != null) {
                //从最左边的节点向右打印
                printnode(leftnode);
                system.out.print("|");
                leftnode = leftnode.getnextnode();
            }
            system.out.println();
            printbtree(tmpnode);
        }
    }

    //打印一个节点内的元素
    private void printnode(node node) {
        list<keyandvalue> keyandvalues = node.getkeyandvalue();
        for (int i = 0; i < keyandvalues.size(); i++) {
            if (i != (keyandvalues.size() - 1)) {
                system.out.print(keyandvalues.get(i).getkey() + ",");
            } else {
                system.out.print(keyandvalues.get(i).getkey());
            }
        }
    }

    public object search(int key, node node, string mode) {

        //如果是叶子节点则直接取值
        if (node.isleaf()) {
            list<keyandvalue> keyandvalues = node.getkeyandvalue();
            for (keyandvalue keyandvalue : keyandvalues) {
                if (keyandvalue.getkey() == key) {
                    switch (mode) {
                        case node:
                            return node;
                        case int:
                            return keyandvalue.getvalue();
                    }
                }
            }
            return null;
        }


        list<node> nodes = node.getnodes();
        //如果寻找的key小于节点的键的最小值
        int minkey = node.getkeyandvalue().get(0).getkey();
        if (key < minkey) {
            for (node n : nodes) {
                list<keyandvalue> keyandvalues = n.getkeyandvalue();
                //找到子节点集合中最大键小于父节点最小键节点
                if (keyandvalues.get(keyandvalues.size() - 1).getkey() < minkey) {
                    return search(key, n, mode);
                }
            }
        }
        //如果寻找的key大于节点的键的最大值
        int maxkey = getmaxkeyinnode(node);
        if (key >= maxkey) {
            for (node n : nodes) {
                list<keyandvalue> keyandvalues = n.getkeyandvalue();
                //找到子节点集合中最小键大于等于父节点最小大键节点
                if (keyandvalues.get(0).getkey() >= maxkey) {
                    return search(key, n, mode);
                }
            }
        }

        //如果寻找的key在最大值和最小值之间，首先定位到最窄的区间
        int min = getleftboundofkey(node, key);
        int max = getrightboundofkey(node, key);


        //去所有的子节点中找键的范围在min和max之间的节点
        for (node n : nodes) {
            list<keyandvalue> kvs = n.getkeyandvalue();
            //找到子节点集合中键的范围在min和max之间的节点
            if (kvs.get(0).getkey() >= min && kvs.get(kvs.size() - 1).getkey() < max) {
                return search(key, n, mode);
            }
        }
        return null;
    }


    public boolean delete(int key) {
        system.out.println("delete:" + key);
        system.out.println();

        //首先找到要删除的key所在的节点
        node deletenode = (node) search(key, root, node);
        //如果没找到则删除失败
        if (deletenode == null) {
            return false;
        }

        if (deletenode == root) {
            delkeyandvalue(root.getkeyandvalue(), key);
            return true;
        }

        if (deletenode == head && isneedmerge(head)) {
            head = head.getnextnode();
        }

        return merge(deletenode, key);
    }


    //平衡当前节点和前节点或者后节点的数量，使两者的数量都满足条件
    private boolean balancenode(node node, node brathernode, string nodetype) {
        if (brathernode == null) {
            return false;
        }
        list<keyandvalue> delkeyandvalues = node.getkeyandvalue();
        if (ismoreelement(brathernode)) {
            list<keyandvalue> bratherkeyandvalues = brathernode.getkeyandvalue();
            int brathersize = bratherkeyandvalues.size();
            //兄弟节点删除挪走的键值对
            keyandvalue keyandvalue = null;
            keyandvalue keyandvalue1;
            switch (nodetype) {
                case prenode:
                    keyandvalue = bratherkeyandvalues.remove(brathersize - 1);
                    keyandvalue1 = getkeyandvalueinminandmax(node.getparantnode(), keyandvalue.getkey(), getminkeyinnode(node));
                    keyandvalue1.setkey(keyandvalue.getkey());
                    break;
                case nextnode:
                    keyandvalue = bratherkeyandvalues.remove(0);
                    keyandvalue1 = getkeyandvalueinminandmax(node.getparantnode(), getmaxkeyinnode(node), keyandvalue.getkey());
                    keyandvalue1.setkey(bratherkeyandvalues.get(0).getkey());
                    break;
            }
            //当前节点添加从前一个节点得来的键值对
            delkeyandvalues.add(keyandvalue);

            //对键值对重排序
            collections.sort(delkeyandvalues);
            return true;
        }
        return false;
    }

    public boolean merge(node node, int key) {
        list<keyandvalue> delkeyandvalues = node.getkeyandvalue();
        //首先删除该key-vaule
        delkeyandvalue(delkeyandvalues, key);
        //如果要删除的节点的键值对的数目小于节点最大键值对数目*填充因子
        if (isneedmerge(node)) {
            boolean isbalance;
            //如果左节点有富余的键值对，则取一个到当前节点
            node prenode = getpreviousnode(node);
            isbalance = balancenode(node, prenode, prenode);
            //如果此时已经平衡，则已经删除成功
            if (isbalance) return true;

            //如果右兄弟节点有富余的键值对，则取一个到当前节点
            node nextnode = getnextnode(node);
            isbalance = balancenode(node, nextnode, nextnode);

            return isbalance || mergenode(node, key);
        } else {
            return true;
        }
    }

    //合并节点
    //key 待删除的key
    private boolean mergenode(node node, int key) {
        if (node.isroot()) {
            return false;
        }
        node prenode;
        node nextnode;
        node parentnode = node.getparantnode();
        list<node> childnodes = parentnode.getnodes();
        list<node> childnodes1 = node.getnodes();
        list<keyandvalue> parentkeyandvalue = parentnode.getkeyandvalue();
        list<keyandvalue> keyandvalues = node.getkeyandvalue();

        if (node.isleaf()) {
            if (parentkeyandvalue.size() == 1 && parentnode != root) {
                return true;
            }
            prenode = getpreviousnode(node);
            nextnode = getnextnode(node);
            if (prenode != null) {
                list<keyandvalue> prekeyandvalues = prenode.getkeyandvalue();
                keyandvalues.addall(prekeyandvalues);
                if (prenode.ishead()) {
                    head = node;
                    node.setpreviousnode(null);
                } else {
                    prenode.getpreviousnode().setnextnode(node);
                    node.setpreviousnode(prenode.getpreviousnode());
                }
                //将合并后节点的后节点设置为当前节点的后节点
                prenode.setnextnode(node.getnextnode());
                keyandvalue keyandvalue = getkeyandvalueinminandmax(parentnode, getminkeyinnode(prenode), key);
                delkeyandvalue(parentkeyandvalue, keyandvalue.getkey());
                if (parentkeyandvalue.isempty()) {
                    root = node;
                } else {
                    //删除当前节点
                    childnodes.remove(prenode);
                }
                collections.sort(keyandvalues);
                merge(parentnode, key);
                return true;
            }

            if (nextnode != null) {
                list<keyandvalue> nextkeyandvalues = nextnode.getkeyandvalue();
                keyandvalues.addall(nextkeyandvalues);
                if (nextnode.istail()) {
                    node.setpreviousnode(null);
                } else {
                    nextnode.getnextnode().setpreviousnode(node);
                    node.setnextnode(nextnode.getnextnode());
                }

                keyandvalue keyandvalue = getkeyandvalueinminandmax(parentnode, key, getminkeyinnode(nextnode));
                delkeyandvalue(parentkeyandvalue, keyandvalue.getkey());
                if (parentkeyandvalue.isempty()) {
                    root = node;
                    node.setparantnode(null);
                } else {
                    //删除当前节点
                    childnodes.remove(nextnode);
                }
                collections.sort(keyandvalues);
                merge(parentnode, key);
                return true;
            }
            //前节点和后节点都等于null那么是root节点
            return false;
        } else {
            prenode = getpreviousnode(node);
            nextnode = getnextnode(node);
            if (prenode != null) {
                //将前一个节点和当前节点还有父节点中的相应key-value合并
                list<keyandvalue> prekeyandvalues = prenode.getkeyandvalue();
                prekeyandvalues.addall(keyandvalues);
                int min = getmaxkeyinnode(prenode);
                int max = getminkeyinnode(node);
                //父节点中移除这个key-value
                keyandvalue keyandvalue = getkeyandvalueinminandmax(parentnode, min, max);
                parentkeyandvalue.remove(keyandvalue);
                if (parentkeyandvalue.isempty()) {
                    root = prenode;
                    node.setparantnode(null);
                    prenode.setparantnode(null);
                } else {
                    childnodes.remove(node);
                }
                assert nextnode != null;
                prenode.setnextnode(nextnode.getnextnode());
                //前节点加上一个当前节点的所有子节点中最小key的key-value
                keyandvalue minkeyandvalue = getminkeyandvalueinchildnode(node);
                assert minkeyandvalue != null;
                keyandvalue keyandvalue1 = new keyandvalue(minkeyandvalue.getkey(), minkeyandvalue.getvalue());
                prekeyandvalues.add(keyandvalue1);
                list<node> prechildnodes = prenode.getnodes();
                prechildnodes.addall(node.getnodes());
                //将当前节点的孩子节点的父节点设为当前节点的后节点
                for (node node1 : childnodes1) {
                    node1.setparantnode(prenode);
                }
                collections.sort(prekeyandvalues);
                merge(parentnode, key);
                return true;
            }

            if (nextnode != null) {
                //将后一个节点和当前节点还有父节点中的相应key-value合并
                list<keyandvalue> nextkeyandvalues = nextnode.getkeyandvalue();
                nextkeyandvalues.addall(keyandvalues);

                int min = getmaxkeyinnode(node);
                int max = getminkeyinnode(nextnode);
                //父节点中移除这个key-value
                keyandvalue keyandvalue = getkeyandvalueinminandmax(parentnode, min, max);
                parentkeyandvalue.remove(keyandvalue);
                childnodes.remove(node);
                if (parentkeyandvalue.isempty()) {
                    root = nextnode;
                    nextnode.setparantnode(null);
                } else {
                    childnodes.remove(node);
                }
                nextnode.setpreviousnode(node.getpreviousnode());
                //后节点加上一个当后节点的所有子节点中最小key的key-value
                keyandvalue minkeyandvalue = getminkeyandvalueinchildnode(nextnode);
                assert minkeyandvalue != null;
                keyandvalue keyandvalue1 = new keyandvalue(minkeyandvalue.getkey(), minkeyandvalue.getvalue());
                nextkeyandvalues.add(keyandvalue1);
                list<node> nextchildnodes = nextnode.getnodes();
                nextchildnodes.addall(node.getnodes());
                //将当前节点的孩子节点的父节点设为当前节点的后节点
                for (node node1 : childnodes1) {
                    node1.setparantnode(nextnode);
                }
                collections.sort(nextkeyandvalues);
                merge(parentnode, key);
                return true;
            }
            return false;
        }
    }

    //得到当前节点的前节点
    private node getpreviousnode(node node) {
        if (node.isroot()) {
            return null;
        }

        node parentnode = node.getparantnode();
        //得到兄弟节点
        list<node> nodes = parentnode.getnodes();
        list<keyandvalue> keyandvalues = new arraylist<>();
        for (node n : nodes) {
            list<keyandvalue> list = n.getkeyandvalue();
            int maxkeyandvalue = list.get(list.size() - 1).getkey();
            if (maxkeyandvalue < getminkeyinnode(node)) {
                keyandvalues.add(new keyandvalue(maxkeyandvalue, n));
            }
        }
        collections.sort(keyandvalues);
        if (keyandvalues.isempty()) {
            return null;
        }
        return (node) keyandvalues.get(keyandvalues.size() - 1).getvalue();
    }


    //得到当前节点的后节点
    private node getnextnode(node node) {
        if (node.isroot()) {
            return null;
        }

        node parentnode = node.getparantnode();
        //得到兄弟节点
        list<node> nodes = parentnode.getnodes();
        list<keyandvalue> keyandvalues = new arraylist<>();
        for (node n : nodes) {
            list<keyandvalue> list = n.getkeyandvalue();
            int minkeyandvalue = list.get(0).getkey();
            if (minkeyandvalue > getmaxkeyinnode(node)) {
                keyandvalues.add(new keyandvalue(minkeyandvalue, n));
            }
        }
        collections.sort(keyandvalues);
        if (keyandvalues.isempty()) {
            return null;
        }
        return (node) keyandvalues.get(0).getvalue();
    }


    private int getminkeyinnode(node node) {
        list<keyandvalue> keyandvalues = node.getkeyandvalue();
        return keyandvalues.get(0).getkey();
    }

    private int getmaxkeyinnode(node node) {
        list<keyandvalue> keyandvalues = node.getkeyandvalue();
        return keyandvalues.get(keyandvalues.size() - 1).getkey();
    }


    private int getleftboundofkey(node node, int key) {
        int left = 0;
        list<keyandvalue> keyandvalues = node.getkeyandvalue();
        for (int i = 0; i < keyandvalues.size(); i++) {
            if (keyandvalues.get(i).getkey() <= key && keyandvalues.get(i + 1).getkey() > key) {
                left = keyandvalues.get(i).getkey();
                break;
            }
        }
        return left;
    }

    private int getrightboundofkey(node node, int key) {
        int right = 0;
        list<keyandvalue> keyandvalues = node.getkeyandvalue();
        for (int i = 0; i < keyandvalues.size(); i++) {
            if (keyandvalues.get(i).getkey() <= key && keyandvalues.get(i + 1).getkey() > key) {
                right = keyandvalues.get(i + 1).getkey();
                break;
            }
        }
        return right;
    }


    private void delkeyandvalue(list<keyandvalue> keyandvalues, int key) {
        for (keyandvalue keyandvalue : keyandvalues) {
            if (keyandvalue.getkey() == key) {
                keyandvalues.remove(keyandvalue);
                break;
            }
        }
    }

    //找到node的键值对中在min和max中的键值对
    private keyandvalue getkeyandvalueinminandmax(node node, int min, int max) {
        if (node == null) {
            return null;
        }
        list<keyandvalue> keyandvalues = node.getkeyandvalue();
        keyandvalue keyandvalue = null;
        for (keyandvalue k : keyandvalues) {
            if (k.getkey() > min && k.getkey() <= max) {
                keyandvalue = k;
                break;
            }
        }
        return keyandvalue;
    }

    private keyandvalue getminkeyandvalueinchildnode(node node) {
        if (node.getnodes() == null || node.getnodes().isempty()) {
            return null;
        }
        list<keyandvalue> sortkeyandvalues = new arraylist<>();
        list<node> childnodes = node.getnodes();
        for (node childnode : childnodes) {
            list<keyandvalue> keyandvalues = childnode.getkeyandvalue();
            keyandvalue minkeyandvalue = keyandvalues.get(0);
            sortkeyandvalues.add(minkeyandvalue);
        }
        collections.sort(sortkeyandvalues);
        return sortkeyandvalues.get(0);
    }

    private boolean isneedmerge(node node) {
        if (node == null) {
            return false;
        }
        list<keyandvalue> keyandvalues = node.getkeyandvalue();
        return keyandvalues.size() < rank / 2;
    }

    //判断一个节点是否有富余的键值对
    private boolean ismoreelement(node node) {

        return node != null && (node.getkeyandvalue().size() > rank / 2);
    }
}

4.

package com.sbxbase.testbtree;

public class testmain {
    public static void main(string[] args) {
        btree btree = new btree(4);//初始化了b+树的阶数
     
        btree.insert( new keyandvalue(1, "123"));
        btree.insert(new keyandvalue(6, "123"));
        btree.insert(new keyandvalue(10, "123"));
        btree.insert(new keyandvalue(2, "123"));
        btree.insert(new keyandvalue(8, "546"));
        btree.insert(new keyandvalue(11, "123"));
        btree.insert(new keyandvalue(18, "12345"));
        btree.insert(new keyandvalue(3, "123"));
        btree.insert(new keyandvalue(15, "12345"));
        btree.insert(new keyandvalue(17, "12345"));
        btree.insert(new keyandvalue(12, "123"));
        btree.insert(new keyandvalue(13, "123"));
        btree.insert(new keyandvalue(4, "123"));
        btree.insert(new keyandvalue(9, "123"));
        btree.insert(new keyandvalue(19, "12345"));
        btree.insert(new keyandvalue(16, "12345"));
        btree.insert(new keyandvalue(5, "123"));
        btree.insert(new keyandvalue(20, "12345"));
        btree.insert(new keyandvalue(7, "12300"));
        btree.insert(new keyandvalue(21, "12345"));

        btree.printbtree(btree.getroot());

        btree.delete(1);
        btree.printbtree(btree.getroot());

        btree.delete(0);
        btree.printbtree(btree.getroot());

        btree.delete(2);
        btree.printbtree(btree.getroot());

        btree.delete(11);
        btree.printbtree(btree.getroot());


    }

}