圖解B樹

引言

今天去面試

面試官：mysql資料庫索引這麼快，知道是通過什麼實作的嗎？

我(一臉懵逼)：不知道

面試官淡淡的說：你心裡有沒有點B數概念？

我：(擦，不就是不知道嗎，用得着罵人嗎)

當場站起來走了，回去搜了一下，才知道面試官問我知不知道B-樹。

今天我們要介紹的就是B樹，看完這篇文章之後，我相信你心裡一定有B樹了。

B樹也稱B-樹,它是一顆平衡的多路搜尋樹。我們描述一顆B樹時需要指定它的階數，階數表示一個節點最多有多少個孩子節點，一般用字母m表示階數。當m取2時，就是我們常見的二叉搜尋樹。

有時也稱M路B樹，即有M個分支的B樹

多級存儲系統中使用B-樹，可針對外部查找，大大減少I/O次數。

上圖就是一顆典型的B樹。

B樹的本質是二叉搜尋樹，如果把B樹中的節點稱為超級節點的話，那麼每個超級節點可以看成是若幹個二叉節點經過适當的合并得到的。比如上圖，每兩代二叉節點合并成一個超級節點，每個超級節點中有3個關鍵碼，有4條分支。

合并後的結果如圖所示，這就是一顆4路B樹，也可稱為(2,4)樹

特性

一顆m階的B樹特性如下：

• 内部各節點有：

1. 不超過m-1個關鍵碼：, n個
2. 不超過m個分支：, n+1個

• 内部節點的分支數n+1有：

1. 樹根：(注：樹根也有可能沒有任何分支)
2. 其他節點：( ⌈m/2⌉表示向上取整，比如3/2=2,java中可以簡單的通過​​

   ​(3+1)/2​

   ​來實作)

• 所有葉子節點位于同一層(所有葉子節點深度相等)；

完整的表示一顆B樹如下：

為了簡便，我們省略外部節點與引用節點，如下這樣描述一顆B樹：

這樣就可以很緊湊的表示一顆B樹了。

實作

結構

我們來觀察某一個節點的結構，可以發現，其中有n個關鍵碼以及n+1個分支，m=n+1。

是以，不難了解用兩個類似清單的結構就可以表示它們。這麼我們用自定義資料結構​

​Vector​

​來表示它們。它的實作在本文末尾。

○表示關鍵碼，×表示孩子節點

private class Node implements Comparable<Node> {
    Node parent;
    //關鍵字集合
    Vector<E> keys = new Vector<>(m);//不超過m-1個關鍵碼,這裡沒設定成m-1，因為當vector.size() == m時說明上(下)溢了
    //分支集合
    Vector<Node> children = new Vector<>(m);//不超過m個分支

    Node() {
        //用來判斷是否為葉子節點
        children.insert(0, null);
    }

    E getKey(int index) {
        return keys.get(index);
    }

    void setKey(int index, E e) {
        keys.set(index, e);
    }


    Node getChild(int index) {
        return children.get(index);
    }

    void setChild(int index, Node node) {
        children.set(index, node);
    }

    /**
     * 傳回目前節點是否為葉子節點
     *
     * @return
     */
    boolean isLeaf() {
        return this.children.get(0) == null;
    }

    /**
     * 為該節點在rightRank處插入一個關鍵碼和分支
     *
     * @param rightRank 要插入的關鍵碼的位置
     * @param e         關鍵碼
     * @param rightChild     分支
     */
    void insertNode(int rightRank, E e, Node rightChild) {
        this.keys.insert(rightRank, e);
        this.children.insert(rightRank + 1, rightChild);
        if (rightChild != null) {
            rightChild.parent = this;
        }
    }

    Node(E e, Node lc, Node rc) {
        keys.insert(0, e);
        children.insert(0, lc);
        children.insert(1, rc);
        if (lc != null) {
            lc.parent = this;
        }
        if (rc != null) {
            rc.parent = this;
        }
    }


    @Override
    public int compareTo(Node other) {
        //比較目前節點和other的最大值
        return this.keys.getLast().compareTo(other.keys.getLast());
    }
}      

下面我們先來一起探讨下B樹中最簡單也是最重要的操作——查找是如何進行的

查找

給定一顆B樹，我們如何進行查找呢？比如，我們要查找關鍵碼5。

首先，通路根節點6，然後查找小于它的做孩子節點2，它隻有一個關鍵碼，但是仍然不是我們要找的值，因為5比2大，繼續沿着它的右孩子[3,4,5]，此時，有不止一個關鍵碼，我們可以順序比較，也可以二分比較。假設這裡我們二分比較，首先比較關鍵碼4，向右比較關鍵碼5，bingo，就是它。存在，說明找到了。

那麼，如果查找一個不存在的關鍵碼，比如11，會怎樣呢？

我就不逐漸描述了，通過上圖也不難了解，注意，最後通路到了關鍵碼12的做孩子，它指向了​

​null​

​，是以說明查找失敗。

