树4：B+树

B+树。它是一种非常重要的数据结构，尤其在数据库系统和文件系统中扮演着核心角色，用于高效地存储、检索和更新大量数据（特别是在磁盘等较慢的存储介质上）。

对于数据库，常见的查询有两类，查询某个数据和范围查询。我们需要一种数据结构加速这两种查询的速度。

select * from user where id=1234；
select * from user where id > 1234 and id < 2345。

首先是我们常见的平衡二叉搜索树，二叉树无法支持范围查询，需要通过中序遍历获得范围列表。那么我们可以使用跳表，查询速度快且由于是链表结构，方便范围查询。

B+ 树

B+ 树是 B 树 的一个升级，它比 B 树更适合实际应用中操作系统的文件索引和数据库索引。目前现代关系型数据库最广泛的支持索引结构就是 B+ 树。
B+ 树是一种多叉排序树，即每个节点通常有多个孩子。一棵 B+ 树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点。
B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入，这与二叉树恰好相反。

B+树的设计主要为了解决以下问题：

1. 减少磁盘I/O次数： 磁盘访问（寻道+旋转）相对于内存访问非常慢。B+树通过让一个节点（通常对应一个磁盘块）容纳大量关键字和指针，使得一次磁盘读取能获取更多有用信息，从而大幅减少查找、插入、删除操作所需的磁盘访问次数。
2. 高效的范围查询： 数据库查询中经常需要查找某个范围内的所有记录（例如，查找年龄在20到30岁之间的所有用户）。B+树对此进行了特别优化。
3. 保持数据有序： 数据在B+树中始终保持排序状态，这对于等值查询和范围查询都至关重要。
4. 平衡性： 确保从根节点到任何叶子节点的路径长度相同，保证操作效率的稳定（O(log n)）。

为什么B+树在数据库中如此重要？

1. 更少的磁盘I/O： 内部节点只存储索引信息（关键字+指针），不存数据。这意味着一个磁盘块可以容纳更多的关键字和指针，从而让树变得更“矮胖”（即阶数 m 更大）。树的高度越低，查找、插入、删除需要访问的磁盘块数就越少。
2. 卓越的范围查询性能： 叶子节点按顺序链接成链表。一旦找到范围查询的起始点，就可以通过链表顺序扫描叶子节点获取所有范围内的数据，无需回溯树结构。这在B树中是无法高效完成的。
3. 更稳定的查询性能： 由于所有数据都在叶子节点，任何查找都必须从根遍历到某个叶子节点，路径长度完全相同（等于树高）。查询时间更可预测。
4. 更高的空间利用率： 内部节点不存数据，空间用于存储更多索引信息。叶子节点通常也能填充得更满（因为删除操作倾向于重新分配或合并）。
5. 全表扫描效率高： 只需遍历叶子节点链表即可获取所有数据，顺序I/O效率极高。

B+树的核心结构

阶数 (Order - m)

• 定义了一个节点最多能拥有的子节点数。
• 一个节点最多包含 m 个子节点。
• 一个节点最多包含 m-1 个关键字。
• 一个节点最少包含 ceil(m/2) 个子节点 (根节点除外，根的子节点数可以 >=2)。
• 一个节点最少包含 ceil(m/2) - 1 个关键字 (根节点除外，根的关键字数可以 >=1)。

节点组成:

内部节点 (Index Node / Non-Leaf Node):

• 存储 k 个关键字：K1, K2, ..., Kk (其中 ceil(m/2)-1 <= k <= m-1)。
• 存储 k+1 个指向子节点的指针：P0, P1, P2, ..., Pk。
• 关键字的语义：P0 指向子树中的所有关键字都 < K1；P1 指向子树中的所有关键字都 >= K1 且 < K2；...；Pk 指向子树中的所有关键字都 >= Kk。
• 只存储索引信息（关键字和子节点指针），不存储实际数据。

叶子节点 (Leaf Node):

• 存储 k 个关键字：K1, K2, ..., Kk (其中 ceil(m/2)-1 <= k <= m-1)。
• 对于每个关键字 Ki，存储其关联的 实际数据 或者 指向实际数据的指针 (Data_Ptr_i)。
• 存储一个指向 下一个叶子节点 的指针 (Next_Leaf_Ptr)。通常也会有指向前一个叶子节点的指针 (Prev_Leaf_Ptr)，形成双向链表。
• 存储所有实际数据（或指向数据的指针）。

性质:

• 所有数据 都在 叶子节点。
• 所有叶子节点位于同一层（树是完全平衡的）。
• 叶子节点通过指针按关键字大小顺序链接（链表）。
• 内部节点的关键字充当分隔值，指导搜索路径。

B+树实现

对于B+树的实现，难点在于插入数据和删除数据的逻辑：

插入

  [2]            [2,3]
  / \       =>   / | \
[1] [2,3]      [1][2][3,4]

有以下几种情况：

