# B-Tree to B+ Tree

```public class BTreeNode{ public int[] key; public BTreeNode[] c; boolean isLeaf; public int[] nextLeaf; public int n; private int T; //Each node has at least T-1 and at most 2T-1 keys public int min; public int max;   public BTreeNode(int t){ T = t; isLeaf = true; key = new int[2*T-1]; c = new BTreeNode[2*T]; n = 0; } public void insert(int newKey){ // Insert new key to current node // Make sure that the current node is not full by checking and // splitting if necessary before descending to node   if(duplicate(newKey) == false){ int i = n-1; if(isLeaf){ while((i >= 0) && (newKey < key[i])) { key[i+1] = key[i]; i--; } n++; key[i + 1] = newKey; } else{ while ((i >= 0) && (newKey < key[i])) { i--; } int insertChild = i + 1; // Subtree where new key must be inserted if(c[insertChild].isFull()){ // The root of the subtree where new key will be inserted has to be split // update keys and references accordingly   n++; c[n] = c[n-1]; for(int j = n - 1; j > insertChild; j--){ c[j] = c[j-1]; key[j] = key[j-1]; } key[insertChild] = c[insertChild].key[T - 1]; c[insertChild].n = T - 1;   BTreeNode newNode = new BTreeNode(T); for(int k = 0; k < T - 1; k++){ newNode.c[k] = c[insertChild].c[k + T]; newNode.key[k] = c[insertChild].key[k + T]; }   newNode.c[T - 1] = c[insertChild].c[2*T-1]; newNode.n = T-1; newNode.isLeaf = c[insertChild].isLeaf; c[insertChild+1] = newNode;   if(newKey < key[insertChild]){ c[insertChild].insert(newKey);   } else{ c[insertChild + 1].insert(newKey);   } } else c[insertChild].insert(newKey);   } } else return; } }   public class BTree{ private BTreeNode root; private int T; //2T is the maximum number of children a node can have private int height; private int firstLeaf;   public void insert(int newKey){ if (root.isFull()){//Split root; split(); height++; } root.insert(newKey); } }```