B-tree

BTree.java

package com.simpledb.misc;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BTree {

	private static final int ORDER = 3;

	private int height = 0;
	private Node root = null;

	public BTree() {
	}

	public void split(Node node) {
		Node parentNode = node.parent;
		if (parentNode == null) {
			parentNode = new Node();
			root = parentNode;
			height++;
		}

		Node leftNode = new Node();
		leftNode.parent = parentNode;
		leftNode.addEntries(node.getLeftEntries());

		Node rightNode = new Node();
		rightNode.parent = parentNode;
		rightNode.rightMost = node.rightMost;
		rightNode.addEntries(node.getRightEntries());

		Entry centerEntry = node.getCenterEntry();
		Entry leftEntry = node.getCenterLeftEntry();
		if (leftEntry != null) {
			leftNode.rightMost = centerEntry.left;
		}

		centerEntry.left = leftNode;
		parentNode.addEntry(centerEntry);

		Entry rightEntry = parentNode.rightEntry(centerEntry);
		if (rightEntry == null) {
			parentNode.rightMost = rightNode;
		} else {
			rightEntry.left = rightNode;
		}

		// update node's parent
		for (Entry e : leftNode.entries()) {
			if (e.left != null) {
				e.left.parent = leftNode;
			}
		}
		if (leftNode.rightMost != null) {
			leftNode.rightMost.parent = leftNode;
		}

		for (Entry e : rightNode.entries()) {
			if (e.left != null) {
				e.left.parent = rightNode;
			}
		}
		if (rightNode.rightMost != null) {
			rightNode.rightMost.parent = rightNode;
		}

		if (parentNode.entrySize() >= ORDER) {
			split(parentNode);
		}
	}

	public synchronized void insert(int key, String value, Node node) {
		if (node.rightMost == null) {
			node.addEntry(new Entry(key, value, node));

			if (node.entrySize() >= ORDER) {
				split(node);
			}
		} else {
			int index = 0;
			for (Entry entry : node.entries()) {
				if (key > entry.key) {
					index++;
					continue;
				} else if (key == entry.key) {
					return;
				} else if (key < entry.key) {
					insert(key, value, entry.left);
					return;
				}
			}
			if (index >= node.entrySize()) {
				insert(key, value, node.rightMost);
			}
		}
	}

	public void rebalance(Node node, Entry deleted) {
		Entry separator = null;
		Node parentNode = node.parent;
		List<Node> allChildNode = new ArrayList<Node>();
		for (Entry entry : parentNode.entries()) {
			if (entry.left == node) {
				separator = entry;
			}
			allChildNode.add(entry.left);
		}
		if (parentNode.rightMost == node) {
			separator = parentNode.lastEntry();
		}
		allChildNode.add(parentNode.rightMost);
		System.out.println("separator: " + separator);
		System.out.println("allChildNode: " + allChildNode);

		int index = allChildNode.indexOf(node);
		if (index < allChildNode.size() - 1
				&& allChildNode.get(index + 1).entrySize() > Math
						.ceil(ORDER / 2f) - 1) {
			System.out.println("rightSiblings");

			Node rightSiblings = allChildNode.get(index + 1);
			Entry rightSibling = rightSiblings.firstEntry();
			rightSibling.left = separator.left;
			separator.left = deleted.left;

			node.addEntry(separator);
			parentNode.removeEntry(separator);

			parentNode.addEntry(rightSibling);
			rightSiblings.removeEntry(rightSibling);

			System.out.println("parentNode: " + parentNode);
			System.out.println("rightSiblings: " + rightSiblings);
			System.out.println("node: " + node);
			return;
		} else if (index > 0
				&& allChildNode.get(index - 1).entrySize() > Math
						.ceil(ORDER / 2f) - 1) {
			System.out.println("leftSiblings");
			// update separator if left sibling
			separator = parentNode.leftEntry(separator);

			Node leftSiblings = allChildNode.get(index - 1);
			Entry leftSibling = leftSiblings.lastEntry();
			System.out.println("leftSibling: " + leftSibling);
			leftSibling.left = separator.left;
			separator.left = deleted.left;

			node.addEntry(separator);
			parentNode.removeEntry(separator);

			parentNode.addEntry(leftSibling);
			leftSiblings.removeEntry(leftSibling);

			System.out.println("parentNode: " + parentNode);
			System.out.println("leftSiblings: " + leftSiblings);
			System.out.println("node: " + node);
			return;
		} else {
			Node newNode = new Node();
			newNode.addEntries(node.entries());
			if (index < allChildNode.size() - 1) {
				Node rightSiblings = allChildNode.get(index + 1);
				newNode.addEntries(rightSiblings.entries());
				separator.left = node.rightMost;
				newNode.rightMost = rightSiblings.rightMost;
				System.out.println("rightSiblings: " + rightSiblings);
			} else if (index > 0) {
				Node leftSiblings = allChildNode.get(index - 1);
				newNode.addEntries(leftSiblings.entries());
				separator.left = leftSiblings.rightMost;
				if (node.entrySize() > 0) {
					newNode.rightMost = node.firstEntry().left;
				} else {
					newNode.rightMost = node.rightMost;
				}
				System.out.println("leftSiblings: " + leftSiblings);
			}
			newNode.addEntry(separator);

			// update new node child's parent
			for (Entry e : newNode.entries()) {
				if (e.left != null) {
					e.left.parent = newNode;
				}
			}
			if (newNode.rightMost != null) {
				newNode.rightMost.parent = newNode;
			}

			// update new node's parent
			newNode.parent = parentNode;

			Entry rightEntry = parentNode.rightEntry(separator);
			if (rightEntry != null) {
				rightEntry.left = newNode;
			} else {
				parentNode.rightMost = newNode;
			}

			parentNode.removeEntry(separator);

			System.out.println("newNode: " + newNode);
			System.out.println("parentNode: " + parentNode);

			if (parentNode.entrySize() < Math.ceil(ORDER / 2f) - 1) {
				if (parentNode.parent == null) {
					newNode.parent = null;
					root = newNode;
					height--;
				} else {
					rebalance(parentNode, separator);
				}
			}
		}
	}

	public void delete(Entry entry) {
		Node node = getEntryNode(entry, this.root);
		System.out.println("entry in node: " + node);

		if (node.rightMost == null) {
			node.removeEntry(entry);
			if (node.entrySize() < Math.ceil(ORDER / 2f) - 1 && height != 0) {
				rebalance(node, entry);
			}
		} else {
			Node rightMostNode = entry.left;
			while (rightMostNode.rightMost != null) {
				rightMostNode = rightMostNode.rightMost;
			}
			Entry leftLargest = rightMostNode.lastEntry();
			rightMostNode.removeEntry(leftLargest);
			entry.key = leftLargest.key;
			entry.value = leftLargest.value;
			rebalance(rightMostNode, leftLargest);
		}
	}

	public Node getEntryNode(Entry en, Node node) {
		if (node == null) {
			return null;
		} else {
			int index = 0;
			for (Entry entry : node.entries()) {
				if (en.key > entry.key) {
					index++;
					continue;
				} else if (en.key == entry.key) {
					return node;
				} else if (en.key < entry.key) {
					return getEntryNode(en, entry.left);
				}
			}
			if (index >= node.entrySize()) {
				return getEntryNode(en, node.rightMost);
			}
		}

		return null;
	}

	public Entry search(int key, Node node) {
		if (node == null) {
			return null;
		} else {
			int index = 0;
			for (Entry entry : node.entries()) {
				if (key > entry.key) {
					index++;
					continue;
				} else if (key == entry.key) {
					return entry;
				} else if (key < entry.key) {
					return search(key, entry.left);
				}
			}
			if (index >= node.entrySize()) {
				return search(key, node.rightMost);
			}
		}

		return null;
	}

	public void print(Node node, int level) {
		if (level > height) {
			// System.out.println("level: " + level);
			return;
		} else {
			for (Entry entry : node.entries()) {
				System.out.println("level: " + level + ", entry: "
						+ entry.toString());
				print(entry.left, level + 1);
			}
			print(node.rightMost, level + 1);
		}
	}

	public static void main(String[] args) {
		BTree btree = new BTree();
		btree.root = new Node();

		for (int i = 7; i >= 1; i--) {
			insert(btree, i);
		}

		for (int i = 1 - 2; i <= 7 + 2; i++) {
			Entry entry = btree.search(i, btree.root);
			System.out.println("search " + i + ", entry: " + entry);
			System.out.println();
		}

		for (int i = 1; i <= 7; i++) {
			delete(btree, i);
		}

		for (int i = 1; i <= 7; i++) {
			insert(btree, i);
		}

		for (int i = 7; i >= 1; i--) {
			delete(btree, i);
		}

		for (int i = 1; i <= 7; i++) {
			insert(btree, i);
		}

		delete(btree, 7);
		delete(btree, 3);

		insert(btree, 3);
		insert(btree, 7);

		delete(btree, 1);
		delete(btree, 5);

		insert(btree, 5);
		insert(btree, 1);
	}

	private static void insert(BTree btree, int i) {
		System.out.println("insert " + i);
		btree.insert(i, String.valueOf((char) ('a' + i - 1)), btree.root);
		btree.print(btree.root, 0);
		System.out.println();
	}

	private static void delete(BTree btree, int i) {
		System.out.println("delete " + i);
		Entry entry = btree.search(i, btree.root);
		btree.delete(entry);
		btree.print(btree.root, 0);
		System.out.println();
	}
}