1. 原本树是空的。那么我们直接新建一个叶子节点，作为root节点即可。

2. 原本树是非空的：

   • 查找可插入的叶子节点
   • 如果存在相同key，则直接替换元素即可
   • 如果可插入叶子，则插入，然后进行节点分裂操作

节点分裂

节点分裂时B+树插入时保持平衡的方法。有以下两种情况：

1. 没有达到分裂条件，则直接修复父节点（插入首位的时候）
2. 如果插入之后达到了m，则需要将节点分裂为两个节点。
3. 如果分裂后的叶子节点没有父节点，则构建的一个内部节点作为他们的父节点，分割关键字是后一个节点的第一个关键字，结束。
4. 如果有父节点，则将后一个节点的第一个关键字放到父节点作为分割关键字。检查父节点情况。
5. 父节点有两种情况，一是没有达到分裂条件m 则结束。
6. 如果达到了分裂条件，则将节点分裂成两个节点，以中点mid为界，0到mid-1 为前一个节点，mid+1到m为后一个节点。如果没有父节点，则构建以mid为分割关键字的节点。
7. 如果有父节点，则将mid为分割关键字插入到父节点。
8. 递归检查父节点情况，直到平衡。

需要注意的是：没有父节点，表示当前节点是根节点，需要构建一新父节点，此节为新的根节点

删除

  [2,3]             [2,4]
  / | \       =>    / | \
[1][2][3,4]       [1][2][4]

有以下几种情况：

1. 需要删除的元素不存在，直接返回。
2. 需要删除的元素在根节点中，则直接删除，不需要调整
3. 如果要删除的元素所在节点在删除一个元素之后大于Math.ceil(maxDegree / 2.0) - 1 则直接删除。然后调整父节点（在删除的元素是节点中的第一个元素的情况下）
4. 如果要删除的元素所在节点在删除一个元素之后不大于Math.ceil(maxDegree / 2.0) - 1，则在删除、调整父节点之后，还需要进行节点合并操作。

节点合并

节点合并需要获取到同一个父节点的当前元素的左右兄弟节点（如果存在）。B+树通过节点合并保证删除后的树平衡。有以下4种情况：

1. 左节点存在且左节点在删除一个元素之后大于Math.ceil(maxDegree / 2.0) - 1，则将左节点的最后一个元素移动到当前节点。结束。
2. 右节点存在且右节点在删除一个元素之后大于Math.ceil(maxDegree / 2.0) - 1，则将右节点的第一个元素移动到当前节点。调整父节点关键字，结束。
3. 左节点存在，但是不满足1、2。则将当前节点合并到左节点，删除当前节点。调整父节点关系（跳到5）。
4. 右节点存在，但是不满足1、2、3。则将当右节点合并到当前节点，删除右节点。调整父节点关系（跳到5）。
5. 此时我们已经完成了叶子节点的分裂。现在需要调整叶子节点的父节点。如果调整后父节点大于Math.ceil(maxDegree / 2.0) - 1，则调整完成，结束。
6. 如果父节点小于等于Math.ceil(maxDegree / 2.0) - 1，则当前节点变成该父节点。当前节点如果没有父节点且只有一个子节点，则该子节点就是根节点；如果不止一个子节点则调整完成，结束。
7. 如果当前节点有父节点，则需要获取到同一个父节点的左右节点，进行节点合并操作。
8. 内部节点的合并与叶子节点的合并操作是类似的，依然是先借元素，如果不行则合并元素。
9. 依此类推，直到平衡。

注意：

1. 父节点关系调整，包括更新关键字、删除关键字操作。
2. 当父节点是根节点且只有一个子节点的时候，当前节点就是根节点。

实现

这里使用Java实现，有大量的数据搬移与循环查找（可使用二分查找优化），效率并不高。这里主要做演示。

package cn.lishiyuan.algorithm.tree;  
  
  
import java.util.Arrays;  
  
public class BTree<T extends Comparable<T>>{  
  
//    private long address; // fd  
  
    private int maxDegree = 3;  
  
    private int size = 0;  
  
    private Node root;  
  
    public BTree(int maxDegree){  
        if (maxDegree >= 3 && maxDegree <= 7){  
            this.maxDegree = maxDegree;  
        }  
        size = 0;  
        root = null;  
    }  
  
    public BTree(){  
        this(3);  
    }  
  
    private static class Node{  
        // 由于需要自底而上合并与删除  
        Node parent;  
        int degree;  
        Object[] keywords;  
        // children[0] 小于 key[0] 的所有数据 ，children[1] 大于等于 key[0] 的数据  
        Node[] children;  
    }  
  
    private static class Leaf extends Node{  
        Object[] data;  
        /*  
         * 叶子节点有前后指针  
         */        private Leaf prev;  
        private Leaf next;  
    }  
  
    public int size() {  
        return size;  
    }  
  
    public boolean isEmpty() {  
        return size == 0;  
    }  
  