有時，這并不是查找失敗，而是加載外部節點到記憶體中，繼續查找。這裡為了簡單，我們就不考慮這種情況。

private Node search(E e) {
    Node p = root;//通過p周遊整棵樹
    lastReachedNode = null;//用于記錄最後一個通路的節點，可用于插入
    while (p != null) {//p不為空就一直進行下去
        int rank = p.keys.search(e);//rank表示關鍵碼清單中<=e的元素的最大值的索引
        if (rank >= 0 && e.compareTo(p.getKey(rank)) == 0) { //若結果>=0，不一定表示找到了，還可能指向的是小于該關鍵碼的最大值索引
            //一定是在p.keys[rank] == e的情況下才能說明找到了
            return p;
        }
        lastReachedNode = p;//緩存最後通路的節點p
        //繼續查找失敗節點的右孩子,因為之前傳回的是小于e的節點，是以應該向它的右分支查找
        p = p.getChild(rank + 1);
    }
    return null;
}      

我們将關鍵碼清單和分支清單錯位，可以更容易看出每個關鍵碼和其左右分支的關系。

插入

嘿嘿，第二個介紹插入實作是因為它依賴于查找，同時查找是最簡單的是以最先介紹。

public boolean insert(E e) {
    Node node = search(e);//調用B樹的查找算法
    if (node != null) {
        //已經存在
        return false;
    }

    //在最後通路的節點中得到要插入的位置(不大于目标關鍵碼的最大關鍵碼的位置)
    int rank = lastReachedNode.keys.search(e);  //該lastReachedNode必為葉節點(它的分支都為空)，不然還會繼續查找下去
    //将其插入該位置之後
    lastReachedNode.keys.insert(rank + 1, e);
    //同時，多插入一個空右分支
    lastReachedNode.children.insert(rank + 2, null);
    size++;
    //可能發生上溢：分支數超過階次m，通過拆分(split)來處理上溢
    split(lastReachedNode);
    return true;
}      

如果不考慮上溢的情況，其實插入實作也很簡單。隻要找到待拆入位置，插入即可。

但是，世界是複雜的。插入時由于多加了一個關鍵碼和一個分支，可能導緻節點的分支數超過m(稱這種情況為上溢),此時不滿足B樹的定義了，是以需要處理這種情況。我們通過分裂來處理。

分裂

分裂從字面意思來看，就是将一個節點分裂成兩個，那麼是如何分的呢？

1. 我們将上溢節點中的關鍵碼記為：
2. 取中位數s = ⌊m/2⌋(表示向下取整，java中的​

   ​/​

   ​​就是向下取整)，以關鍵碼為界分為：，,
3. 關鍵碼提升至父節點(有的話)
4. 以分裂所得的兩個節點作為的左右孩子(分支)

還是通過圖示來了解這個過程吧，假設在一顆6階B樹(節點最多5個關鍵碼，或者說最多有6個分支)中插入關鍵碼37:

導緻發生了上溢，我們在這6個關鍵碼中選取中位數：6/2=3（m/2），指向的關鍵碼為37。

我們将該節點以37為界進行分裂，分裂為兩個節點[17,20,31]與[41,56]，并将37提升到父節點中，這兩個節點作為它的左右孩子。

盡管這兩個分裂出來的節點關鍵碼數量比分裂前幾乎少了一半，但還是會滿足B樹關于關鍵碼所設的下限。

我們回顧下B樹的定義,分支數m = 關鍵碼數n+ 1

m >= ⌈M/2⌉ ,M為B樹的階數

n+1 >= ⌈M/2⌉

得關鍵碼數n >= ⌈M/2⌉ - 1

這裡M=6，關鍵碼數的下限為3-1=2，是以可以看出，為啥有分支數 >= ⌈階數/2⌉ 這個定義

雖然被分裂的節點不會再上溢了，但是因為提升了一個關鍵碼到父節點，父節點也是有可能發生上溢的，此時，重複這個過程即可…直到根節點發生上溢(也就是說，它的父節點為空)

如果根節點也發生了上溢，同樣取出中位數關鍵碼，将提升後的關鍵碼成為新的根節點。同時整顆樹的高度提升1。根節點隻有1個關鍵碼也是符合定義的。回顧樹根的分支數下限定義： → ，即樹根關鍵碼數隻要大于等于1即可。同樣可以看出這樣設計的奧妙所在。同時該新根節點的分支數也滿足大于等于2的條件。

如上圖左所示，假設[17,20,31,37,41,56]為根節點，發生了上溢，處理後結果如上圖右所示。

從如上過程可以看出，最多分裂樹高h次，是以，整個插入算法的時間複雜度為

/**
 * 分裂，解決上溢
 *
 * @param node
 */
