B-Tree插入、删除的Java实现

一、一颗非空m阶B-Tree的性质

1. 除根结点以外的每个结点的孩子引用最多存在m个，关键码最多存在m - 1个；除根结点以外的每个结点的孩子引用至少存在⌈m / 2⌉个，关键码至少存在⌈m / 2⌉ - 1个。

2. 一颗非空B-Tree的根结点至少存在2个孩子引用（注意：一颗非空B-Tree的根结点最少存在的孩子引用数不受m限制，且最少允许存在2个孩子引用！）。

3. 每个结点的关键码遵循“左小右大”排序存放，即关键码集合中靠左的关键码小于靠右侧的关键码。

4. 所有叶子结点存在同一层（可以看出B-Tree是一种严格平衡的多路搜索树）。

package wind.wdb;import java.util.Arrays;import java.util.Comparator;import java.util.Random;/**
 * B-Tree
 * @param <K>
 */public final class MultipleSearchTree<K> {
    /**
     * B-Tree Node
     * @param <K>
     */
    private static final class BTreeNode<K> {
        K[] key;                    // 关键码数组
        BTreeNode<K> parent;        // 父结点
        BTreeNode<K>[] ptr;         // 孩子结点数组
        int ptrSize;                // 实际存在的孩子数量

        BTreeNode(int order) {
            // 关键码数组和指针数组都多分配一个存储空间 避免发生上溢时数组访问越界
            this.key        = (K[])new Object[order];
            this.parent     = null;
            this.ptr        = new BTreeNode[order + 1];
            this.ptrSize    = 1;                            // 默认至少拥有一个空孩子
        }
    }

    private static final int FIELD_LIMIT_ORDER_MINIMUM  = 3;            // 阶数字段所允许的最小取值
    private static final int FIELD_LIMIT_ORDER_MAXIMUM  = 65535;        // 阶数字段所允许的最大取值
    private static final int FIELD_DEFAULT_ORDER        = 4;            // 阶数字段默认取值

    private final Comparator<? super K> comparator;         // 关键码比较器
    private final int order;                                // 阶数
    private BTreeNode<K> root;                              // 树根
    private int keySize;                                    // 存储的关键码数

    public MultipleSearchTree(Comparator<? super K> comparator) {
        checkComparator(comparator);
        this.comparator = comparator;
        this.order = FIELD_DEFAULT_ORDER;
    }

    public MultipleSearchTree(int order, Comparator<? super K> comparator) {
        checkComparator(comparator);
        checkOrder(order);
        this.comparator = comparator;
        this.order = order;
    }


    /**
     * 阶数检查
     * @param order
     */
    private static void checkOrder(int order) {
        if (order < FIELD_LIMIT_ORDER_MINIMUM) {
            System.out.println("阶数的取值过小，最小的阶数取值不能小于" + FIELD_LIMIT_ORDER_MINIMUM + "！");
        } else if (order > FIELD_LIMIT_ORDER_MAXIMUM) {
            System.out.println("阶数的取值过大，最小的阶数取值不能大于" + FIELD_LIMIT_ORDER_MAXIMUM + "！");
        }
    }


    /**
     * 比较器检查
     * @param comparator
     * @param <K>
     */
    private static <K> void checkComparator(Comparator<? super K> comparator) {
        if (comparator == null) {
            throw new NullPointerException("关键码比较器不能为空！");
        }
    }


    /**
     * 移除关键码
     * @param key
     * @return 移除成功返回true，否则返回false。
     */
    public boolean remove(K key) {
        if (key == null || this.root == null) {
            return false;
        }

        final Comparator<? super K> comparator = this.comparator;
        BTreeNode<K> delItr = this.root;    // 关键码搜索器
        int delPos          = 0;            // delItr.key[delPos]即为要删除的关键码

        do {
            delPos = Arrays.binarySearch(delItr.key, 0, delItr.ptrSize - 1, key, comparator);

            if (delPos < 0) {
                // 不断深入
                delItr = delItr.ptr[~delPos];
            } else {
                break;
            }
        } while (delItr != null);
        // 关键码不存在   故无法删除
        if (delItr == null) return false;
        // 若关键码所在结点存在直接后继   则将实际删除关键码的结点替换为直接后继
        if (delItr.ptr[delPos + 1] != null) {
            BTreeNode<K> original   = delItr;

            delItr                  = delItr.ptr[delPos + 1];
            while (delItr.ptr[0] != null) {
                delItr = delItr.ptr[0];
            }
            original.key[delPos]    = delItr.key[0];
            delPos                  = 0;
        }
        // 移除关键码
        System.arraycopy(delItr.key, delPos + 1, delItr.key, delPos, (delItr.ptrSize - 1) - (delPos + 1));
        // 此处不必移动孩子数组进行覆盖删除 因为删除必然发生在外部结点   故移动空结点是耗时且无意义的
        // 更新属性
        delItr.ptrSize--;
        // 若发生了下溢则有必要进行修复
        if (delItr.ptrSize < Math.ceil(this.order / 2)) {
            fixUnderflow(delItr);
        }

        this.keySize--;

        return true;
    }


    /**
     * 下溢修复
     * @param fixItr
     */
    private void fixUnderflow(BTreeNode<K> fixItr) {
        final Comparator<? super K> comparator = this.comparator;

        while (fixItr.ptrSize < Math.ceil(this.order / 2)) {
            BTreeNode<K> parent = fixItr.parent;

            // 若已上升至根节点
            if (parent == null) {
                // 对于根节点而言不必满足至少拥有ceil(m/2)个孩子
                if (fixItr.ptrSize < 2 && fixItr.ptr[0] != null) {
                    this.root           = fixItr.ptr[0];
                    this.root.parent    = null;
                }
                return;
            }

            int fixItrPos = 0;

            // 定位fixItr是其父亲的第几个孩子（下标）
            while (parent.ptr[fixItrPos] != fixItr) {
                ++fixItrPos;
            }


            /*
             * 注意：这里判断fixItrPos不是一个最左侧孩子又或者不是最右侧孩子的目的是为了防止关键码数组parent.key访问越界！
             * 就以下面这个分支"if (0 < fixItrPos)"为例。
             * 假设此时左兄弟的关键码数量恰好满足"leftSibling.ptrSize - 1 >= Math.ceil(this.order / 2)"
             * 对于这种情况的修复很简单：
             *      1、将介于左兄弟leftSibling和fixItr的父节点关键码借给fixItr
             *      2、将左兄弟的最大（最右侧）的关键码填补父节点借出关键码的位置
             *      3、最后将左兄弟的最右侧孩子结点转移至fixItr作为最左侧孩子即可！
             * 但关键就在于第1步的“介于左兄弟leftSibling和fixItr的父节点关键码”的选取
             * 貌似咋看好像是parent.key[fixItrPos - 1]和parent.key[fixItrPos]
             * 都可以作为中间关键码的选取？？但其实并不是    简单思索便可很清楚的知道
             * 如果此时我们的fixItrPos恰好指向的位置是一个最右侧的关键码，而此时如果我们使用[fixItrPos]
             * 对parent.key进行访问就会恰好超出关键码的最大数组范围一个元素位置，从而引发数组访问越界异常！
             * 因此只能是选取parent.key[fixItrPos - 1]作为介于两者之间的中间关键码！
             * 即使fixItrPos是这个分支所允许的最小值，那也最小只可能是1。
             * 也就是说其左兄弟是parent.ptr[0]，此时若使用parent.key[fixItrPos - 1]
             * 取中间关键码那也只会取到最靠左侧的关键码，不会发生越界情况！
             * （下面的“if (fixItrPos < parent.ptrSize - 1)”情况是对称的，同理！主要是为了防止访问越界！）
             */
            // fixItr不是一个最左侧孩子
            if (0 < fixItrPos) {
                BTreeNode<K> leftSibling = parent.ptr[fixItrPos - 1];

                // 若关键码充足
                if (leftSibling.ptrSize - 1 >= Math.ceil(this.order / 2)) {
                    // 父亲借出关键码给fixItr
                    System.arraycopy(fixItr.key, 0, fixItr.key, 1, fixItr.ptrSize - 1);
                    fixItr.key[0] = parent.key[fixItrPos - 1];

                    // 左兄弟的最大关键码填补父亲借出的关键码位置
                    parent.key[fixItrPos - 1] = leftSibling.key[(leftSibling.ptrSize - 1) - 1];

                    // 左兄弟多出的最右侧关键码转移至fixItr
                    System.arraycopy(fixItr.ptr, 0, fixItr.ptr, 1, fixItr.ptrSize);
                    fixItr.ptr[0] = leftSibling.ptr[leftSibling.ptrSize - 1];
                    if (fixItr.ptr[0] != null) {
                        fixItr.ptr[0].parent = fixItr;
                    }

                    // 更新属性
                    fixItr.ptrSize++;
                    leftSibling.ptrSize--;

                    return;
                }
            }

            // fixItr不是一个最右侧孩子
            if (fixItrPos < parent.ptrSize - 1) {
                BTreeNode<K> rightSibling = parent.ptr[fixItrPos + 1];

                if (rightSibling.ptrSize - 1 >= Math.ceil(this.order / 2)) {
                    // 父亲借出关键码给fixItr
                    fixItr.key[fixItr.ptrSize - 1] = parent.key[fixItrPos];

                    // 右兄弟的最小关键码填补父亲借出的关键码位置
                    parent.key[fixItrPos] = rightSibling.key[0];
                    System.arraycopy(rightSibling.key, 1, rightSibling.key, 0, (rightSibling.ptrSize - 1) - 1);

                    // 右兄弟多出的最左侧孩子转移至fixItr
                    fixItr.ptr[fixItr.ptrSize] = rightSibling.ptr[0];
                    System.arraycopy(rightSibling.ptr, 1, rightSibling.ptr, 0, rightSibling.ptrSize - 1);
                    if (fixItr.ptr[fixItr.ptrSize] != null) {
                        fixItr.ptr[fixItr.ptrSize].parent = fixItr;
                    }

                    // 更新属性
                    fixItr.ptrSize++;
                    rightSibling.ptrSize--;

                    return;
                }
            }

            if (0 < fixItrPos) {
                BTreeNode<K> leftSibling = parent.ptr[fixItrPos - 1];

                // 父节点关键码转移至左兄弟末尾
                leftSibling.key[leftSibling.ptrSize - 1] = parent.key[fixItrPos - 1];
                System.arraycopy(parent.key, fixItrPos, parent.key, fixItrPos - 1, (parent.ptrSize - 1) - fixItrPos);

                // 将fixItr从parent的孩子集合中移除
                System.arraycopy(parent.ptr, fixItrPos + 1, parent.ptr, fixItrPos, parent.ptrSize - (fixItrPos + 1));
                // 更新属性
                parent.ptrSize--;

                // 将fixItr的全部关键码转移至左兄弟
                System.arraycopy(fixItr.key, 0, leftSibling.key, leftSibling.ptrSize, fixItr.ptrSize - 1);

                // 将fixItr的全部孩子转移至左兄弟
                if (fixItr.ptr[0] != null) {
                    System.arraycopy(fixItr.ptr, 0, leftSibling.ptr, leftSibling.ptrSize, fixItr.ptrSize);
                    for (int i = 0; i < fixItr.ptrSize; ++i) {
                        fixItr.ptr[i].parent = leftSibling;
                    }
                }

                // 更新属性
                leftSibling.ptrSize += fixItr.ptrSize;
            } else {
                BTreeNode<K> rightSibling = parent.ptr[fixItrPos + 1];

                // 父节点转移关键码至fixItr
                fixItr.key[fixItr.ptrSize - 1] = parent.key[fixItrPos];
                System.arraycopy(parent.key, fixItrPos + 1, parent.key, fixItrPos, (parent.ptrSize - 1) - (fixItrPos + 1));

                // 将rs从parent的孩子集合中移除
                System.arraycopy(parent.ptr, fixItrPos + 2, parent.ptr, fixItrPos + 1, parent.ptrSize - (fixItrPos + 2));
                // 更新属性
                parent.ptrSize--;

                // 将右兄弟的全部关键码转移至fixItr
                System.arraycopy(rightSibling.key, 0, fixItr.key, fixItr.ptrSize, rightSibling.ptrSize - 1);

                // 将右兄弟的全部孩子转移至fixItr
                if (rightSibling.ptr[0] != null) {
                    System.arraycopy(rightSibling.ptr, 0, fixItr.ptr, fixItr.ptrSize, rightSibling.ptrSize);
                    for (int i = 0; i < rightSibling.ptrSize; ++i) {
                        rightSibling.ptr[i].parent = fixItr;
                    }
                }

                // 更新属性
                fixItr.ptrSize += rightSibling.ptrSize;
            }

            // 上溯
            fixItr = parent;
        }
    }


    /**
     * 添加新的关键码
     * @param key 添加的关键码
     * @return 添加成功返回true，否则返回false。
     */
    public boolean add(K key) {
        // 若key先前并不存在当前B-Tree中  则必然会添加成功
        if (key == null) {
            return false;
        } else if (this.root != null) {
            final Comparator<? super K> comparator  = this.comparator;
            BTreeNode<K> iterator                   = this.root;
            BTreeNode<K> insert                     = null;
            int insPos                                 = 0;

            do {
                insPos = Arrays.binarySearch(iterator.key, 0, iterator.ptrSize - 1, key, comparator);

                if (insPos < 0) {
                    // 不断深入 并由insert记录最终的插入结点
                    insert      = iterator;
                    iterator    = iterator.ptr[~insPos];
                } else {
                    // 若找到key已存在当前B-Tree中则中断插入操作
                    return false;
                }
            } while (iterator != null);
            // 取得正确的关键码插入位置
            insPos = ~insPos;
            // 将insert.key[insPos]起始的往后关键码整体向后移动一位  空出[insPos]位置供插入使用
            System.arraycopy(insert.key, insPos, insert.key, insPos + 1, (insert.ptrSize - 1) - insPos);
            insert.key[insPos] = key;
            // 此处无需将insert.ptr[insPos + 1]起始的往后关键码整体向后移动    因为插入必然发生在外部结点   移动空孩子无意义且费效率
            insert.ptrSize++;
            // 若有需要需进行上溢修复
            if (insert.ptrSize > this.order) {
                fixOverflow(insert);
            }
        } else {
            this.root           = new BTreeNode<>(this.order);
            this.root.key[0]    = key;
            this.root.ptrSize   = 2;
        }

        this.keySize++;

        return true;
    }

    /**
     * 上溢修复
     * @param fixItr
     */
    private final void fixOverflow(BTreeNode<K> fixItr) {
        final Comparator<? super K> comparator = this.comparator;

        while (fixItr.ptrSize > this.order) {
            BTreeNode<K> parent = fixItr.parent;                    // 父亲
            BTreeNode<K> right  = new BTreeNode<>(this.order);      // 分裂出来的右孩子
            int midKeyIndex     = (fixItr.ptrSize - 1) >> 1;        // fixItr.key的中间关键码位置下标

            // fixItr.key[midKeyIndex]作为被提升至父节点的关键码
            // fixItr.key从[midKeyIndex + 1]起始的关键码全部转移至right.key
            System.arraycopy(fixItr.key, midKeyIndex + 1, right.key, 0, (fixItr.ptrSize - 1) - (midKeyIndex + 1));
            // fixItr.ptr从[midKeyIndex + 1]起始的孩子全部转移至right.ptr
            if (fixItr.ptr[0] != null) {
                System.arraycopy(fixItr.ptr, midKeyIndex + 1, right.ptr, 0, fixItr.ptrSize - (midKeyIndex + 1));
                // 重定向父亲引用
                for (int i = midKeyIndex + 1; i < fixItr.ptrSize; ++i) {
                    fixItr.ptr[i].parent = right;
                }
            }
            // 更新属性
            right.ptrSize   = fixItr.ptrSize - (midKeyIndex + 1);
            fixItr.ptrSize  -= right.ptrSize;

            // 若发生上溢的是根节点
            if (parent == null) {
                this.root           = new BTreeNode<>(this.order);
                this.root.key[0]    = fixItr.key[midKeyIndex];
                this.root.ptr[0]    = fixItr;
                this.root.ptr[1]    = right;
                fixItr.parent       = this.root;
                right.parent        = this.root;
                // 更新属性
                this.root.ptrSize   = 2;
                return;
            }

            // 若发生上溢的非根节点
            // 确定中间关键码在parent.key中的提升位置
            int risePos = ~Arrays.binarySearch(parent.key, 0, parent.ptrSize - 1, fixItr.key[midKeyIndex], comparator);

            // 腾出parent.key[risePos]以供存储提升的关键码
            System.arraycopy(parent.key, risePos, parent.key, risePos + 1, (parent.ptrSize - 1) - risePos);
            parent.key[risePos]     = fixItr.key[midKeyIndex];
            // 腾出parent.ptr[risePos + 1]以供存储分裂出来的右孩子
            System.arraycopy(parent.ptr, risePos + 1, parent.ptr, risePos + 2, parent.ptrSize - (risePos + 1));
            parent.ptr[risePos + 1] = right;
            right.parent            = parent;
            // 更新属性
            parent.ptrSize++;

            // 上溯
            fixItr = parent;
        }
    }}final class Run {
    public static void main(String[] args) {
        MultipleSearchTree<Double> bTree    = new MultipleSearchTree<>(4, Double::compareTo);
        Random random                       = new Random();
        Double[] key                        = new Double[100000];

        for (int j = 0; j < 100; ++j) {
            for (int i = 0; i < key.length; ++i) {
                key[i] = random.nextDouble();
            }
            for (int i = 0; i < key.length; ++i) {
                System.out.print("第" + (i + 1) + "轮：");
                System.out.println(bTree.add(key[i]) ? "插入成功" : "插入失败");
            }
            for (int i = 0; i < key.length; ++i) {
                System.out.print("第" + (i + 1) + "轮：");
                System.out.println(bTree.remove(key[i]) ? "删除成功" : "删除失败");
            }
        }
    }}