    public boolean contains(T key) {  
        Node node = findNode(key);  
        if (node == null){  
            return false;  
        }  
  
        for (int i = 0; i < node.degree; i++) {  
            if(node.keywords[i].equals(key)){  
                return true;  
            }  
        }  
  
        return false;  
    }  
  
    public Object find(T key) {  
        Leaf node = findNode(key);  
        if (node == null){  
            return null;  
        }  
        // 获取index  
        for (int i = 0; i < node.degree; i++) {  
            if (node.keywords[i].equals(key)) {  
                return node.data[i];  
            }  
        }  
        return null;  
    }  
  
    public void add(T key,Object data) {  
        // 查询叶子节点的可插入位置  
        if(key == null){  
            return;  
        }  
  
        // 寻找合适的位置插入  
        if (root==null){  
            root = newLeaf(key, data);  
            size++;  
            return;        }  
  
        Leaf node = findNode(key);  
        if(node !=null ){  
            int index = -1;  
            for (int i = 0; i < node.degree; i++) {  
                // 替换  
                if (node.keywords[i].equals(key)) {  
                    node.data[i] = data;  
                    return;                }  
                if (((T)node.keywords[i]).compareTo(key) > 0) {  
                    index = i;  
                    break;                }  
            }  
            //  
            if(index == -1){  
                // 所有关键字都小于key，则直接接在最后就行  
                index = node.degree;  
                node.keywords[index] = key;  
                node.data[index] = data;  
                node.degree++;  
                // 分裂节点，如果需要的话  
                divideLeaf(node);  
            }else {  
                // index 就是目标位置，空出位置  
                for (int i = node.degree - 1; i >= index; i--) {  
                    node.keywords[i+1] = node.keywords[i];  
                    node.data[i+1] = node.data[i];  
                }  
                node.keywords[index] = key;  
                node.data[index] = data;  
                node.degree++;  
  
                if(index==0){  
                    // 放在第一位，需要修复  
                    if(node.parent!=null){  
                        for (int i = 0; i <= node.parent.degree; i++) {  
                            if(node.parent.children[i].equals(node) && i>0){  
                                node.parent.keywords[i-1] = node.keywords[0];  
                            }  
                        }  
                    }  
                }  
  
                divideLeaf(node);  
            }  
  
            size++;  
        }  
  
    }  
  
    public Object remove(T key) {  
        // 查询叶子节点的可插入位置  
        if(key == null){  
            return null;  
        }  
  
        // 寻找合适的位置插入  
        if (root==null){  
            return null;  
        }  
  
        Leaf node = findNode(key);  
        if(node == null){  
            return null;  
        }  
  
        int index = -1;  
  
        for (int i = 0; i < node.degree; i++) {  
            // 替换  
            if (node.keywords[i].equals(key)) {  
                index = i;  
                break;            }  
        }  
        // 不存在节点  
        if(index == -1){  
            return null;  
        }  
  
        // 直接删除不用调整  
        if(root == node){  
            Object result = node.data[index];  
            for (int i = index; i < node.degree-1; i++) {  
                // 向前移动一位  
                node.keywords[i] = node.keywords[i+1];  
                node.data[i]= node.data[i+1];  
            }  
            node.keywords[node.degree-1] = null;  
            node.data[node.degree-1] = null;  
  
            node.degree--;  
            size--;  
  
            // 没有节点了就置空  
            if(size==0){  
                root = null;  
            }  
  
            return result;  
        }  
  
  
        // 检查是否需要合并  
        double line = Math.ceil(maxDegree / 2.0) - 1;  
  
        // 删除后 依然能保证平衡则直接删除  
        if ((node.degree -1) >= line){  
            Object result = node.data[index];  
            for (int i = index; i < node.degree-1; i++) {  
                // 向前移动一位  
                node.keywords[i] = node.keywords[i+1];  
                node.data[i]= node.data[i+1];  
            }  
            node.keywords[node.degree-1] = null;  
            node.data[node.degree-1] = null;  
  
            node.degree--;  
  
            if (index == 0){  
                // 需要调整父级对应节点keyword  
                Node parent = node.parent;  
                for (int i = 0; i < parent.degree; i++) {  
                    if (parent.children[i].equals(node) && i>0) {  
                        parent.keywords[i-1] = node.keywords[0];  
                        break;                    }  
                }  
            }  
            size--;  
            return result;  
        }  
  
        // 无法保持平衡，删除后需要调整平衡状态  
        Object result = node.data[index];  
        for (int i = index; i < node.degree-1; i++) {  
            // 向前移动一位  
            node.keywords[i] = node.keywords[i+1];  
            node.data[i]= node.data[i+1];  
        }  
  
        node.keywords[node.degree-1] = null;  
        node.data[node.degree-1] = null;  
  
        node.degree--;  
  
        Leaf left = node.prev;  
        Leaf right = node.next;  
  
        if(left != null && left.parent != node.parent){  
            left = null;  
        }  
  
        if(right != null && right.parent != node.parent){  
            right = null;  
        }  
  
        mergeLeaf(node,left,right);  
  
        size--;  
        return result;  
    }  
  