private void split(Node node) {
    //判斷是否需要分裂
    if (node.children.size() <= m) {
        return;
    }
    int s = m / 2; //取中位數s,以關鍵字k_s為界劃分為： k_0,...,k_(s-1),  k_s  ,k_(s+1),...,k_(m_1)
    Node newNode = new Node();//新節點已有一個空分支
    for (int i = 0; i < m - s - 1; i++) {
        //将s+1到m-1的元素(包括關鍵碼和分支)逐個移到newNode中 ，共有 m-1-(s+1)+1 = m-s-1個 即endIndex-startIndex+1
        newNode.children.insert(i, node.children.remove(s + 1));//移動分支
        newNode.keys.insert(i, node.keys.remove(s + 1));//移動關鍵碼
    }

    //移動node的最後一個分支到newNode中,此時node的關鍵碼數和分支數相同，那是因為中位數關鍵碼還未提升
    newNode.setChild(m - s - 1, node.children.remove(s + 1));
    if (!newNode.isLeaf()) {
        //如果新節點不是葉子節點，新節點有m-s個分支,設定其分支的父節點指向它
        for (int i = 0; i < m - s; i++) { //設定父節點
            newNode.getChild(i).parent = newNode;
        }
    }
    Node p = node.parent;//擷取node目前的父節點p,若p不為空，它的左孩子已經指向node了，不需要修改，隻要讓其右孩子指向newNode
    if (p == null) { //如果分裂的是根節點
        p = new Node();
        root = p;
        p.setChild(0, node);//node作為新父節點的左孩子,後面有newNode作為它的右孩子
        node.parent = p;
    }
    //得到中位數關鍵碼在p節點中的合适位置
    //不大于中位數的最大元素的位置  + 1，注意這種處理手法，多次出現
    int rank = 1 + p.keys.search(node.getKey(0));
    //中位數對應關鍵碼上升,newNode作為它的右孩子
    p.insertNode(rank, node.keys.remove(s), newNode);
    //上升一層，可能需要繼續分裂
    split(p);
}      

我們構造一顆(2,3)樹，并通過圖示來分析一下它的插入過程

public static void main(String[] args) {
    BTree<Integer> tree = new BTree<>(3);
    int[] values = {8, 3, 2, 1, 6, 7, 9, 12, 15};
    for (int value : values) {
        tree.insert(value);
    }
    System.out.println(tree.size());
}      

我們一步一步來構造這顆階數為3的2-3樹

插入8

此時這是一顆最簡單的B樹，^ 代表​

​null​

​​，代表最近插入的關鍵碼或分支，此時根節點無分支，或者說有兩個空分支。插入3

3是插入到關鍵碼8前面，它的又分支也是一樣，插入操作會将已存在的元素向右移動，這裡表示原來的關鍵碼或分支。

插入2

插入完2的節點上所示，注意，此時不是最終狀态。每次插入完之後會判斷是否上溢，此時有4個分支，超過了階數3，發生了上溢。我們要對該節點進行分裂操作：

取中位數(​

​3/2=1​

​)對應的關鍵碼3，将該節點分裂為兩個節點，3右邊的關鍵碼全部移到新節點上去。

同時将關鍵碼對應的左分支移動到新節點上，就是上圖左邊分支清單索引2處的元素移到到了右邊0處。移動完之後，分支索引3處的元素會左移一位，然後将它移動新階段關鍵碼8的右孩子分支處。

也就是将中位數元素後的所有關鍵碼和分支(分支會比關鍵碼數量多1)全部移動到新分支上。

細心的同學會發現，此時上圖左邊的節點有兩個關鍵碼和兩個分支，似乎多了一個分支。别急，還有一個步驟，将中位數上的關鍵碼(也就是3)向上提升到父節點(可能沒有，這裡就沒有)

因為此時分裂的就是根節點，是以直接構造出一個新節點作為根節點，将它的左右孩子分别指向原節點和分裂出來的新節點。同時更新孩子的父節點引用。(這裡沒有畫出來父節點引用) 至此，才是一個完整的插入并分裂結果。插入1

在關鍵碼2前面插入即可

插入6

在8前插入，和上一步類似。

插入7

我們進行查詢操作後，得到最後通路的關鍵碼為6，是以在其後插入關鍵碼7。此時也發生了上溢，過程和我們前面分析的一樣，就不展開分析了。

最終結果為：

插入9

插入12

首先是插入到[8,9]節點上，插入了關鍵字12後，導緻上溢，将[8,9,12]分裂後：

9提升到它們的父節點上，但是導緻了父節點的上溢，繼續分裂

将父節點的9關鍵碼分裂出來後的快照如上，此時中位關鍵碼7還未提升，可以從圖中看出，相當于是将關鍵碼9的左孩子以及最後一個節點(這裡也是9，但要知道可能不止移動一個關鍵碼)的右孩子移動到分裂出的節點。

最終結果如上，整棵樹的高度又提升了一層。

插入15

到此，整顆(2,3)-B樹構造完畢。

删除

幾乎所有的樹中，删除算法是最複雜的。B樹葉不例外，但是還是可以弄明白的。