class Node {
	private List<Entry> entries = new ArrayList<Entry>();

	public Node parent;
	public Node rightMost;

	@Override
	public String toString() {
		return entries.toString();
	}

	public void addEntry(Entry entry) {
		entries.add(entry);
		Collections.sort(entries);
	}

	public Entry firstEntry() {
		if (entrySize() > 0) {
			return entries.get(0);
		}

		return null;
	}

	public Entry lastEntry() {
		if (entrySize() > 0) {
			return entries.get(entrySize() - 1);
		}

		return null;
	}

	public void removeEntry(int key) {
		for (Entry entry : entries) {
			if (entry.key == key) {
				entries.remove(entry);
				break;
			}
		}
	}

	public void removeEntry(Entry entry) {
		entries.remove(entry);
	}

	public void addEntries(List<Entry> entries) {
		this.entries.addAll(entries);
		Collections.sort(this.entries);
	}

	public List<Entry> entries() {
		return entries;
	}

	public int entrySize() {
		return entries.size();
	}

	public List<Entry> getLeftEntries() {
		return this.entries.subList(0, entrySize() / 2);
	}

	public List<Entry> getRightEntries() {
		return this.entries.subList(entrySize() / 2 + 1, entrySize());
	}

	public Entry getCenterEntry() {
		return this.entries.get(entrySize() / 2);
	}

	public Entry getCenterLeftEntry() {
		return this.entries.get(entrySize() / 2 - 1);
	}

	public Entry getCenterRightEntry() {
		return this.entries.get(entrySize() / 2 + 1);
	}

	public Entry leftEntry(Entry entry) {
		int index = this.entries.indexOf(entry);
		if (index > 0 && index < entrySize()) {
			return this.entries.get(index - 1);
		}

		return null;
	}

	public Entry rightEntry(Entry entry) {
		int index = this.entries.indexOf(entry);
		if (index >= 0 && index < entrySize() - 1) {
			return this.entries.get(index + 1);
		}

		return null;
	}
}

class Entry implements Comparable<Entry> {
	public int key;
	public String value;
	public Node left;

	public Entry(int key, String value, Node container) {
		this.key = key;
		this.value = value;
	}

	@Override
	public String toString() {
		return String.format("[%d,%s,%s]", key, value, left);
	}

	@Override
	public int compareTo(Entry o) {
		return this.key - o.key;
	}
}