    public void clear() {  
        root = null;  
        size = 0;  
    }  
  
    /**  
     * 查找节点  
     */  
    private Leaf findNode(T key){  
        if(key == null){  
            return null;  
        }  
        if(root == null){  
            return null;  
        }  
  
        Node cur = root;  
        while (cur!=null && !(cur instanceof BTree.Leaf)){  
            // 查询节点  
            for (int i = 0; i < cur.degree; i++) {  
                // 第一个大于当前节点的位置  
                if(((T)cur.keywords[i]).compareTo(key) > 0){  
                    // 前一个节点必然是小于等于key的  
                    cur = cur.children[i];  
                    break;                }else if (i == cur.degree - 1) {  
                    cur = cur.children[i+1];  
                    break;                }  
                // 其他情况直接向后查找i++  
            }  
        }  
  
        return (Leaf) cur;  
    }  
  
    /**  
     * 合并叶子  
     * @param node  
     * @param left  
     * @param right  
     */  
    private void mergeLeaf(Leaf node,Leaf left,Leaf right){  
  
        // 检查是否满足条件  
        double line = Math.ceil(maxDegree / 2.0) - 1;  
        // 兄弟借元素  
        // 先左节点查看  
        if(left != null && (left.degree-1) >= line){  
            // 借最右边元素  
            Object key = left.keywords[left.degree-1];  
            Object data= left.data[left.degree-1];  
            left.keywords[left.degree-1] = null;  
            left.data[left.degree-1] = null;  
            left.degree--;  
  
            for (int i = node.degree-1 ;i >= 0; i--) {  
                node.data[i+1]= node.data[i];  
                node.keywords[i+1] = node.keywords[i];  
            }  
            node.keywords[0] = key;  
            node.data[0] = data;  
            node.degree++;  
  
            // 更新父节点的keywords  
            Node parent = node.parent;  
            for (int i = 0; i <= parent.degree; i++) {  
                if (parent.children[i].equals(node)&& i>0) {  
                    parent.keywords[i-1] = key;  
                    break;                }  
            }  
  
            return;  
        }  
  
        // 右节点借元素  
        if(right != null && (right.degree-1) >= line){  
            // 借最右边元素  
            Object key = right.keywords[0];  
            Object data= right.data[0];  
  
            // 向前移动  
            for (int i = 0 ;i < right.degree-1; i++) {  
                right.data[i]= right.data[i+1];  
                right.keywords[i] = right.keywords[i+1];  
            }  
            right.keywords[right.degree-1] = null;  
            right.data[right.degree-1] = null;  
            right.degree--;  
  
            node.keywords[node.degree] = key;  
            node.data[node.degree] = data;  
            node.degree++;  
  
            // 处理后一个节点的父节点  
            Node parent = right.parent;  
            for (int i = 0; i <= parent.degree; i++) {  
                if (parent.children[i].equals(right) && i>0) {  
                    parent.keywords[i-1] = right.keywords[0];  
                    break;                }  
            }  
  
            if(node.degree==1){  
                // 如果是第一个元素，则需要第一个大于等于key之前的元素设置过  
                parent = node.parent;  
                for (int i = 0; i <= parent.degree; i++) {  
                    if (parent.children[i].equals(node) && i>0) {  
                        parent.keywords[i-1] = key;  
                        break;                    }  
                }  
            }  
  
            return;  
  
        }  
  
  
        // 合并兄弟，会导致父节点长度变短导致不符合定义  
        // 先合并左兄弟，  
        if(left !=null && left.degree > 0){  
            // 复制到leaf  
            for (int i = 0; i < node.degree; i++) {  
                left.keywords[left.degree+i] = node.keywords[i];  
                left.data[left.degree+i] = node.data[i];  
            }  
            left.degree += node.degree;  
  
            left.next = node.next;  
            if(node.next!=null){  
                node.next.prev = left;  
            }  
  
  
            node.prev = null;  
            node.next = null;  
            node.parent= null;  
            node.keywords= null;  
            node.children= null;  
            node.data= null;  
            node.degree = 0;  
  
            // 父节点删除  
            int index = -1;  
            Node parent = left.parent;  
            for (int i = 0; i <= parent.degree; i++) {  
                if(parent.children[i].equals(left)){  
                    // 父节点必然是一个node  
                    // i开始的所有元素向前移动一位  
                    index = i;  
                    break;                }  
            }  
            if(index!=-1){  
                //  
                for (int i = index; i < parent.degree-1; i++) {  
                    parent.keywords[i] = parent.keywords[i+1];  
                }  
                for (int i = index+1; i < parent.degree; i++) {  
                    parent.children[i] = parent.children[i + 1];  
                }  
            }  
  
            // 清除多余元素  
            parent.keywords[parent.degree-1] = null;  
            parent.children[parent.degree] = null;  
            parent.degree--;  
  
            // 获取左右兄弟合并父级  
            if(parent.degree < line){  
                if (parent.parent==null) {  
                    // 父节点是根节点  
                    if(parent.degree == 0){  
                        // 已经只有一个节点了  
                        root = left;  
                        root.parent = null;  
                        parent.children = null;  
                        parent.keywords = null;  
                        return;                    }  
                }else {  
                    // 获取左右节点递归合并  
                    int pIndex = -1;  
                    for (int i = 0; i <= parent.parent.degree; i++) {  
                        if (parent == parent.parent.children[i]) {  
                            pIndex = i;  
                            break;                        }  
                    }  
                    Node pLeft = null;  
                    Node pRight = null;  
                    if(pIndex-1 >=0){  
                        pLeft = parent.parent.children[pIndex-1];  
                    }  
                    if(pIndex+1 <= parent.parent.degree){  
                        pRight = parent.parent.children[pIndex+1];  
                    }  
                    mergeNode(parent,pLeft, pRight);  
                }  
            }  
            return;  
        }  
  
        // 再尝试合并右兄弟  
        if(right !=null){  
            // 复制到leaf  
            for (int i = 0; i < right.degree; i++) {  
                node.keywords[node.degree+i] = right.keywords[i];  
                node.data[node.degree+i] = right.data[i];  
            }  
            node.degree += right.degree;  
  
            node.next = right.next;  
            if(right.next!=null){  
                right.next.prev = node;  
            }  
  
            right.prev = null;  
            right.next = null;  
            right.parent= null;  
            right.keywords= null;  
            right.children= null;  
            right.data= null;  
            right.degree = 0;  
  
            // 父节点删除  
            int index = -1;  
            Node parent = node.parent;  
            for (int i = 0; i <= parent.degree; i++) {  
                if(parent.children[i].equals(node)){  
                    // i-1开始的所有元素向前移动一位  
                    index = i;  
                    break;                }  
            }  
            if(index!=-1){  
                for (int i = index; i < parent.degree-1; i++) {  
                    parent.keywords[i] = parent.keywords[i+1];  
                }  
                for (int i = index+1; i < parent.degree; i++) {  
                    parent.children[i] = parent.children[i+1];  
                }  
            }  
            // 清除多余元素  
  
            parent.keywords[parent.degree-1] = null;  
            parent.children[parent.degree] = null;  
            parent.degree--;  
            // 获取左右兄弟合并父级  
            if(parent.degree < line){  
                if (parent.parent==null) {  
                    // 当前节点是根节点  
                    if(parent.degree == 0){  
                        // 已经只有一个节点了  
                        root = node;  
                        root.parent = null;  
                        parent.children = null;  
                        parent.keywords = null;  
                        return;                    }  
                }else {  
                    // 获取左右节点递归合并  
                    int pIndex = -1;  
                    for (int i = 0; i <= parent.parent.degree; i++) {  
                        if (parent == parent.parent.children[i]) {  
                            pIndex = i;  
                            break;                        }  
                    }  
                    Node pLeft = null;  
                    Node pRight = null;  
                    if(pIndex-1 >=0){  
                        pLeft = parent.parent.children[pIndex-1];  
                    }  
                    if(pIndex+1 <= parent.parent.degree){  
                        pRight = parent.parent.children[pIndex+1];  
                    }  
                    mergeNode(parent,pLeft, pRight);  
                }  
            }  
            return;  
        }  
    }  
  
  
  