public boolean remove(E e) {
    //首先還是先查詢是否存在
    Node node = search(e);
    if (node == null) {
        return false;
    }
    int rank = node.keys.search(e);//得到e在節點中的位置
    if (!node.isLeaf()) {//如果非葉子，則找到後繼節點
        Node p = node.children.get(rank + 1);//右子樹中一直向左
        //找到node的後繼節點
        while (!p.isLeaf()) {
            p = p.children.get(0);
        }
        //将node與後繼節點交換位置
        node.keys.set(rank, p.getKey(0));
        node = p;
        rank = 0;
    }
    //此時node位于最底層，其中第rank個關鍵碼就是待删除者
    //除了要删除關鍵碼，還要删除該關鍵碼的右分支
    node.keys.remove(rank);
    node.children.remove(rank + 1);
    size--;
    //解決下溢問題
    solveUnderflow(node);
    return true;
}      

删除算法的主線和BST差不多，但是由于删除節點後可能會導緻某個節點的分支數少于限定值，這種情況稱為下溢，下面重點來分析下該問題如何解決。

若節點V下溢時，它必然比最小關鍵碼限定少一個關鍵碼，即：⌈m/2⌉ - 2個關鍵碼和⌈m/2⌉ - 1個分支。

這時，解決方式得方情況實作：

• 若V節點的兄弟節點(左或右)的關鍵碼足夠多(>= ⌈m/2⌉ )關鍵碼，假設它的左兄弟滿足這種情況，此時可以從左兄弟(右兄弟同理)借一個(當然是不會還的哈哈)關鍵碼到節點V。這裡需要注意到，不能直接把做兄弟的最後一個孩子移到V中，因為這樣不能符合中序周遊上的順序性(父節點關鍵碼大于左分支關鍵碼小于右分支關鍵碼)，是以實際上的做法是将x移到父節點，同時将父節點關鍵碼y移動V節點。、

• 若V的左兄弟L和右兄弟R或不存在，或所包含的關鍵碼數不足 ⌈m/2⌉ 個(那就是剛好 ⌈m/2⌉ -1個)，但是左右兄弟必有一個存在(因為所有的葉子節點都在同一層上，極端情況是最左邊的節點隻有右兄弟，而最右邊的節點隻有左兄弟)，這裡假設左兄弟L存在。此時，假設将L和V以及父節點關鍵y合并成一個新節點，該新節點的關鍵碼數為： ⌈m/2⌉ - 1 + 1 + ⌈m/2⌉ - 2 (L的關鍵碼數 +父節點一個關鍵碼 + V節點關鍵數 ) = m - 2 ，注意該值小于關鍵碼數的上限(m-1)。

注意，由于從父節點拉了一個關鍵碼下來，可能導緻父節點也發生下溢，重複整個處理下溢過程即可。

整個修複下溢過程疊代數不超過。

/**
 * 解決下溢問題：删除後關鍵碼數量不滿足B樹定義:不小于ceil(m/2)
 *
 * @param node
 */
