Index: generic/src/adt/btree.c
===================================================================
--- generic/src/adt/btree.c	(revision 40378479b8bf47b5c6ddf534dfbafae2c8441d34)
+++ generic/src/adt/btree.c	(revision c715e9b93d5ce15f27506aa32b70bfc97c8630bf)
@@ -43,4 +43,8 @@
  * 	  There is always pointer to the left-hand side subtree
  * 	  (i.e. left sibling) in the parent node.
+ *
+ * Be carefull when using these trees. They need to allocate
+ * and deallocate memory for their index nodes and as such
+ * can sleep.
  */
 
@@ -56,4 +60,5 @@
 static void node_initialize(btree_node_t *node);
 static void node_insert_key(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
+void node_remove_key(btree_node_t *node, __native key);
 static btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median);
 
@@ -179,38 +184,55 @@
 {
 	btree_node_t *cur, *next;
-	void *val = NULL;
-	
-	/*
-	 * Iteratively descend to the leaf that can contain searched key.
+	
+	/*
+	 * Iteratively descend to the leaf that can contain the searched key.
 	 */
 	for (cur = t->root; cur; cur = next) {
-		int i;
-	
+
 		/* Last iteration will set this with proper leaf node address. */
 		*leaf_node = cur;
-		for (i = 0; i < cur->keys; i++) {
-			if (key <= cur->key[i]) {
-				val = cur->value[i];
-				next = cur->subtree[i];
-				
-				/*
-				 * Check if there is anywhere to descend.
-				 */
-				if (!next) {
-					/*
-					 * Leaf-level.
-					 */
-					return (key == cur->key[i]) ? val : NULL;
-				}
-				goto descend;
+		
+		/*
+		 * The key can be in the leftmost subtree.
+		 * Test it separately.
+		 */
+		if (key < cur->key[0]) {
+			next = cur->subtree[0];
+			continue;
+		} else {
+			void *val;
+			int i;
+		
+			/*
+			 * Now if the key is smaller than cur->key[i]
+			 * it can only mean that the value is in cur->subtree[i]
+			 * or it is not in the tree at all.
+			 */
+			for (i = 1; i < cur->keys; i++) {
+				if (key < cur->key[i]) {
+					next = cur->subtree[i];
+					val = cur->value[i - 1];
+
+					if (LEAF_NODE(cur))
+						return key == cur->key[i - 1] ? val : NULL;
+
+					goto descend;
+				} 
 			}
-		}
-		next = cur->subtree[i];
-	descend:
-		;
-	}
-
-	/*
-	 * The key was not found in the *leaf_node and is greater than any of its keys.
+			
+			/*
+			 * Last possibility is that the key is in the rightmost subtree.
+			 */
+			next = cur->subtree[i];
+			val = cur->value[i - 1];
+			if (LEAF_NODE(cur))
+				return key == cur->key[i - 1] ? val : NULL;
+		}
+		descend:
+			;
+	}
+
+	/*
+	 * The key was not found in the *leaf_node and is smaller than any of its keys.
 	 */
 	return NULL;
@@ -273,5 +295,5 @@
 }
 
-/** Insert key-value-left-subtree triplet into B-tree non-full node.
+/** Insert key-value-right-subtree triplet into B-tree non-full node.
  *
  * It is actually possible to have more keys than BTREE_MAX_KEYS.
@@ -308,14 +330,14 @@
 }
 
-/** Split full B-tree node and insert new key-value-left-subtree triplet.
+/** Split full B-tree node and insert new key-value-right-subtree triplet.
  *
  * This function will split a node and return pointer to a newly created
- * node containing keys greater than the lesser of medians (or median)
- * of the old keys and the newly added key. It will also write the
- * median key to a memory address supplied by the caller.
- *
- * If the node being split is an index node, the median will be
- * removed from the original node. If the node is a leaf node,
- * the median will be preserved.
+ * node containing keys greater than or equal to the greater of medians
+ * (or median) of the old keys and the newly added key. It will also write
+ * the median key to a memory address supplied by the caller.
+ *
+ * If the node being split is an index node, the median will not be
+ * included in the new node. If the node is a leaf node,
+ * the median will be copied there.
  *
  * @param node B-tree node wich is going to be split.
@@ -343,6 +365,9 @@
 	 * Compute median of keys.
 	 */
-	*median = MEDIAN_LOW(node);
-		
+	*median = MEDIAN_HIGH(node);
+		
+	/*
+	 * Allocate and initialize new right sibling.
+	 */
 	rnode = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
 	node_initialize(rnode);
@@ -352,6 +377,8 @@
 	/*
 	 * Copy big keys, values and subtree pointers to the new right sibling.
-	 */
-	for (i = MEDIAN_LOW_INDEX(node) + 1, j = 0; i < node->keys; i++, j++) {
+	 * If this is an index node, do not copy the median.
+	 */
+	i = (int) INDEX_NODE(node);
+	for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
 		rnode->key[j] = node->key[i];
 		rnode->value[j] = node->value[i];
@@ -368,15 +395,18 @@
 	if (rnode->subtree[j])
 		rnode->subtree[j]->parent = rnode;
-	rnode->keys = j;
-	
-	/*
-	 * Shrink the old node.
-	 * If this is an index node, remove the median.
-	 */
-	node->keys = MEDIAN_LOW_INDEX(node) + 1;
-	if (INDEX_NODE(node))
-		node->keys--;
+
+	rnode->keys = j;	/* Set number of keys of the new node. */
+	node->keys /= 2;	/* Shrink the old node. */
 		
 	return rnode;
+}
+
+/** Remove key from B-tree node.
+ *
+ * @param node B-tree node.
+ * @param key Key to be removed.
+ */
+void node_remove_key(btree_node_t *node, __native key)
+{
 }