    /**  
     * 合并节点的情况，这里需要注意的是合并两个node需要一个关键字，需要从父节点下移  
     */  
    private void mergeNode(Node node,Node left,Node right){  
  
        // 检查是否满足条件  
        double line = Math.ceil(maxDegree / 2.0) - 1;  
        // 兄弟借元素  
        // 先左节点查看  
        if(left != null && (left.degree-1) >= line){  
            // 借最右边元素  
            Object key = left.keywords[left.degree-1];  
            Node data= left.children[left.degree];  
            left.keywords[left.degree-1] = null;  
            left.children[left.degree] = null;  
            left.degree--;  
  
            for (int i = node.degree-1 ;i >= 0; i--) {  
                node.keywords[i+1] = node.keywords[i];  
            }  
  
            for (int i = node.degree ;i >= 0; i--) {  
                node.children[i+1]= node.children[i];  
            }  
            // 更新父节点  
            data.parent=node;  
            node.keywords[0] = key;  
            node.children[0] = data;  
            node.degree++;  
            // 更新父节点的keywords  
            Node parent = node.parent;  
            for (int i = 0; i <= parent.degree; i++) {  
                if (parent.children[i].equals(node) && i>0) {  
                    parent.keywords[i-1] = key;  
                    break;                }  
            }  
            return;  
        }  
  
        // 先右节点借元素  
        if(right != null && (right.degree-1) >= line){  
            // 借最右边元素  
            Object key = right.keywords[0];  
            Node data= right.children[0];  
  
            for (int i = 0 ;i < right.degree-1; i++) {  
                right.keywords[i] = right.keywords[i+1];  
            }  
            for (int i = 0 ;i < right.degree; i++) {  
                right.children[i]= right.children[i+1];  
            }  
            right.keywords[right.degree-1] = null;  
            right.children[right.degree] = null;  
            right.degree--;  
  
            // 更新父节点  
            data.parent=node;  
            node.keywords[node.degree] = key;  
            node.children[node.degree+1] = data;  
            node.degree++;  
  
            // 处理后一个节点的父节点  
            Node parent = right.parent;  
            for (int i = 0; i <= parent.degree; i++) {  
                if (parent.children[i].equals(right) && i>0) {  
                    parent.keywords[i-1] = right.keywords[0];  
                    break;                }  
            }  
  
            if(node.degree==1){  
                // 如果是第一个元素，则需要第一个大于等于key之前的元素设置过  
                parent = node.parent;  
                for (int i = 0; i <= parent.degree; i++) {  
                    if (parent.children[i].equals(node) && i>0) {  
                        parent.keywords[i-1] = key;  
                        break;                    }  
                }  
            }  
            return;  
  
        }  
  
  
        // 合并兄弟，会导致父节点长度变短导致不符合定义  
        // 先合并左兄弟，  
        if(left !=null){  
            // 合并node  
            // 父节点删除  
            int index = -1;  
            Node parent = left.parent;  
            for (int i = 0; i <= parent.degree; i++) {  
                if(parent.children[i].equals(left)){  
                    // i-1开始的所有元素向前移动一位  
                    index = i;  
                    break;                }  
            }  
            // 获取分割键并下移  
            if(index!=-1){  
                left.keywords[left.degree] = parent.keywords[index];  
                left.degree++;  
            }  
            // 此时就对齐了  
            for (int i = 0; i < node.degree; i++) {  
                left.keywords[left.degree+i] = node.keywords[i];  
            }  
            for (int i = 0; i <= node.degree; i++) {  
                Node child = node.children[i];  
                child.parent = left;// 更新子节点指针  
                left.children[left.degree+i] = child;  
            }  
  
            node.parent= null;  
            node.keywords=null;  
            node.children=null;  
  
            left.degree+=node.degree;  
  
            node.degree = 0;  
  
            // 向前移动  
            if(index!=-1){  
                for (int i = index; i < parent.degree-1; i++) {  
                    parent.keywords[i] = parent.keywords[i+1];  
                }  
                for (int i = index+1; i < parent.degree; i++) {  
                    parent.children[i] = parent.children[i+1];  
                }  
            }  
            // 清除多余元素  
            parent.keywords[parent.degree-1] = null;  
            parent.children[parent.degree] = null;  
            parent.degree--;  
            // 获取左右兄弟合并父级  
            if(parent.degree < line){  
                if (parent.parent==null) {  
                    // 当前节点是根节点  
                    if(parent.degree == 0){  
                        // 已经只有一个节点了  
                        root = left;  
                        root.parent = null;  
                        parent.children = null;  
                        parent.keywords = null;  
                        return;                    }  
                }else {  
                    // 获取左右节点递归合并  
                    int pIndex = -1;  
                    for (int i = 0; i <= parent.parent.degree; i++) {  
                        if (parent == parent.parent.children[i]) {  
                            pIndex = i;  
                            break;                        }  
                    }  
                    Node pLeft = null;  
                    Node pRight = null;  
                    if(pIndex-1 >=0){  
                        pLeft = parent.parent.children[pIndex-1];  
                    }  
                    if(pIndex+1 <= parent.parent.degree){  
                        pRight = parent.parent.children[pIndex+1];  
                    }  
                    mergeNode(parent,pLeft, pRight);  
                }  
            }  
            return;  
        }  
  
        // 再尝试合并右兄弟  
        if(right !=null){  
            // 合并node  
  
            // 父节点删除  
            int index = -1;  
            Node parent = node.parent;  
            for (int i = 0; i <= parent.degree; i++) {  
                if(parent.children[i].equals(node)){  
                    // i-1开始的所有元素向前移动一位  
                    index = i;  
                    break;                }  
            }  
            // 下移  
            if(index!=-1){  
                node.keywords[node.degree]= parent.keywords[index];  
                node.degree++;  
            }  
  
  
            // 此时就对齐了  
            for (int i = 0; i < right.degree; i++) {  
                node.keywords[node.degree+i] = right.keywords[i];  
            }  
            for (int i = 0; i <= right.degree; i++) {  
                Node child = right.children[i];  
                child.parent = node;  
                node.children[node.degree+i] = child;  
            }  
            // 合并节点要构建一个中间关键字  
  
            right.parent= null;  
            right.keywords=null;  
            right.children=null;  
            node.degree+=right.degree;  
  
            right.degree = 0;  
  
  
  
            if(index!=-1){  
                for (int i = index; i < parent.degree-1; i++) {  
                    parent.keywords[i] = parent.keywords[i+1];  
                }  
                for (int i = index+1; i < parent.degree; i++) {  
                    parent.children[i] = parent.children[i+1];  
                }  
            }  
            parent.keywords[parent.degree-1] = null;  
            parent.children[parent.degree] = null;  
            parent.degree--;  
            // 获取左右兄弟合并父级  
            if(parent.degree < line){  
                if (parent.parent==null) {  
                    // 当前节点是根节点  
                    if(parent.degree == 0){  
                        // 已经只有一个节点了  
                        root = node;  
                        root.parent = null;  
                        parent.children = null;  
                        parent.keywords = null;  
                        return;                    }  
                }else {  
                    // 获取左右节点递归合并  
                    int pIndex = -1;  
                    for (int i = 0; i <= parent.parent.degree; i++) {  
                        if (parent == parent.parent.children[i]) {  
                            pIndex = i;  
                            break;                        }  
                    }  
                    Node pLeft = null;  
                    Node pRight = null;  
                    if(pIndex-1 >=0){  
                        pLeft = parent.parent.children[pIndex-1];  
                    }  
                    if(pIndex+1 <= parent.parent.degree){  
                        pRight = parent.parent.children[pIndex+1];  
                    }  
                    mergeNode(parent,pLeft, pRight);  
                }  
            }  
  
            return;  
        }  
    }  
  