private void solveUnderflow(Node node) {
    //并未下溢
    if (node.children.size() >= ceilHalfM) {
        return;
    }
    Node p = node.parent;
    if (p == null) {
        //已經到了根節點，沒有分支的下限
        if (node.keys.size() == 0 && node.getChild(0) != null) {
            //樹根已不含有關鍵碼，卻有唯一的非空孩子,将它作為新根，這是整顆樹高度下降的唯一場景
            root = node.getChild(0);
            root.parent = null;
            node.setChild(0, null);//node對應的引用可被回收了
        }
        return;
    }
    //還未達到根節點
    //确定node是p的第rank個孩子,此時p可能不含關鍵碼，不能通過關鍵碼查找
    int rank = 0;
    while (node.compareTo(p.getChild(rank)) != 0) {
        rank++;
    }

    //向左兄弟借關鍵碼
    if (rank > 0) {
        //若node不是p的第一個孩子，必存在左兄弟
        Node ls = p.getChild(rank - 1);//left sibling : ls
        if (ls.children.size() > ceilHalfM) {//若左兄弟的關鍵碼足夠
            //rank - 1關鍵碼處的右孩子是rank
            node.keys.insert(0, p.getKey(rank - 1));//這裡借的是對應的父節點的關鍵碼
            p.setKey(rank - 1, ls.keys.remove(rank - 1));//将左兄弟最大的關鍵碼提升到父節點位置

            //将左兄弟最右側的孩子給node
            node.children.insert(0, ls.children.remove(ls.children.size() - 1));
            if (!node.isLeaf()) {
                //如果該孩子不是空還需要修改parent引用
                node.children.get(0).parent = node;
            }
            return;
        }
        //若左兄弟關鍵碼不夠
    }
    //代碼到了這裡說明 左兄弟為空或 左兄弟關鍵碼數不夠

    //若有右兄弟，向右兄弟借關鍵碼，和向左兄弟借關鍵碼是一個鏡像操作
    if (p.children.size() - 1 > rank) {

        Node rs = p.getChild(rank + 1);
        //若右兄弟關鍵碼數足夠
        if (rs.children.size() > ceilHalfM) {
            //p借出一個關鍵碼給node，作為最大者
            node.keys.insert(node.keys.size(), p.getKey(rank));
            p.setKey(rank, rs.keys.remove(0));//右兄弟最小關鍵碼提升

            node.children.insert(node.children.size(), rs.children.remove(0));
            if (node.getChild(node.children.size() - 1) != null) {
                node.getChild(node.children.size() - 1).parent = node;
            }
            return;
        }
    }
    //代碼執行到此，說明左，右兄弟要麼為空(左右兄弟至少有一個不為空)，要麼關鍵碼數不夠

    if (rank > 0) { //說明左兄弟不為空,合并到左兄弟
        Node ls = p.getChild(rank - 1);
        //首先将父節點rank-1處關鍵碼下移到左兄弟
        ls.keys.insert(ls.keys.size(), p.keys.remove(rank - 1));
        p.children.remove(rank);//下移後指向node的分支删除掉
        //node的最左側孩子過繼給ls做最右側孩子
        ls.children.insert(ls.children.size(), node.children.remove(0));
        if (ls.getChild(ls.children.size() - 1) != null) {
            ls.getChild(ls.children.size() - 1).parent = ls;
        }
        //将node剩餘的關鍵碼和孩子移動到ls
        while (!node.keys.isEmpty()) {
            ls.keys.insert(ls.keys.size(), node.keys.remove(0));
            ls.children.insert(ls.children.size(), node.children.remove(0));
            if (ls.getChild(ls.children.size() - 1) != null) {
                ls.getChild(ls.children.size() - 1).parent = ls;
            }
        }
    } else {
        //與右兄弟合并
        Node rs = p.getChild(rank + 1);
        rs.keys.insert(0, p.keys.remove(rank));
        p.children.remove(rank);

        rs.children.insert(0, node.children.remove(node.children.size() - 1));
        if (rs.getChild(0) != null) {
            rs.getChild(0).parent = rs;
        }
        while (!node.keys.isEmpty()) {
            rs.keys.insert(0, node.keys.remove(node.keys.size() - 1));
            if (rs.getChild(0) != null) {
                rs.getChild(0).parent = rs;
            }
        }
    }
    //可能父節點p也下溢了
    solveUnderflow(p);
}      

完整代碼

BTree:

package com.algorithms.tree;

import com.algorithms.list.Vector;

/**
 * m路B樹，路就是分支的意思,說明有m個分支,相應的就有m-1個關鍵碼
 * 不超過m-1個關鍵碼(key),關鍵碼按遞增次序排列，不超過m個分支(孩子)
 * 樹根的分支數 >=2(或者僅存在合法的根節點，無分支)
 * 其他節點的分支數至少為ceil(m/2)
 * 每個節點最多含有m個分支
 *
 * @author yjw
 * @date 2019/7/1/001
 */
public class BTree<E extends Comparable<? super E>> {
    private static final int DEFAULT_M = 3;//(2,3)樹

    private int size;
    private Node root;
    private final int m; //階數
    private Node lastReachedNode;
    private final int ceilHalfM;//ceil(m/2)

    public BTree(int m) {
        //必須是大于2
        if (m <= 2) {
            throw new IllegalArgumentException("m mast be greater than 2");
        }
        this.m = m;
        size = 0;
        root = new Node();
        this.ceilHalfM = (m + 1) / 2;//(m+1)/2 就是ceil(m/2) ceil是天花闆，取上限的意思
    }

    public BTree() {
        this(DEFAULT_M);
    }

    public int size() {
        return size;
    }

    private Node search(E e) {
        Node p = root;
        lastReachedNode = null;
        while (p != null) {
            int rank = p.keys.search(e);
            if (rank >= 0 && e.compareTo(p.keys.get(rank)) == 0) {
                //找到了
                return p;
            }
            lastReachedNode = p;
            p = p.children.get(rank + 1);
        }
        return null;
    }

    public boolean insert(E e) {
        Node node = search(e);
        if (node != null) {
            //已經存在
            return false;
        }
        //在lastReachedNode中确定插入位置,lastReachedNode必然是葉子節點
        int rank = lastReachedNode.keys.search(e);
        lastReachedNode.insertNode(rank + 1, e, null);
        size++;
        split(lastReachedNode);
        return true;
    }

