Sort of...
The code works for M >= 4, where M is the number of maximum key-value pairs in one node (In fact, this number can never be reached because the node will be split into two once this number is reached.
For rules on how B-Tree works, refer to this post. I may update this blog when I fix the deletion issue with M = 3 (probably rewrite the code to make it cleaner). Moreover, it turns out Cassandra has a B-Tree implementation. It's a little bit to complicated for me (plus I couldn't find its deletion implementation), but it's interesting to take a look. Check here.
package bTree;
/**
* M: maximum degree/number of key-value pairs in a node
* HT:height of the B-tree
* N: number of key-value pairs in the tree
* @author shirleyyoung
*
* @param
* @param
*/
public class BTree <Key extends Comparable<Key>, Value>{
private int M;
private Node root;
private int HT;
private int N;
/******************************************************
* The structure to store the key-value pairs
* @author shirleyyoung
*
******************************************************/
private class Entry <Key extends Comparable<Key>, Value> implements Comparable{
private Comparable key;
private Object value;
public Entry(Comparable key, Object value){
this.key = key;
this.value = value;
}
public int compareTo(Entry e) {
return key.compareTo(e.key);
}
public String toString(){
return "(" + key.toString() + ", " + value.toString() + ")";
}
}
/***************************************************************
* tree node class
* Each node is a list of Entry objects
* Entry list is used for all key - value pairs stored in the node
* index: the current number of key-value pairs,
* as well as the index where next key-value pair will be added
* since it's 0 index, the node contains m + 1 key - value pairs
* entryList: the entryList
* children: children list of the node, each node may have at most
* M + 1 children
* @author shirleyyoung
*
***************************************************************/
private class Node indexToAdd; i--)
entryList[i] = entryList[i - 1];
entryList[indexToAdd] = e;
index++;
}
public String toString(){
String s = "";
for (int i = 0; i < index; i++){
s += entryList[i].toString() + ", ";
}
s = s.substring(0, s.length() - 2);
s += String.format("\nindex: %d\n", index);
return s;
}
}
/*******************************************************
* constructor
* @param M
********************************************************/
public BTree(){
M = 4;
HT = 0;
N = 0;
root = new Node();
}
public BTree(int M){
this();
this.M = M;
root = new Node();
}
/********************************************************
* search for a value given the key
* @param key
* @return
*******************************************************/
public Object get(Comparable key){
Entry found = search(root, key, HT);
if (found == null){
System.out.println("No such key!");
return null;
}
else return found.value;
}
private Entry search(Node x, Comparable key, int ht){
if (x == null)
return null;
Entry[] entryList = x.entryList;
if(ht == 0){//leaf node
for(int j = 0; j < x.index; j++){
if(key.equals(entryList[j].key))
return entryList[j];
}
} else{
for(int j = 0; j < x.index; j++){
if (key.equals(entryList[j].key))
return entryList[j];
else if(j == 0 && key.compareTo(entryList[j].key) < 0)
return search(x.children[j], key, ht - 1);
else if(j == x.index - 1|| key.compareTo(entryList[j + 1].key) < 0)
return search(x.children[j + 1], key, ht - 1);
}
}
return null;
}
/*******************************************************
* Insertion
* @param key
* @param value
*******************************************************/
public void insert(Comparable key, Object value){
Entry exists = search(root, key, HT);
if(exists != null){
exists.value = value;
System.out.println("Key already exists, modify the value to the input value.");
return;
}
Node newRoot = insert(root, key, value, HT);
N++;
if(newRoot == null) return;
root = newRoot;
HT++;
}
private Node insert(Node curr, Comparable key, Object value, int ht){
int indexToInsert;
if(ht == 0){//leaf nodes level
//find the correct place to insert the value
for(indexToInsert = 0; indexToInsert < curr.index; indexToInsert++){
if(key.compareTo(curr.entryList[indexToInsert].key) < 0) break;
}
//shift the larger nodes right
curr.add(new Entry(key, value), indexToInsert);
//the key value pair is added to the existing node, no new node is inserted, return null
if(curr.index < M) return null;
return split(curr);
}else {
for(indexToInsert = 0; indexToInsert < curr.index; indexToInsert++){
if (indexToInsert == 0 && key.compareTo(curr.entryList[indexToInsert].key) < 0) break;
else if((indexToInsert == curr.index - 1) || key.compareTo(curr.entryList[indexToInsert + 1].key) < 0){
//children[j].next, j++
indexToInsert += 1;
break;
}
}
Node u = insert(curr.children[indexToInsert], key, value, ht - 1);
if(u == null) return null;
return combine(curr, u);
}
}
/*********************************************************
* split the node if it reaches maximum degree
* choose middle node as the new root
* e.g., if M = 4 or 5, choose entryList[2] as new root
* @param curr
* @return
*********************************************************/
private Node split(Node curr){
Node newRoot = new Node();
newRoot.entryList[0] = curr.entryList[M/2];
newRoot.index++;
Node right = new Node();
int j = 0, i = M/2 + 1;
while(j < M && i < M){
right.entryList[j] = curr.entryList[i];
right.children[j++] = curr.children[i++];
}
right.children[j] = curr.children[i];
right.index = j;
curr.index = M/2;
newRoot.children[0] = curr;
newRoot.children[1] = right;
return newRoot;
}
/****************************************************
* combine two nodes when total elements
* are less than M
* split the node if the entry list of the
* combined node reaches M
* @param left
* @param right
* @return
****************************************************/
private Node combine(Node left, Node right){
int j = 0;
int total = left.index + right.index;
while (left.index < total){
left.entryList[left.index] = right.entryList[j];
left.children[left.index++] = right.children[j++];
}
left.children[left.index] = right.children[j];
right.children = null;
right = null;
if (left.index < M) {return null;}
else return split(left);
}
/****************************************************
* Deletion
* @param key
* @return
****************************************************/
public Object delete(Comparable key){
Entry toDelete = search(root, key, HT);
if(toDelete == null) {
System.out.println("No such key!");
return null;
}
N--;
return delete(root, key, HT).value;
}
private Entry delete(Node n, Comparable key, int ht){
int index = n.searchEntry(key);
if(ht == 0){ // if leaf nodes
if(n.entryList[index].key != key)
return null;
else
return n.removeEntry(index);
}else {
if (key.equals(n.entryList[index].key)){ //if key is in internal node n
//if left children has a size larger than M/2
//replace entry that has the key to be deleted in n with the largest
//entry in left children, then recursively delete children entry
//System.out.println("found index: " + index);
Entry toDelete = n.entryList[index];
int h = ht - 1;
if(n.children[index].index >= M/2){
Node child = n.children[index];
while (h != 0){
child = child.children[child.index];
h--;
}
n.entryList[index] = child.entryList[child.index - 1];
delete(n.children[index], child.entryList[child.index - 1].key, ht - 1);
//else if right children has a size larger than M/2
//replace entry has the key to be deleted in n with the smallest
//entry in right children, then recursively delete children entry
} else if (n.children[index + 1].index >= M/2){
Node child = n.children[index + 1];
while(h != 0){
child = child.children[0];
h--;
}
n.entryList[index] = child.entryList[0];
delete(child, child.entryList[0].key, h);
//case 3 will take care of the case when node n has too few entries to be moved
} else {
n = moveEntryDown(n.children[index], n, index, n.children[index + 1]);
if (ht == HT && root.index == 0){
root = n;
HT--;
ht--;
}
delete(n, key, ht);
}
return toDelete;
} else { // if key is not in internal node n
//find the root of the subtree where the desired key is
//supposed to present
//System.out.println("index: " + index);
//System.out.println("children[index] has index: " + n.children[index].index);
//Node child = n.children[index];
//System.out.println("Largest children key: " + child.entryList[child.index - 1].key);
if(index == (n.index - 1) && key.compareTo(n.entryList[n.index - 1].key) > 0){
//child = n.children[index + 1];
index += 1;
}
//if key is in the children
boolean chk = key == n.children[index].entryList[n.children[index].searchEntry(key)].key;
if (n.children[index].index < M/2 && chk){
//case 3a, left sibling has size at least M/2
//remove the last entry from the left sibling, put into n[index - 1]
//add n[index - 1] to the n.children[index]
if(index > 0 && n.children[index - 1].index >= M/2){
Node helper = n.children[index - 1];
n.children[index].add(n.entryList[index - 1], 0);
n.entryList[index - 1] = helper.entryList[helper.index - 1];
helper.removeEntry(helper.index - 1);
//case 3a, right sibling has size at least M/2
} else if (index < n.index && n.children[index + 1].index >= M/2){
Node helper = n.children[index + 1];
n.children[index].add(n.entryList[index], n.children[index].index);
n.entryList[index] = helper.entryList[0];
helper.removeEntry(0);
//case 3b, merge two nodes
} else {
Node mergeChild = n.children[index];
if(index == n.index)
n = moveEntryDown(n.children[index - 1], n, index - 1, mergeChild);
else n = moveEntryDown(mergeChild, n, index, n.children[index + 1]);
if (ht == HT && root.index == 0){
root = n;
HT--;
ht--;
}
return delete(n, key, ht);
}
}
if (index == n.index - 1 && key.compareTo(n.entryList[index].key) > 0)
return delete(n.children[index + 1], key, ht - 1);
else return delete(n.children[index], key, ht - 1);
}
}
}
/**
* combine left and right children and move the entry (parent[index]) down
* to serve as median node
* only be called when both left and right has size < M/2
* and parent has size >= M/2
* @param left
* @param parent
* @param index
* @param right
*/
private Node moveEntryDown(Node left, Node parent, int index, Node right){
left.add(parent.entryList[index], left.index);
parent.removeEntry(index);
combine(left, right);
if (parent.index == 0)
parent = left;
else parent.children[index] = left;
return parent;
}
public String toString(){
return toString(root, HT) + "\n";
}
private String toString(Node n, int ht){
String s = "";
if(ht == 0){
for(int i = 0; i < n.index; i++)
s += i + ": " + n.entryList[i].toString() + "\n";
} else{
for(int i = 0; i < n.index; i++){
s += i + ": " + n.entryList[i].toString() + "\nChildren " + i + ": \n";
s += toString(n.children[i], ht - 1) + "\n";
}
s += toString(n.children[n.index], ht - 1);
}
return s;
}
public int size(){
return N;
}
public int height(){
return HT + 1;
}
}
Check my git for test code.