    /**  
     * 分裂节点  
     * @param node  
     */  
    private void divideNode(Node node){  
        if(node == null){  
            return;  
        }  
        // 不需要分裂  
        if (node.degree != maxDegree){  
            return;  
        }  
        // 分裂节点  
        // 将前面 maxDegree / 2 分裂出去  
        // 比如此时有3个关键字，mid就是1，index=0就是左节点，index=2是右节点，index=1是父节点  
        int mid = maxDegree / 2;  
        // 也就是从mid到node.degree-1 index 是新节点  
        // 如果是叶子节点  
  
        Node parent = node.parent;  
        // 如果是普通节点  
        // 目标位置  
        Object pKey = node.keywords[mid];  
        Node rightChild = newNode(node,mid);  
        // rightChild子节点的父节点修改  
        for (int i = 0; i <= rightChild.degree; i++) {  
            rightChild.children[i].parent = rightChild;  
        }  
  
        if(parent == null){  
            // 根节点  
            parent = new Node();  
            parent.parent = null;  
            parent.keywords = new Object[maxDegree];  
            parent.degree=1;  
            parent.keywords[0] = pKey;  
            parent.children = new Node[maxDegree + 1];  
            parent.children[0] = node;  
            parent.children[1] = rightChild;  
            node.parent = parent;  
            rightChild.parent = parent;  
            root = parent;  
        }else {  
            // 查找合适的位置插入，然后检查是否要分裂  
            int index = -1;  
            for (int i = 0; i <= parent.degree; i++) {  
                if (parent.children[i].equals(node)) {  
                    // 从这个位置腾出位置  
                    index = i;  
                    break;                }  
            }  
  
            if(index == -1 || index == parent.degree){  
                // 直接接在最后一个位置  
                parent.keywords[parent.degree] = pKey;  
                parent.children[++parent.degree] = rightChild;  
            }else {  
                // 向后移动腾出位置  
                for (int i = parent.degree-1 ; i >= index ; i--) {  
                    parent.keywords[i+1] = parent.keywords[i];  
                    parent.children[i+2] = parent.children[i+1];  
                }  
                parent.keywords[index] = pKey;  
                parent.children[index+1] = rightChild;  
                parent.degree++;  
            }  
            rightChild.parent = parent;  
            node.parent = parent;  
            // 如果需要的话分裂父节点  
            divideNode(parent);  
        }  
  
    }  
  