    /**
     * 分裂，解決上溢
     *
     * @param node
     */
    private void split(Node node) {
        //判斷是否需要分裂
        if (node.children.size() <= m) {
            return;
        }
        int s = m / 2; //取中位數s,以關鍵字k_s為界劃分為： k_0,...,k_(s-1),  k_s  ,k_(s+1),...,k_(m_1)
        Node newNode = new Node();//新節點已有一個空分支
        for (int i = 0; i < m - s - 1; i++) {
            //将s+1到m-1的元素(包括關鍵碼和分支)逐個移到newNode中 ，共有 m-1-(s+1)+1 = m-s-1個 即endIndex-startIndex+1
            newNode.children.insert(i, node.children.remove(s + 1));//移動分支
            newNode.keys.insert(i, node.keys.remove(s + 1));//移動關鍵碼
        }

        //移動node的最後一個分支到newNode中,此時node的關鍵碼數和分支數相同，那是因為中位數關鍵碼還未提升
        newNode.setChild(m - s - 1, node.children.remove(s + 1));
        if (!newNode.isLeaf()) {
            //如果新節點不是葉子節點，新節點有m-s個分支,設定其分支的父節點指向它
            for (int i = 0; i < m - s; i++) { //設定父節點
                newNode.getChild(i).parent = newNode;
            }
        }
        Node p = node.parent;//擷取node目前的父節點p,若p不為空，它的左孩子已經指向node了，不需要修改，隻要讓其右孩子指向newNode
        if (p == null) { //如果分裂的是根節點
            p = new Node();
            root = p;
            p.setChild(0, node);//node作為新父節點的左孩子,後面有newNode作為它的右孩子
            node.parent = p;
        }
        //得到中位數關鍵碼在p節點中的合适位置
        //不大于中位數的最大元素的位置  + 1，注意這種處理手法，多次出現
        int rank = 1 + p.keys.search(node.getKey(0));
        //中位數對應關鍵碼上升,newNode作為它的右孩子
        p.insertNode(rank, node.keys.remove(s), newNode);
        //上升一層，可能需要繼續分裂
        split(p);
    }

    public boolean remove(E e) {
        //首先還是先查詢是否存在
        Node node = search(e);
        if (node == null) {
            return false;
        }
        int rank = node.keys.search(e);//得到e在節點中的位置
        if (!node.isLeaf()) {//如果非葉子，則找到後繼節點
            Node p = node.children.get(rank + 1);//右子樹中一直向左
            //找到node的後繼節點
            while (!p.isLeaf()) {
                p = p.children.get(0);
            }
            //将node與後繼節點交換位置
            node.keys.set(rank, p.getKey(0));
            node = p;
            rank = 0;
        }
        //此時node位于最底層，其中第rank個關鍵碼就是待删除者
        //除了要删除關鍵碼，還要删除該關鍵碼的右分支
        node.keys.remove(rank);
        node.children.remove(rank + 1);
        size--;
        //解決下溢問題
        solveUnderflow(node);
        return true;
    }

    /**
     * 解決下溢問題：删除後關鍵碼數量不滿足B樹定義:不小于ceil(m/2)
     *
     * @param node
     */
    private void solveUnderflow(Node node) {
        //并未下溢
        if (node.children.size() >= ceilHalfM) {
            return;
        }
        Node p = node.parent;
        if (p == null) {
            //已經到了根節點，沒有分支的下限
            if (node.keys.size() == 0 && node.getChild(0) != null) {
                //樹根已不含有關鍵碼，卻有唯一的非空孩子,将它作為新根，這是整顆樹高度下降的唯一場景
                root = node.getChild(0);
                root.parent = null;
                node.setChild(0, null);//node對應的引用可被回收了
            }
            return;
        }
        //還未達到根節點
        //确定node是p的第rank個孩子,此時p可能不含關鍵碼，不能通過關鍵碼查找
        int rank = 0;
        while (node.compareTo(p.getChild(rank)) != 0) {
            rank++;
        }

        //向左兄弟借關鍵碼
        if (rank > 0) {
            //若node不是p的第一個孩子，必存在左兄弟
            Node ls = p.getChild(rank - 1);//left sibling : ls
            if (ls.children.size() > ceilHalfM) {//若左兄弟的關鍵碼足夠
                //rank - 1關鍵碼處的右孩子是rank
                node.keys.insert(0, p.getKey(rank - 1));//這裡借的是對應的父節點的關鍵碼
                p.setKey(rank - 1, ls.keys.remove(rank - 1));//将左兄弟最大的關鍵碼提升到父節點位置

                //将左兄弟最右側的孩子給node
                node.children.insert(0, ls.children.remove(ls.children.size() - 1));
                if (!node.isLeaf()) {
                    //如果該孩子不是空還需要修改parent引用
                    node.children.get(0).parent = node;
                }
                return;
            }
            //若左兄弟關鍵碼不夠
        }
        //代碼到了這裡說明 左兄弟為空或 左兄弟關鍵碼數不夠

        //若有右兄弟，向右兄弟借關鍵碼，和向左兄弟借關鍵碼是一個鏡像操作
        if (p.children.size() - 1 > rank) {

            Node rs = p.getChild(rank + 1);
            //若右兄弟關鍵碼數足夠
            if (rs.children.size() > ceilHalfM) {
                //p借出一個關鍵碼給node，作為最大者
                node.keys.insert(node.keys.size(), p.getKey(rank));
                p.setKey(rank, rs.keys.remove(0));//右兄弟最小關鍵碼提升

                node.children.insert(node.children.size(), rs.children.remove(0));
                if (node.getChild(node.children.size() - 1) != null) {
                    node.getChild(node.children.size() - 1).parent = node;
                }
                return;
            }
        }
        //代碼執行到此，說明左，右兄弟要麼為空(左右兄弟至少有一個不為空)，要麼關鍵碼數不夠

        if (rank > 0) { //說明左兄弟不為空,合并到左兄弟
            Node ls = p.getChild(rank - 1);
            //首先将父節點rank-1處關鍵碼下移到左兄弟
            ls.keys.insert(ls.keys.size(), p.keys.remove(rank - 1));
            p.children.remove(rank);//下移後指向node的分支删除掉
            //node的最左側孩子過繼給ls做最右側孩子
            ls.children.insert(ls.children.size(), node.children.remove(0));
            if (ls.getChild(ls.children.size() - 1) != null) {
                ls.getChild(ls.children.size() - 1).parent = ls;
            }
            //将node剩餘的關鍵碼和孩子移動到ls
            while (!node.keys.isEmpty()) {
                ls.keys.insert(ls.keys.size(), node.keys.remove(0));
                ls.children.insert(ls.children.size(), node.children.remove(0));
                if (ls.getChild(ls.children.size() - 1) != null) {
                    ls.getChild(ls.children.size() - 1).parent = ls;
                }
            }
        } else {
            //與右兄弟合并
            Node rs = p.getChild(rank + 1);
            rs.keys.insert(0, p.keys.remove(rank));
            p.children.remove(rank);

            rs.children.insert(0, node.children.remove(node.children.size() - 1));
            if (rs.getChild(0) != null) {
                rs.getChild(0).parent = rs;
            }
            while (!node.keys.isEmpty()) {
                rs.keys.insert(0, node.keys.remove(node.keys.size() - 1));
                if (rs.getChild(0) != null) {
                    rs.getChild(0).parent = rs;
                }
            }
        }
        //可能父節點p也下溢了
        solveUnderflow(p);
    }


