I've just started learning about BTrees and B+ Trees and I'm a little lost. I have 3 classes that implement the insert method for BTrees. BTreeNode, BTree, and BTreeTest. What I want to know is that besides changing the number of keys for the internal nodes from 2T-1 to M-1, and the children from 2T to M, number of keys for the leafs from 2T-1 to L, and the number of children from 2T to M, how else would I need to change my code in order for it to work for B+ Trees. On my BTreeNode class I have the insert method and on the BTree class I have it to where it checks if you have to split the root before inserting a new key. The duplicate method just makes sure there's no duplicates.
These are my methods:
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); } }
Any help would be appreciated. Thanks in advance.