    /**  
     * 分裂叶子  
     * @param old  
     */  
    private void divideLeaf(Leaf old){  
        if(old == null){  
            return;  
        }  
        if (old.degree != maxDegree){  
            // 修复父节点，在插入位置时首位的情况下需要修复  
            return;  
        }  
        // 分裂节点  
        // 将前面 maxDegree / 2 分裂出去  
        int mid = maxDegree / 2;  
        // 也就是从mid到node.degree-1 index 是新节点  
        // 如果是叶子节点  
  
        Node parent = old.parent;  
        Node rightChild = newLeaf(old, mid);  
        Object pKey = rightChild.keywords[0];  
  
        if(parent == null){  
            // 根节点  
            parent = new Node();  
            parent.parent = null;  
            parent.keywords = new Object[maxDegree];  
            parent.degree=1;  
            parent.keywords[0] = pKey;  
            parent.children = new Node[maxDegree + 1];  
            parent.children[0] = old;  
            parent.children[1] = rightChild;  
            old.parent = parent;  
            rightChild.parent = parent;  
            root = parent;  
        }else {  
            // 查找合适的位置插入，然后检查是否要分裂  
            int index = -1;  
            for (int i = 0; i <= parent.degree; i++) {  
                if (parent.children[i].equals(old)) {  
                    index = i;  
                    break;                }  
            }  
  
            if(index == -1 || index == parent.degree){  
                // 直接接在最后一个位置  
                parent.keywords[parent.degree] = pKey;  
                parent.children[++parent.degree] = rightChild;  
                rightChild.parent = parent;  
                old.parent = parent;  
            }else {  
                // 腾出位置  
                for (int i = parent.degree-1 ; i >= index ; i--) {  
                    parent.keywords[i+1] = parent.keywords[i];  
                    parent.children[i+2] = parent.children[i+1];  
                }  
                parent.keywords[index] = pKey;  
                parent.children[index+1] = rightChild;  
                parent.degree++;  
                rightChild.parent = parent;  
                old.parent = parent;  
            }  
  
        }  
        // 如果需要的话分裂父节点  
        divideNode(parent);  
    }  
  