    /**
     * 此處Node定義為内部類，非靜态類(有static關鍵字)，是以可以通路其關聯類的屬性(m)和類型參數E
     *
     * @param
     */
    private class Node implements Comparable<Node> {
        Node parent;
        //關鍵字集合
        Vector<E> keys = new Vector<>(m);//不超過m-1個關鍵碼,這裡沒設定成m-1，因為當vector.size() == m時說明上(下)溢了
        //分支集合
        Vector<Node> children = new Vector<>(m);//不超過m個分支

        Node() {
            //用來判斷是否為葉子節點
            children.insert(0, null);
        }

        E getKey(int index) {
            return keys.get(index);
        }

        void setKey(int index, E e) {
            keys.set(index, e);
        }


        Node getChild(int index) {
            return children.get(index);
        }

        void setChild(int index, Node node) {
            children.set(index, node);
        }

        /**
         * 傳回目前節點是否為葉子節點
         *
         * @return
         */
        boolean isLeaf() {
            return this.children.get(0) == null;
        }

        /**
         * 為該節點在rightRank處插入一個關鍵碼和分支
         *
         * @param rightRank  要插入的關鍵碼的位置
         * @param e          關鍵碼
         * @param rightChild 分支
         */
        void insertNode(int rightRank, E e, Node rightChild) {
            this.keys.insert(rightRank, e);
            this.children.insert(rightRank + 1, rightChild);
            if (rightChild != null) {
                rightChild.parent = this;
            }
        }

        Node(E e, Node lc, Node rc) {
            keys.insert(0, e);
            children.insert(0, lc);
            children.insert(1, rc);
            if (lc != null) {
                lc.parent = this;
            }
            if (rc != null) {
                rc.parent = this;
            }
        }


        @Override
        public int compareTo(Node other) {
            //比較目前節點和other的最大值
            return this.keys.getLast().compareTo(other.keys.getLast());
        }
    }

    public static void main(String[] args) {
        BTree<Integer> tree = new BTree<>(3);
        int[] values = {8, 3, 2, 1, 6, 7, 9, 12, 15};
        for (int value : values) {
            tree.insert(value);
        }
        System.out.println(tree.size());
        tree.remove(1);
        System.out.println(tree.size);
    }
}      

Vector:

package com.algorithms.list;

import java.util.Arrays;
import java.util.NoSuchElementException;

/**
 * 向量
 *
 * @author yjw
 * @date 2019/6/27/027
 */
public class Vector<E extends Comparable<? super E>> {
    private static final int DEFAULT_CAPACITY = 10;
    private static final Comparable[] EMPTY_ELEMENT_DATA = {};

    /**
     * 向量的容量
     */
    private int capacity;

    /**
     * 向量中元素個數
     */
    private int size;

    //這裡設定成泛型數組  參考https://blog.csdn.net/yjw123456/article/details/93666945
    private E[] items;

