title: B tree implementation to B+ tree
body: <p>im trying to create a B+ tree from a previous B tree implementation I create, but Im really lost here... the only difference from B to B+ im trying to implement, is storing the keys on the leaves instead of removing them. 
  <br>Example: 
  <br>Final B Tree
  <br>3 6 false
  <br>1 2 true
  <br>4 5 true
  <br>7 8 9 10 true</p>
  
  <hr>
  
  <p>Final B+ Tree
  <br>3 6 false
  <br>1 2 true
  <br>3 4 5 true
  <br>6 7 8 9 10 true   </p>
  
  <hr>
  
  <p><br>This is what I have for a B Tree (I really didnt want to post the whole code, but explaining all of it will be harder and confusing). I would appreciate at least some ideas... 
  <br>
  <br> MAIN</p>
  
  <pre><code>  public class BTreeTest{
  
  public static void main(String[] args)   {
  Random generator = new Random();
  BTree T = new BTree(3);
  
  final int INSERTS = 50;          // how many elements are inserted
  final int VALUE_LIMIT = 1000;    // generated integers up to VALUE_LIMIT
  int[] values = new int[INSERTS]; // array can be used to print insert order
                                   // or to test other methods
  for (int i=0;i&lt;INSERTS;i++){
    int val = generator.nextInt(VALUE_LIMIT);
    values[i] = val;
    T.insert(val);      
  }
  T.printNodes();
  }}
  </code></pre>
  
  <p><br> B tree NODE</p>
  
  <pre><code>  public class BTreeNode{
    public int[] key;
    public BTreeNode[] c;
    boolean isLeaf;
    public int n;
    private int T; //Each node has at least T-1 and at most 2T-1 keys
  
    public  BTreeNode(int t){
     T = t;
     isLeaf = true;
     key = new int[2*T-1];
     c = new BTreeNode[2*T];
     n=0; 
   }
  
   public boolean isFull(){
     return n==(2*T-1);
   }
  
     public void insert(int newKey){
  // Insert new key to current node
  // We make sure that the current node is not full by checking and
  // splitting if necessary before descending to node
  
  //System.out.println("inserting " + newKey); // Debugging code
  int i=n-1;
  if (isLeaf){
    while ((i&gt;=0)&amp;&amp; (newKey&lt;key[i])) {
      key[i+1] = key[i];
      i--;
    }
    n++;
    key[i+1]=newKey;
  }
  else{
    while ((i&gt;=0)&amp;&amp; (newKey&lt;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
      // We promote the mediand of that root to the current node and
      // update keys and references accordingly
  
      //System.out.println("This is the full node we're going to break ");
      // Debugging     code
      //c[insertChild].printNodes();
      //System.out.println("going to promote " + c[insertChild].key[T-1]);
      n++;
      c[n]=c[n-1];
      for(int j = n-1;j&gt;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&lt;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;
  
      //System.out.println("This is the left side ");
      //c[insertChild].printNodes(); 
      //System.out.println("This is the right side ");
      //c[insertChild+1].printNodes();
      //c[insertChild+1].printNodes();
  
      if (newKey &lt;key[insertChild]){
        c[insertChild].insert(newKey);     }
      else{
        c[insertChild+1].insert(newKey);    }
    }
    else
      c[insertChild].insert(newKey);
  }
   }
  
   public void print(){
  //Prints all keys in the tree in ascending order
  if (isLeaf){
    for(int i =0; i&lt;n;i++)
      System.out.print(key[i]+" ");
    System.out.println();
  }
  else{
    for(int i =0; i&lt;n;i++){
      c[i].print();
      System.out.print(key[i]+" ");
    }
    c[n].print();
  }
  }
  
   public void printNodes(){
  //Prints all keys in the tree, node by node, using preorder
  //It also prints the indicator of whether a node is a leaf
  //Used mostly for debugging purposes
  printNode();
  if (!isLeaf){
    for(int i =0; i&lt;=n;i++){
      c[i].printNodes();
    }
  }
   }
   public void printNode(){
   //Prints all keys in node
  for(int i =0; i&lt;n;i++)
    System.out.print(key[i]+" ");
  System.out.println(isLeaf);
  }
   }
  </code></pre>
  
  <p><br> B Tree </p>
  
  <pre><code>      public class BTree{
        private BTreeNode root;
        private int T; //2T is the maximum number of childen a node can have
        private int height;
  
    public BTree(int t){
      root = new BTreeNode(t);
      T = t;
      height = 0;
    }
  
    public void printHeight(){
      System.out.println("Tree height is "+height);
    }
  
    public void insert(int newKey){
      if (root.isFull()){//Split root;
       split();
       height++;
     }
      root.insert(newKey);
      } 
  
    public void print(){
     // Wrapper for node print method
      root.print();
      }
  
    public void printNodes(){
      // Wrapper for node print method
      root.printNodes();
      }
  
    public void split(){
  // Splits the root into three nodes.
  // The median element becomes the only element in the root
  // The left subtree contains the elements that are less than the median
  // The right subtree contains the elements that are larger than the median
  // The height of the tree is increased by one
  
  //System.out.println("Before splitting root");
  //root.printNodes(); // Code used for debugging
  BTreeNode leftChild = new BTreeNode(T);
  BTreeNode rightChild = new BTreeNode(T);
  leftChild.isLeaf = root.isLeaf;
  rightChild.isLeaf = root.isLeaf;
  leftChild.n = T-1;
  rightChild.n = T-1;
  int median = T-1;
  for (int i = 0;i&lt;T-1;i++){
    leftChild.c[i] = root.c[i];
    leftChild.key[i] = root.key[i];
  }
  leftChild.c[median]= root.c[median];
  for (int i = median+1;i&lt;root.n;i++){
    rightChild.c[i-median-1] = root.c[i];
    rightChild.key[i-median-1] = root.key[i];
  }
  rightChild.c[median]=root.c[root.n];
  root.key[0]=root.key[median];
  root.n = 1;
  root.c[0]=leftChild;
  root.c[1]=rightChild;
  root.isLeaf = false;
  //System.out.println("After splitting root");
  //root.printNodes();
   }}
  </code></pre>