    private Node newNode(Node old,int startIndex){  
        // 需要将index元素提上父级  
        Node node = new Node();  
        node.keywords= new Object[maxDegree];  
        node.children = new Node[maxDegree + 1];  
        node.degree = old.degree - (startIndex+1);  
        // 比如需要提升的index是1，那么就需要在2分割，  
        /*  
             0 1 2            [1,2,3]            0 1 2 3         */        System.arraycopy(old.keywords,startIndex+1,node.keywords,0,node.degree);  
        System.arraycopy(old.children,startIndex+1,node.children,0,(node.degree+1));  
        // 旧节点清除数据  
        int len = old.degree - startIndex;  
        Arrays.fill(old.keywords,startIndex,old.degree,null);  
        Arrays.fill(old.children,startIndex + 1, old.degree+1,null);  
        old.degree = old.degree - (node.degree+1);  
        // 构建节点指针  
        node.parent = old.parent;  
        return node;  
    }  
  
    private Leaf newLeaf(T key,Object data){  
        Leaf leaf = new Leaf();  
        leaf.keywords= new Object[maxDegree];  
        leaf.data = new Object[maxDegree];  
        leaf.degree = 1;  
        leaf.keywords[0] = key;  
        leaf.data[0] = data;  
        return leaf;  
    }  
  
    private Leaf newLeaf(Leaf oldLeaf,int startIndex){  
        Leaf leaf = new Leaf();  
        leaf.keywords= new Object[maxDegree];  
        leaf.data = new Object[maxDegree];  
        leaf.degree = oldLeaf.degree - startIndex;  
        System.arraycopy(oldLeaf.keywords,startIndex,leaf.keywords,0,leaf.degree);  
        System.arraycopy(oldLeaf.data,startIndex,leaf.data,0,leaf.degree);  
        // 旧节点清除数据  
        Arrays.fill(oldLeaf.keywords,startIndex,oldLeaf.degree,null);  
        Arrays.fill(oldLeaf.data,startIndex,oldLeaf.degree,null);  
        oldLeaf.degree = oldLeaf.degree - leaf.degree;  
        // 构建节点指针  
        // 旧节点的下个节点的上个节点是新节点  
        if(oldLeaf.next!=null){  
            oldLeaf.next.prev = leaf;  
        }  
        // 新节点的下个节点是旧节点的下个节点  
        leaf.next= oldLeaf.next;  
  
        leaf.prev = oldLeaf;  
        oldLeaf.next = leaf;  
  
        return leaf;  
    }  
  
    @Override  
    public String toString() {  
        StringBuilder builder = new StringBuilder();  
        if (root==null){  
            builder.append("null");  
        }else {  
            Node current = root;  
            while (current!=null && !(current instanceof Leaf)){  
                if(current.children != null){  
                    current = current.children[0];  
                }  
            }  
            if(current == null){  
                builder.append("error null");  
            }else {  
                Leaf leaf = (Leaf) current;  
                while (leaf!=null){  
                    for (int i = 0; i < leaf.degree; i++) {  
                        builder.append(leaf.keywords[i]).append("=>");  
                    }  
                    leaf = leaf.next;  
                }  
            }  
  
        }  
  
  
        return builder.toString();  
    }  
}

B+树是一种为磁盘等块存储设备量身定制的平衡多路搜索树。通过将所有数据存储在有序且链接的叶子节点，并让内部节点仅存储索引信息，它完美地优化了磁盘I/O次数和范围查询效率。这些特性使其成为数据库系统和文件系统中索引结构的事实标准。