    @SuppressWarnings("unchecked")
    public Vector(int capacity) {
        if (capacity < 0) {
            throw new IllegalArgumentException("Negative capacity");
        } else if (capacity == 0) {
            items = (E[]) EMPTY_ELEMENT_DATA;
        } else {
            items = (E[]) new Comparable[capacity];
        }
        this.capacity = capacity;
        this.size = 0;
    }

    public Vector() {
        this(DEFAULT_CAPACITY);
    }

    /**
     * 得到索引index處的值
     *
     * @param index
     * @return
     */
    public E get(int index) {
        checkIndex(index);
        return items[index];
    }

    /**
     * 替換索引index處的值
     *
     * @param index
     * @param e
     * @return 舊值
     */
    public E set(int index, E e) {
        checkIndex(index);
        E old = items[index];
        items[index] = e;
        return old;
    }

    public int size() {
        return size;
    }

    public E getLast() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return items[size - 1];
    }


    /**
     * 在索引index處插入元素e
     *
     * @param index
     * @param e
     * @return
     */
    public void insert(int index, E e) {
        checkIndex(index);
        ensureCapacity(size + 1);

        //将index及index之後的元素後移
        for (int i = size - 1; i >= index; i--) {
            items[i + 1] = items[i];
        }
        items[index] = e;
        size++;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * @param e
     * @return index: 不大于(<=)該項e的元素的最大值的索引
     */
    public int search(E e) {
        if (isEmpty()) {
            return -1;
        }
        //基于items是有序的
        return search(e, 0, size);
    }

    /**
     * [low,high)
     *
     * @param e
     * @param low
     * @param high
     * @return
     */
    private int search(E e, int low, int high) {
        while (low < high) {
            int mid = low + (high - low) / 2;
            int cmp = e.compareTo(items[mid]);
            if (cmp < 0) {
                high = mid;
            } else if (cmp > 0) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return low - 1;
    }


    public void add(E e) {
        ensureCapacity(size + 1);
        items[size++] = e;
    }

    public E remove(int index) {
        checkIndex(index);
        E removed = items[index];
        for (int i = index; i < size - 1; i++) {
            items[i] = items[i + 1];
        }
        size--;
        return removed;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < size; i++) {
            sb.append(items[i]);
            if (i >= size - 1) {
                return sb.append("]").toString();
            }
            sb.append(", ");
        }
        return sb.append("]").toString();
    }

    /**
     * 對向量中元素進行排序
     */
    public void sort() {
        //通過歸并排序的方式
        mergeSort(items, 0, size);
    }

    private void checkIndex(int index) {
        if (index < 0) {
            throw new IndexOutOfBoundsException("index :" + index);
        }
    }

    private void ensureCapacity(int minCapacity) {
        if (items == EMPTY_ELEMENT_DATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        if (minCapacity - capacity > 0) {
            capacity = minCapacity * 2;
            items = Arrays.copyOf(items, capacity);
        }
    }


    private void mergeSort(E[] array, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;

            /**
             * mid屬于左邊的數組，mid+1屬于右邊的數組
             */
            mergeSort(array, left, mid);//對前半段排序
            mergeSort(array, mid + 1, right);//對右半段排序

            //優化：如果array[mid]小于array[mid+1],則不需要進行歸并了
            if (array[mid].compareTo(array[mid + 1]) < 0) {
                return;
            }
            // 歸并
            // 注意，傳入的是mid+1
            merge(array, left, mid + 1, right);
        }
    }

    /**
     * @param array
     * @param left     指向左邊數組，左邊數組開始位置
     * @param right    指向右邊數組，右邊數組開始位置
     * @param rightEnd 右邊數組最後一個元素位置
     */
    private void merge(E[] array, int left, int right, int rightEnd) {
        @SuppressWarnings("unchecked")
        E[] aux = (E[]) new Comparable[array.length];//輔助數組

        int leftEnd = right - 1;//左邊數組最後位置
        int auxIndex = left;//輔助數組開始位置
        int num = rightEnd - left + 1;//元素總數
        while (left <= leftEnd && right <= rightEnd) {
            if (array[left].compareTo(array[right]) < 0) {
                aux[auxIndex++] = array[left++];
            } else {
                aux[auxIndex++] = array[right++];
            }
        }

        /**
         * 拷貝剩下的元素
         * 以下兩個while循環，隻有一個會執行
         */
        while (left <= leftEnd) {
            aux[auxIndex++] = array[left++];
        }
        while (right <= rightEnd) {
            aux[auxIndex++] = array[right++];
        }
        //将輔助數組拷貝回原數組
        for (int i = 0; i < num; i++, rightEnd--) {
            array[rightEnd] = aux[rightEnd];
        }
    }


    public static void main(String[] args) {
        int[] values = {1, 2, 3, 5, 7, 9, 10, 12, 13, 15};
        Vector<Integer> vector = new Vector<>();
        for (int value : values) {
            vector.add(value);
        }
        vector.insert(3, 4);
        System.out.println(vector);
        System.out.println(vector.search(6));
        System.out.println(vector.search(7));
        System.out.println(vector.search(8));

    }

}      

複雜度