Add new code

Signed-off-by: Carlos Maiolino <[email protected]>

18 files changed, 1399 insertions, 0 deletions

diff --git a/Algorithms/bplus-tree/src/bplus_foreach.c b/Algorithms/bplus-tree/src/bplus_foreach.c
new file mode 100644
index 0000000..e9184b7
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_foreach.c
@@ -0,0 +1,39 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#include "bplus_foreach.h"
+
+#include "bplus_node.h"
+
+void bplus_foreach_item_in_node(BplusTree* tree, BplusNode* node, BplusForeachItemFunc* foreach, void* argument)
+{
+    if (!node->is_leaf)
+        for (size_t i = 0; i < node->length; ++i)
+            bplus_foreach_item_in_node(tree, bplus_node_at(node, i), foreach, argument);
+
+    else
+        for (size_t i = 0; i < node->length; ++i)
+            foreach(tree, node->items + i, argument);
+
+}
+
+void bplus_foreach_item_in_tree(BplusTree* tree, BplusForeachItemFunc* foreach, void* argument)
+{
+    bplus_foreach_item_in_node(tree, tree->root, foreach, argument);
+}
+
+void bplus_foreach_node_in_node(BplusTree* tree, BplusNode* node, BplusForeachNodeFunc* foreach, void* argument)
+{
+    if (!node->is_leaf)
+        for (size_t i = 0; i < node->length; ++i)
+            bplus_foreach_node_in_node(tree, bplus_node_at(node, i), foreach, argument);
+
+    foreach(tree, node, argument);
+}
+
+void bplus_foreach_node_in_tree(BplusTree* tree, BplusForeachNodeFunc* foreach, void* argument)
+{
+    bplus_foreach_node_in_node(tree, tree->root, foreach, argument);
+}
diff --git a/Algorithms/bplus-tree/src/bplus_foreach.h b/Algorithms/bplus-tree/src/bplus_foreach.h
new file mode 100644
index 0000000..69849a6
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_foreach.h
@@ -0,0 +1,27 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#ifndef __BPLUS_FOREACH_H__
+#define __BPLUS_FOREACH_H__
+
+#include "bplus_tree_private.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif // ifdef __cplusplus
+
+void bplus_foreach_item_in_node(BplusTree* tree, BplusNode* node, BplusForeachItemFunc* foreach, void* argument);
+void bplus_foreach_item_in_tree(BplusTree* tree, BplusForeachItemFunc* foreach, void* argument);
+
+typedef void (BplusForeachNodeFunc)(BplusTree* tree, BplusNode* node, void* argument);
+void bplus_foreach_node_in_node(BplusTree* tree, BplusNode* node, BplusForeachNodeFunc* foreach, void* argument);
+void bplus_foreach_node_in_tree(BplusTree* tree, BplusForeachNodeFunc* foreach, void* argument);
+
+#ifdef __cplusplus
+}
+#endif // ifdef __cplusplus
+
+#endif // ifndef __BPLUS_FOREACH_H__
diff --git a/Algorithms/bplus-tree/src/bplus_insert.c b/Algorithms/bplus-tree/src/bplus_insert.c
new file mode 100644
index 0000000..9cd3ea7
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_insert.c
@@ -0,0 +1,58 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#include "bplus_insert.h"
+
+#include "bplus_node.h"
+#include "bplus_search.h"
+#include "bplus_rebalance.h"
+
+#include <string.h>
+
+static void bplus_leaf_insert_at(BplusTree const* tree, BplusNode* node, size_t const index, BplusKey const key, BplusValue const value)
+{
+    g_return_if_fail(node != NULL);
+    g_return_if_fail(index <= node->length);
+
+    bplus_node_move_and_resize_data(tree, node, index + 1, index);
+    bplus_key_at(node, index)   = key;
+    bplus_value_at(node, index) = value;
+}
+
+void bplus_node_insert_at(BplusTree const* tree, BplusNode* node, size_t const index, size_t const length, BplusItem const* const items)
+{
+    g_return_if_fail(node != NULL);
+    g_return_if_fail(index <= node->length);
+    g_return_if_fail(node->length + length <= BPLUS_TREE_ORDER);
+
+    bplus_node_move_and_resize_data(tree, node, index + length, index);
+    memcpy(node->items + index, items, length * sizeof(BplusItem));
+
+    if (node->is_leaf)
+        return;
+
+    for (size_t i = index; i < index + length; ++i)
+        bplus_node_at(node, i)->parent = node;
+}
+
+void bplus_tree_insert(BplusTree* tree, BplusKey const key, BplusValue const value)
+{
+    BplusPath path;
+    bplus_tree_get_path_to_key(tree, key, &path);
+
+    size_t     index = path.index[0];
+    BplusNode* node  = (BplusNode*) path.leaf;
+
+    /* If the node is not empty, we will insert it after the given index */
+    if ((index < node->length) && bplus_key_lte(tree, bplus_key_at(node, index), key))
+        index++;
+
+    bplus_leaf_insert_at(tree, node, index, key, value);
+    if (index == 0)
+        bplus_rebalance_propagate(tree, &path);
+
+    if (bplus_node_overfilled(node))
+        bplus_rebalance_overfilled(tree, &path);
+}
diff --git a/Algorithms/bplus-tree/src/bplus_insert.h b/Algorithms/bplus-tree/src/bplus_insert.h
new file mode 100644
index 0000000..e73f963
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_insert.h
@@ -0,0 +1,22 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#ifndef __BPLUS_INSERT_H__
+#define __BPLUS_INSERT_H__
+
+#include "bplus_tree_private.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif // ifdef __cplusplus
+
+void bplus_node_insert_at(BplusTree const* tree, BplusNode* node, size_t const index, size_t const length, BplusItem const* const items);
+
+#ifdef __cplusplus
+}
+#endif // ifdef __cplusplus
+
+#endif // ifndef __BPLUS_INSERT_H__
diff --git a/Algorithms/bplus-tree/src/bplus_iterator.c b/Algorithms/bplus-tree/src/bplus_iterator.c
new file mode 100644
index 0000000..8ab796e
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_iterator.c
@@ -0,0 +1,161 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#include "bplus_iterator.h"
+
+#include "bplus_leaf.h"
+#include "bplus_search.h"
+
+static BplusIterator* bplus_iterator_new_full(BplusTree const* tree,
+                                              BplusLeaf const* leaf_from, BplusItem const* item_from,
+                                              BplusLeaf const* leaf_to, BplusItem const* item_to)
+{
+    BplusIterator* iterator = g_slice_new(BplusIterator);
+
+    iterator->leaf_from = leaf_from;
+    iterator->item_from = item_from;
+    iterator->leaf_to   = leaf_to;
+    iterator->item_to   = item_to;
+    iterator->item      = item_from;
+    iterator->leaf      = leaf_from;
+
+    return iterator;
+}
+
+static BplusIterator* bplus_iterator_new_to_last(BplusTree const* tree, BplusLeaf const* leaf_from, BplusItem const* item_from)
+{
+    return bplus_iterator_new_full(tree, leaf_from, item_from, tree->last, tree->last->node.items + tree->last->node.length);
+}
+
+static BplusIterator* bplus_iterator_new_from_first(BplusTree const* tree, BplusLeaf const* leaf_to, BplusItem const* item_to)
+{
+    return bplus_iterator_new_full(tree, tree->first, tree->first->node.items, leaf_to, item_to);
+}
+
+BplusIterator* bplus_iterator_new(BplusTree const* tree)
+{
+    return bplus_iterator_new_to_last(tree, tree->first, tree->first->node.items);
+}
+
+void bplus_iterator_destroy(BplusIterator* iterator)
+{
+    g_return_if_fail(iterator != NULL);
+
+    g_slice_free(BplusIterator, iterator);
+}
+
+gboolean bplus_iterator_next(BplusIterator* iterator)
+{
+    g_return_val_if_fail(iterator != NULL, FALSE);
+
+    BplusItem const* const next = iterator->item + 1;
+    BplusLeaf const* const leaf = iterator->leaf;
+    if (next == iterator->item_to)
+        return FALSE;
+
+    if (next - leaf->node.items < leaf->node.length)
+    {
+        ++iterator->item;
+    }
+    else
+    {
+        if (leaf->right == NULL)
+            return FALSE;
+
+        iterator->leaf = leaf->right;
+        iterator->item = leaf->right->node.items;
+    }
+
+    return TRUE;
+}
+
+gboolean bplus_iterator_previous(BplusIterator* iterator)
+{
+    g_return_val_if_fail(iterator != NULL, FALSE);
+
+    BplusItem const* const item = iterator->item;
+    BplusLeaf const* const leaf = iterator->leaf;
+
+    if (item == iterator->item_from)
+        return FALSE;
+
+    if (item - leaf->node.items == 0)
+    {
+        if (leaf->left == NULL)
+            return FALSE;
+
+        iterator->leaf = leaf->left;
+        iterator->item = leaf->left->node.items + leaf->left->node.length;
+    }
+
+    --iterator->item;
+
+    return TRUE;
+}
+
+BplusItem const* bplus_iterator_get_item(BplusIterator const* iterator)
+{
+    g_return_val_if_fail(iterator != NULL, NULL);
+
+    if (iterator->item_from == iterator->item_to)
+        return NULL;
+
+    return iterator->item;
+}
+
+BplusIterator* bplus_tree_first(BplusTree const* tree)
+{
+    g_return_val_if_fail(tree != NULL, NULL);
+
+    return bplus_iterator_new(tree);
+}
+
+BplusIterator* bplus_iterator_from_key(BplusTree const* tree, BplusKey const key)
+{
+    g_return_val_if_fail(tree != NULL, NULL);
+
+    BplusPath path_from;
+    BplusPath path_to;
+    bplus_tree_get_paths_to_key_range(tree, key, key, &path_from, &path_to);
+
+    return bplus_iterator_new_to_last(tree, (BplusLeaf*) path_from.leaf, path_from.leaf->items + path_from.index[0]);
+}
+
+BplusIterator* bplus_iterator_to_key(BplusTree const* tree, BplusKey const key)
+{
+    g_return_val_if_fail(tree != NULL, NULL);
+
+    BplusPath path_from;
+    BplusPath path_to;
+    bplus_tree_get_paths_to_key_range(tree, key, key, &path_from, &path_to);
+
+    return bplus_iterator_new_from_first(tree, (BplusLeaf*) path_to.leaf, path_to.leaf->items + path_to.index[0]);
+}
+
+BplusIterator* bplus_iterator_for_key(BplusTree const* tree, BplusKey const key)
+{
+    g_return_val_if_fail(tree != NULL, NULL);
+
+    BplusPath path_from;
+    BplusPath path_to;
+    bplus_tree_get_paths_to_key_range(tree, key, key, &path_from, &path_to);
+
+    return bplus_iterator_new_full(tree,
+                                   (BplusLeaf*) path_from.leaf, path_from.leaf->items + path_from.index[0],
+                                   (BplusLeaf*) path_to.leaf, path_to.leaf->items + path_to.index[0]);
+}
+
+BplusIterator* bplus_iterator_for_key_range(BplusTree const* tree, BplusKey const key_from, BplusKey const key_to)
+{
+    g_return_val_if_fail(tree != NULL, NULL);
+
+    BplusPath path_from;
+    BplusPath path_to;
+    bplus_tree_get_paths_to_key_range(tree, key_from, key_to, &path_from, &path_to);
+
+    return bplus_iterator_new_full(tree,
+                                   (BplusLeaf*) path_from.leaf, path_from.leaf->items + path_from.index[0],
+                                   (BplusLeaf*) path_to.leaf, path_to.leaf->items + path_to.index[0]);
+}
diff --git a/Algorithms/bplus-tree/src/bplus_iterator.h b/Algorithms/bplus-tree/src/bplus_iterator.h
new file mode 100644
index 0000000..c7ae9b2
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_iterator.h
@@ -0,0 +1,31 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#ifndef __BPLUS_ITERATOR_H__
+#define __BPLUS_ITERATOR_H__
+
+#include "bplus_tree_private.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif // ifdef __cplusplus
+
+struct _BplusIterator
+{
+    BplusItem const* item;
+    BplusLeaf const* leaf;
+
+    BplusLeaf const* leaf_from;
+    BplusItem const* item_from;
+    BplusLeaf const* leaf_to;
+    BplusItem const* item_to;
+};
+
+#ifdef __cplusplus
+}
+#endif // ifdef __cplusplus
+
+#endif // ifndef __BPLUS_ITERATOR_H__
diff --git a/Algorithms/bplus-tree/src/bplus_leaf.c b/Algorithms/bplus-tree/src/bplus_leaf.c
new file mode 100644
index 0000000..a6b6ae5
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_leaf.c
@@ -0,0 +1,71 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#include "bplus_leaf.h"
+
+BplusLeaf* bplus_leaf_new(BplusTree* tree)
+{
+    g_return_val_if_fail(tree != NULL, NULL);
+
+    BplusLeaf* leaf = g_slice_new(BplusLeaf);
+
+    bplus_node_init(&leaf->node, TRUE);
+    leaf->left  = NULL;
+    leaf->right = NULL;
+
+#ifdef BPLUS_TREE_GATHER_STATS
+    tree->node_count++;
+    tree->leaf_count++;
+    tree->underflow_count++;
+#endif /* ifdef BPLUS_TREE_GATHER_STATS */
+
+    return leaf;
+}
+
+BplusLeaf* bplus_leaf_new_right(BplusTree* tree, BplusLeaf* leaf_left)
+{
+    g_return_val_if_fail(tree != NULL, NULL);
+    g_return_val_if_fail(leaf_left != NULL, NULL);
+
+    BplusLeaf* leaf_right = bplus_leaf_new(tree);
+
+    leaf_right->left  = leaf_left;
+    leaf_right->right = leaf_left->right;
+    leaf_left->right  = leaf_right;
+
+    if (leaf_right->right != NULL)
+        leaf_right->right->left = leaf_right;
+
+    if (tree->last == leaf_left)
+        tree->last = leaf_right;
+
+    return leaf_right;
+}
+
+void bplus_leaf_destroy(BplusTree* tree, BplusLeaf* leaf)
+{
+    g_return_if_fail(tree != NULL);
+    g_return_if_fail(leaf != NULL);
+
+    if (leaf->left != NULL)
+        leaf->left->right = leaf->right;
+
+    if (leaf->right != NULL)
+        leaf->right->left = leaf->left;
+
+    if (tree->first == leaf)
+        tree->first = leaf->right;
+
+    if (tree->last == leaf)
+        tree->last = leaf->left;
+
+#ifdef BPLUS_TREE_GATHER_STATS
+    tree->node_count--;
+    tree->leaf_count--;
+    tree->underflow_count--;
+#endif /* ifdef BPLUS_TREE_GATHER_STATS */
+
+    g_slice_free(BplusLeaf, leaf);
+}
diff --git a/Algorithms/bplus-tree/src/bplus_leaf.h b/Algorithms/bplus-tree/src/bplus_leaf.h
new file mode 100644
index 0000000..482a933
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_leaf.h
@@ -0,0 +1,34 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#ifndef __BPLUS_LEAF_H__
+#define __BPLUS_LEAF_H__
+
+#include "bplus_tree_private.h"
+
+#include "bplus_node.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif // ifdef __cplusplus
+
+struct _BplusLeaf
+{
+    BplusNode node;
+
+    BplusLeaf* left;
+    BplusLeaf* right;
+};
+
+BplusLeaf* bplus_leaf_new(BplusTree* tree);
+BplusLeaf* bplus_leaf_new_right(BplusTree* tree, BplusLeaf* leaf_left);
+void       bplus_leaf_destroy(BplusTree* tree, BplusLeaf* leaf);
+
+#ifdef __cplusplus
+}
+#endif // ifdef __cplusplus
+
+#endif // ifndef __BPLUS_LEAF_H__
diff --git a/Algorithms/bplus-tree/src/bplus_node.c b/Algorithms/bplus-tree/src/bplus_node.c
new file mode 100644
index 0000000..6637367
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_node.c
@@ -0,0 +1,111 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#include "bplus_node.h"
+
+#include "bplus_leaf.h"
+
+#include <string.h>
+
+BplusNode* bplus_node_new(BplusTree* tree)
+{
+    g_return_val_if_fail(tree != NULL, NULL);
+
+    BplusNode* node = g_slice_new(BplusNode);
+
+    bplus_node_init(node, FALSE);
+
+#ifdef BPLUS_TREE_GATHER_STATS
+    tree->node_count++;
+    tree->underflow_count++;
+#endif /* ifdef BPLUS_TREE_GATHER_STATS */
+
+    return node;
+}
+
+BplusNode* bplus_node_new_right(BplusTree* tree, BplusNode* node_left)
+{
+    g_return_val_if_fail(tree != NULL, NULL);
+    g_return_val_if_fail(node_left != NULL, NULL);
+
+    BplusNode* node_right;
+
+    if (node_left->is_leaf)
+        node_right = (BplusNode*) bplus_leaf_new_right(tree, (BplusLeaf*) node_left);
+    else
+        node_right = bplus_node_new(tree);
+
+    node_right->parent = node_left->parent;
+
+    return node_right;
+}
+
+void bplus_node_init(BplusNode* node, gboolean is_leaf)
+{
+    g_return_if_fail(node != NULL);
+
+    node->parent  = NULL;
+    node->is_leaf = is_leaf;
+
+    node->length = 0;
+}
+
+void bplus_node_destroy(BplusTree* tree, BplusNode* node)
+{
+    g_return_if_fail(tree != NULL);
+    g_return_if_fail(node != NULL);
+
+    if (node->is_leaf)
+    {
+        bplus_leaf_destroy(tree, (BplusLeaf*) node);
+    }
+    else
+    {
+#ifdef BPLUS_TREE_GATHER_STATS
+        tree->node_count--;
+        tree->underflow_count--;
+#endif /* ifdef BPLUS_TREE_GATHER_STATS */
+
+        g_slice_free(BplusNode, node);
+    }
+}
+
+void bplus_node_move_and_resize_data(BplusTree const* tree, BplusNode* node, size_t const index_to, size_t const index_from)
+{
+    g_return_if_fail(node != NULL);
+    g_return_if_fail(index_from <= node->length);
+
+#ifdef BPLUS_TREE_GATHER_STATS
+    int was_underfilled = bplus_node_underfilled(node);
+    int was_overfilled  = bplus_node_overfilled(node);
+#endif /* ifdef BPLUS_TREE_GATHER_STATS */
+
+    int64_t const resize_length = index_to - index_from;
+    if (resize_length == 0)
+        return;
+
+    int64_t const move_length = node->length - index_from;
+    if (move_length > 0)
+        memmove(node->items + index_to, node->items + index_from, move_length * sizeof(BplusItem));
+
+    if (resize_length > 0)
+        node->length += resize_length;
+
+    else if (resize_length < 0)
+        node->length -= -resize_length;
+
+#ifdef BPLUS_TREE_GATHER_STATS
+    if (!bplus_node_underfilled(node) && was_underfilled)
+        tree->underflow_count--;
+    else if (bplus_node_underfilled(node) && !was_underfilled)
+        tree->underflow_count++;
+
+    if (bplus_node_overfilled(node) && !was_overfilled)
+        tree->overflow_count++;
+    else if (!bplus_node_overfilled(node) && was_overfilled)
+        tree->overflow_count--;
+#endif /* ifdef BPLUS_TREE_GATHER_STATS */
+
+}
diff --git a/Algorithms/bplus-tree/src/bplus_node.h b/Algorithms/bplus-tree/src/bplus_node.h
new file mode 100644
index 0000000..83a4d9a
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_node.h
@@ -0,0 +1,55 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#ifndef __BPLUS_NODE_H__
+#define __BPLUS_NODE_H__
+
+#include "bplus_tree_private.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif // ifdef __cplusplus
+
+struct _BplusNode
+{
+    size_t    length;
+    BplusItem items[BPLUS_TREE_ORDER];
+
+    uint8_t    is_leaf;
+    BplusNode* parent;
+};
+
+#define bplus_key_gt(bplus_tree_m, k1, k2)  ((k1) > (k2))
+#define bplus_key_gte(bplus_tree_m, k1, k2) ((k1) >= (k2))
+#define bplus_key_lt(bplus_tree_m, k1, k2)  ((k1) < (k2))
+#define bplus_key_lte(bplus_tree_m, k1, k2) ((k1) <= (k2))
+#define bplus_key_eq(bplus_tree_m, k1, k2)  ((k1) == (k2))
+#define bplus_key_neq(bplus_tree_m, k1, k2) ((k1) != (k2))
+
+#define bplus_key_at(node_m, index_m)   (((BplusNode*) node_m)->items[(index_m)].key)
+#define bplus_key_first(node_m)         bplus_key_at(node_m, 0)
+#define bplus_key_last(node_m)          bplus_key_at(node_m, (node_m)->length - 1)
+#define bplus_value_at(node_m, index_m) (((BplusNode*) node_m)->items[(index_m)].value)
+#define bplus_value_first(node_m)       bplus_value_at(node_m, 0)
+#define bplus_value_last(node_m)        bplus_value_at(node_m, (node_m)->length - 1)
+#define bplus_node_at(node_m, index_m)  ((BplusNode*) bplus_value_at(node_m, index_m))
+#define bplus_node_first(node_m)        ((BplusNode*) bplus_value_first(node_m))
+#define bplus_node_last(node_m)         ((BplusNode*) bplus_value_last(node_m))
+
+#define bplus_node_overfilled(node_m)  ((node_m)->length > (BPLUS_TREE_ORDER - 1))
+#define bplus_node_underfilled(node_m) ((node_m)->length <= 1)
+
+BplusNode* bplus_node_new(BplusTree* tree);
+BplusNode* bplus_node_new_right(BplusTree* tree, BplusNode* node_left);
+void       bplus_node_destroy(BplusTree* tree, BplusNode* node);
+void       bplus_node_init(BplusNode* node, gboolean is_leaf);
+void       bplus_node_move_and_resize_data(BplusTree const* tree, BplusNode* node, size_t const index_to, size_t const index_from);
+
+#ifdef __cplusplus
+}
+#endif // ifdef __cplusplus
+
+#endif // ifndef __BPLUS_NODE_H__
diff --git a/Algorithms/bplus-tree/src/bplus_rebalance.c b/Algorithms/bplus-tree/src/bplus_rebalance.c
new file mode 100644
index 0000000..a3cf401
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_rebalance.c
@@ -0,0 +1,279 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#include "bplus_rebalance.h"
+
+#include "bplus_node.h"
+#include "bplus_search.h"
+#include "bplus_insert.h"
+#include "bplus_remove.h"
+
+void bplus_rebalance_propagate(BplusTree const* tree, BplusPath* path)
+{
+    g_return_if_fail(tree != NULL);
+    g_return_if_fail(path != NULL);
+
+    BplusNode* node = path->leaf;
+    for (size_t i = 1; i < path->length; ++i)
+    {
+        size_t const   index = path->index[i];
+        BplusKey const key   = bplus_key_first(node);
+
+        if (bplus_key_gt(tree, bplus_key_at(node->parent, index), key))
+            bplus_key_at(node->parent, index) = key;
+        else
+            break;
+
+        node = node->parent;
+    }
+}
+
+static int64_t bplus_node_get_rebalance_amount(BplusTree const* tree, BplusNode const* node_left, BplusNode const* node_right)
+{
+    g_return_val_if_fail(tree != NULL, 0);
+    g_return_val_if_fail(node_left != NULL, 0);
+    g_return_val_if_fail(node_right != NULL, 0);
+
+    size_t const total = node_left->length + node_right->length;
+
+    /* If the nodes can be merged without overfilling */
+    if (total <= (BPLUS_TREE_ORDER / 3))
+        return -node_right->length;
+
+    /* If the data can be balanced over the two without overfilling */
+    else if (total < (BPLUS_TREE_ORDER * 5 / 3))
+        return node_left->length - (total + 1) / 2;
+
+    return 0;
+}
+
+static gboolean bplus_node_find_merge_candidate(BplusTree const* tree, size_t const index, BplusNode* node,
+                                                BplusNode** node_left, BplusNode** node_right)
+{
+    g_return_val_if_fail(tree != NULL, FALSE);
+    g_return_val_if_fail(node != NULL, FALSE);
+
+    *node_left  = node;
+    *node_right = node;
+    if ((node->parent == NULL) || (node->parent->length <= 1))
+        return FALSE;
+
+    if (index == 0)
+    {
+        *node_right = bplus_node_at(node->parent, index + 1);
+        if (bplus_node_get_rebalance_amount(tree, node, *node_right) == 0)
+            *node_right = node;
+
+    }
+    else if (index == node->parent->length - 1)
+    {
+        *node_left = bplus_node_at(node->parent, index - 1);
+        if (bplus_node_get_rebalance_amount(tree, *node_left, node) == 0)
+            *node_left = node;
+
+    }
+    else
+    {
+        *node_left  = bplus_node_at(node->parent, index - 1);
+        *node_right = bplus_node_at(node->parent, index + 1);
+
+        int64_t const merge_amount_right = bplus_node_get_rebalance_amount(tree, node, *node_right);
+        int64_t const merge_amount_left  = bplus_node_get_rebalance_amount(tree, *node_left, node);
+
+        if (merge_amount_left < 0)
+        {
+            /* Merge with left copies data to the left.
+             * Prefer a merge with right only if it copies less data from the right.
+             */
+            if (merge_amount_right >= 0)
+                *node_right = node;
+            else if (merge_amount_right < merge_amount_left)
+                *node_right = node;
+            else
+                *node_left = node;
+        }
+        else if (merge_amount_left > 0)
+        {
+            /* Merge with left copies data from the left.
+             * Prefer a merge with right if it copies less data to the right or data from right.
+             */
+            if (merge_amount_right == 0)
+                *node_right = node;
+            else if (merge_amount_right > merge_amount_left)
+                *node_right = node;
+            else
+                *node_left = node;
+        }
+        else if (merge_amount_right != 0)
+        {
+            /* Merge with left is impossible.
+             * Prefer a merge with right.
+             */
+            *node_left = node;
+        }
+        else
+        {
+            *node_left  = node;
+            *node_right = node;
+        }
+    }
+
+    return *node_left != *node_right;
+} /* bplus_node_find_merge_candidate */
+
+static size_t bplus_rebalance_data(BplusTree const* tree, BplusNode* node_left, BplusNode* node_right)
+{
+    g_return_val_if_fail(tree != NULL, 0);
+    g_return_val_if_fail(node_left != NULL, 0);
+    g_return_val_if_fail(node_right != NULL, 0);
+
+    int64_t const amount = bplus_node_get_rebalance_amount(tree, node_left, node_right);
+    g_return_val_if_fail(amount <= 0 || amount < node_left->length, 0);
+    g_return_val_if_fail(amount >= 0 || -amount <= node_right->length, 0);
+
+    if (amount > 0)
+    {
+        size_t const     index = node_left->length - amount;
+        BplusItem const* items = node_left->items + index;
+
+        bplus_node_insert_at(tree, node_right, 0, amount, items);
+        bplus_node_remove_at(tree, node_left, index, amount);
+
+    }
+    else if (amount < 0)
+    {
+        size_t const     index = node_left->length;
+        BplusItem const* items = node_right->items;
+
+        bplus_node_insert_at(tree, node_left, index, -amount, items);
+        bplus_node_remove_at(tree, node_right, 0, -amount);
+    }
+
+    return 0;
+} /* bplus_rebalance_data */
+
+static void bplus_rebalance_split_node(BplusTree* tree, BplusNode* node_left, size_t const index)
+{
+    g_return_if_fail(tree != NULL);
+    g_return_if_fail(node_left != NULL);
+
+    BplusNode* const node_right = bplus_node_new_right(tree, node_left);
+    bplus_rebalance_data(tree, node_left, node_right);
+
+    BplusItem const item = { .key = bplus_key_first(node_right), .value = node_right };
+    bplus_node_insert_at(tree, node_left->parent, index + 1, 1, &item);
+}
+
+static void bplus_rebalance_new_root(BplusTree* tree)
+{
+    g_return_if_fail(tree != NULL);
+
+    BplusNode* const node = tree->root;
+    BplusNode* const root = bplus_node_new(tree);
+    bplus_key_first(root)   = bplus_key_first(node);
+    bplus_value_first(root) = node;
+    root->length            = 1;
+    node->parent            = root;
+    tree->root              = root;
+    tree->height++;
+}
+
+static int bplus_rebalance_try_merge(BplusTree* tree, BplusNode* node, size_t const index)
+{
+    g_return_val_if_fail(tree != NULL, 0);
+    g_return_val_if_fail(node != NULL, 0);
+
+    BplusNode* node_left;
+    BplusNode* node_right;
+    if (!bplus_node_find_merge_candidate(tree, index, node, &node_left, &node_right))
+        return 0;
+
+    size_t const index_right = (node == node_left) ? index + 1 : index;
+    bplus_rebalance_data(tree, node_left, node_right);
+
+    if (node_right->length == 0)
+    {
+        bplus_node_remove_at(tree, node->parent, index_right, 1);
+        bplus_node_destroy(tree, node_right);
+    }
+    else
+    {
+        bplus_key_at(node->parent, index_right) = bplus_key_first(node_right);
+    }
+
+    return 1;
+}
+
+void bplus_rebalance_overfilled(BplusTree* tree, BplusPath const* path)
+{
+    g_return_if_fail(tree != NULL);
+    g_return_if_fail(path != NULL);
+
+    BplusNode* node = (BplusNode*) path->leaf;
+    for (size_t i = 1; i < path->length; ++i)
+    {
+        if (!bplus_node_overfilled(node))
+            break;
+
+        size_t const index = path->index[i];
+        if (!bplus_rebalance_try_merge(tree, node, index))
+            bplus_rebalance_split_node(tree, node, index);
+
+        node = node->parent;
+    }
+
+    if (bplus_node_overfilled(node))
+    {
+        bplus_rebalance_new_root(tree);
+        bplus_rebalance_split_node(tree, node, 0);
+    }
+}
+
+static void bplus_rebalance_shrink_tree(BplusTree* tree)
+{
+    g_return_if_fail(tree != NULL);
+    g_return_if_fail(tree->root != NULL);
+
+    size_t i = 0;
+    for (; i < tree->height; ++i)
+    {
+        if (tree->root->length != 1)
+            break;
+        if (tree->root->is_leaf)
+            break;
+
+        BplusNode* node = tree->root;
+        tree->root         = bplus_node_first(tree->root);
+        tree->root->parent = NULL;
+        node->length       = 0;
+        bplus_node_destroy(tree, node);
+    }
+
+    tree->height -= i;
+}
+
+void bplus_rebalance_underfilled(BplusTree* tree, BplusPath const* path)
+{
+    g_return_if_fail(tree != NULL);
+    g_return_if_fail(path != NULL);
+
+    BplusNode* node = (BplusNode*) path->leaf;
+    for (size_t i = 1; i < path->length; ++i)
+    {
+        if (!bplus_node_underfilled(node))
+            break;
+
+        size_t const index = path->index[i];
+        if (!bplus_rebalance_try_merge(tree, node, index) && (node->length == 0))
+        {
+            bplus_node_remove_at(tree, node->parent, index, 1);
+            bplus_node_destroy(tree, node);
+        }
+
+        node = node->parent;
+    }
+
+    bplus_rebalance_shrink_tree(tree);
+}
diff --git a/Algorithms/bplus-tree/src/bplus_rebalance.h b/Algorithms/bplus-tree/src/bplus_rebalance.h
new file mode 100644
index 0000000..3872f4d
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_rebalance.h
@@ -0,0 +1,24 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#ifndef __BPLUS_REBALANCE_H__
+#define __BPLUS_REBALANCE_H__
+
+#include "bplus_tree_private.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif // ifdef __cplusplus
+
+void bplus_rebalance_propagate(BplusTree const* tree, BplusPath* path);
+void bplus_rebalance_overfilled(BplusTree* tree, BplusPath const* path);
+void bplus_rebalance_underfilled(BplusTree* tree, BplusPath const* path);
+
+#ifdef __cplusplus
+}
+#endif // ifdef __cplusplus
+
+#endif // ifndef __BPLUS_REBALANCE_H__
diff --git a/Algorithms/bplus-tree/src/bplus_remove.c b/Algorithms/bplus-tree/src/bplus_remove.c
new file mode 100644
index 0000000..9265ce1
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_remove.c
@@ -0,0 +1,60 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#include "bplus_remove.h"
+
+#include "bplus_node.h"
+#include "bplus_search.h"
+#include "bplus_rebalance.h"
+
+void bplus_node_remove_at(BplusTree const* tree, BplusNode* node, size_t const index, size_t const length)
+{
+    g_return_if_fail(node != NULL);
+    g_return_if_fail(index < node->length);
+    g_return_if_fail(index + length <= node->length);
+
+    bplus_node_move_and_resize_data(tree, node, index, index + length);
+}
+
+BplusValue bplus_tree_remove_first(BplusTree* tree)
+{
+    BplusPath    path  = { .leaf = (BplusNode*) tree->first };
+    BplusNode*   node  = (BplusNode*) path.leaf;
+    size_t const index = path.index[0];
+
+    BplusValue value = bplus_value_at(node, 0);
+    bplus_node_remove_at(tree, node, index, 1);
+    if (index == 0)
+        bplus_rebalance_propagate(tree, &path);
+
+    if (bplus_node_underfilled(node))
+        bplus_rebalance_underfilled(tree, &path);
+
+    return value;
+}
+
+BplusValue bplus_tree_remove(BplusTree* tree, BplusKey const key)
+{
+    BplusPath path;
+    bplus_tree_get_path_to_key(tree, key, &path);
+
+    size_t const index = path.index[0];
+    BplusNode*   node  = (BplusNode*) path.leaf;
+
+    if (bplus_key_eq(tree, bplus_key_at(node, index), key))
+    {
+        BplusValue value = bplus_value_at(node, index);
+        bplus_node_remove_at(tree, node, index, 1);
+        if (index == 0)
+            bplus_rebalance_propagate(tree, &path);
+
+        if (bplus_node_underfilled(node))
+            bplus_rebalance_underfilled(tree, &path);
+
+        return value;
+    }
+
+    return NULL;
+}
diff --git a/Algorithms/bplus-tree/src/bplus_remove.h b/Algorithms/bplus-tree/src/bplus_remove.h
new file mode 100644
index 0000000..81b94d3
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_remove.h
@@ -0,0 +1,22 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#ifndef __BPLUS_REMOVE_H__
+#define __BPLUS_REMOVE_H__
+
+#include "bplus_tree_private.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif // ifdef __cplusplus
+
+void bplus_node_remove_at(BplusTree const* tree, BplusNode* node, size_t const index, size_t const length);
+
+#ifdef __cplusplus
+}
+#endif // ifdef __cplusplus
+
+#endif // ifndef __BPLUS_REMOVE_H__
diff --git a/Algorithms/bplus-tree/src/bplus_search.c b/Algorithms/bplus-tree/src/bplus_search.c
new file mode 100644
index 0000000..a1e7c3b
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_search.c
@@ -0,0 +1,127 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#include "bplus_search.h"
+
+#include "bplus_node.h"
+#include "bplus_leaf.h"
+
+#define bplus_node_get_key_index_op(operator_m, tree_m, node_m, key_m)      \
+    do                                                                      \
+    {                                                                       \
+        size_t index = 1;                                                   \
+        while (index < (node_m)->length)                                    \
+        {                                                                   \
+            if (operator_m((tree_m), bplus_key_at(node_m, index), (key_m))) \
+                break;                                                      \
+            ++index;                                                        \
+        }                                                                   \
+                                                                            \
+        return --index;                                                     \
+    }                                                                       \
+    while (0)
+
+static size_t bplus_node_get_key_index(BplusTree const* tree, BplusNode const* node, BplusKey const key)
+{
+    g_return_val_if_fail(tree != NULL, 0);
+    g_return_val_if_fail(node != NULL, 0);
+
+    bplus_node_get_key_index_op(bplus_key_gt, tree, node, key);
+}
+
+static size_t bplus_node_get_key_index_before(BplusTree const* tree, BplusNode const* node, BplusKey const key)
+{
+    g_return_val_if_fail(tree != NULL, 0);
+    g_return_val_if_fail(node != NULL, 0);
+
+    bplus_node_get_key_index_op(bplus_key_gte, tree, node, key);
+}
+
+#define bplus_tree_get_path_to_key_op(operator_m, tree_m, key_m, path_m)           \
+    do                                                                             \
+    {                                                                              \
+        if (__builtin_expect(((tree_m)->root->length == 0), 0))                    \
+        {                                                                          \
+            (path_m)->length   = 1;                                                \
+            (path_m)->index[0] = 0;                                                \
+            (path_m)->leaf     = tree->root;                                       \
+            return;                                                                \
+        }                                                                          \
+                                                                                   \
+        BplusNode const* node   = (tree_m)->root;                                  \
+        size_t const     length = (tree_m)->height;                                \
+        for (size_t i = length; i > 0; --i)                                        \
+        {                                                                          \
+            for (int i = 0; i < BPLUS_TREE_ORDER * sizeof(*node->items) / 64; ++i) \
+            {                                                                      \
+                __builtin_prefetch(node->items + i * 64 / sizeof(*node->items));   \
+            }                                                                      \
+                                                                                   \
+            size_t const index = operator_m((tree_m), node, (key_m));              \
+            (path_m)->index[i - 1] = index;                                        \
+                                                                                   \
+            if (i == 1)                                                            \
+                break;                                                             \
+                                                                                   \
+            node = bplus_node_at(node, index);                                     \
+        }                                                                          \
+                                                                                   \
+        (path_m)->length = length;                                                 \
+        (path_m)->leaf   = (BplusNode*) node;                                      \
+    }                                                                              \
+    while (0)
+
+void bplus_tree_get_path_to_key(BplusTree const* tree, BplusKey const key, BplusPath* path)
+{
+    g_return_if_fail(tree != NULL);
+    g_assert(tree->height < sizeof((path)->index) / sizeof(*(path)->index));
+
+    bplus_tree_get_path_to_key_op(bplus_node_get_key_index, tree, key, path);
+}
+
+static void bplus_tree_get_path_to_key_before(BplusTree const* tree, BplusKey const key, BplusPath* path)
+{
+    g_return_if_fail(tree != NULL);
+    g_assert(tree->height < sizeof((path)->index) / sizeof(*(path)->index));
+
+    bplus_tree_get_path_to_key_op(bplus_node_get_key_index_before, tree, key, path);
+}
+
+void bplus_tree_get_paths_to_key_range(BplusTree const* tree, BplusKey key_from, BplusKey key_to, BplusPath* path_from, BplusPath* path_to)
+{
+    g_return_if_fail(tree != NULL);
+    g_assert(tree->height < sizeof((path_from)->index) / sizeof(*(path_from)->index));
+    g_assert(tree->height < sizeof((path_to)->index) / sizeof(*(path_to)->index));
+
+    if (bplus_key_gt(tree, key_from, key_to))
+    {
+        BplusKey tmp = key_to;
+        key_to   = key_from;
+        key_from = tmp;
+    }
+
+    bplus_tree_get_path_to_key(tree, key_to, path_to);
+    if (!bplus_key_gt(tree, bplus_key_at(path_to->leaf, path_to->index[0]), key_to))
+        path_to->index[0]++;
+
+    bplus_tree_get_path_to_key_before(tree, key_from, path_from);
+    if (!bplus_key_gte(tree, bplus_key_at(path_from->leaf, path_from->index[0]), key_from))
+        path_from->index[0]++;
+
+    BplusLeaf const* const leaf = (BplusLeaf*) path_from->leaf;
+    if (path_from->index[0] == leaf->node.length)
+    {
+        if (leaf->right == NULL)
+        {
+            path_from->leaf     = path_to->leaf;
+            path_from->index[0] = path_to->index[0];
+        }
+        else
+        {
+            path_from->leaf     = (BplusNode*) leaf->right;
+            path_from->index[0] = 0;
+        }
+    }
+}
diff --git a/Algorithms/bplus-tree/src/bplus_search.h b/Algorithms/bplus-tree/src/bplus_search.h
new file mode 100644
index 0000000..3e76a39
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_search.h
@@ -0,0 +1,23 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#ifndef __BPLUS_SEARCH_H__
+#define __BPLUS_SEARCH_H__
+
+#include "bplus_tree_private.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif // ifdef __cplusplus
+
+void bplus_tree_get_path_to_key(BplusTree const* tree, BplusKey const key, BplusPath* path);
+void bplus_tree_get_paths_to_key_range(BplusTree const* tree, BplusKey key_from, BplusKey key_to, BplusPath* path_from, BplusPath* path_to);
+
+#ifdef __cplusplus
+}
+#endif // ifdef __cplusplus
+
+#endif // ifndef __BPLUS_SEARCH_H__
diff --git a/Algorithms/bplus-tree/src/bplus_tree.c b/Algorithms/bplus-tree/src/bplus_tree.c
new file mode 100644
index 0000000..fc8bb8e
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_tree.c
@@ -0,0 +1,202 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#include "bplus_tree_private.h"
+
+#include "bplus_leaf.h"
+#include "bplus_search.h"
+#include "bplus_iterator.h"
+#include "bplus_foreach.h"
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdarg.h>
+#include <stdio.h>
+
+int bplus_tree_print(BplusTree const* const tree, char const* format, ...) __attribute__((format(printf, 2, 3)));
+
+BplusTree* bplus_tree_new()
+{
+    return bplus_tree_new_full(1);
+}
+
+BplusTree* bplus_tree_new_full(gboolean allow_duplicate_keys)
+{
+    BplusTree* tree = malloc(sizeof(BplusTree));
+
+    tree->first = bplus_leaf_new(tree);
+    tree->last  = tree->first;
+    tree->root  = (BplusNode*) tree->first;
+
+    tree->height               = 1;
+    tree->allow_duplicate_keys = allow_duplicate_keys;
+
+    return tree;
+}
+
+void bplus_tree_print_stats(BplusTree* tree);
+
+static void bplus_foreach_node_destroy(BplusTree* tree, BplusNode* node, void* argument)
+{
+    bplus_node_destroy(tree, node);
+}
+
+void bplus_tree_destroy(BplusTree* tree)
+{
+    g_return_if_fail(tree != NULL);
+
+#ifdef BPLUS_TREE_GATHER_STATS
+    bplus_tree_print_stats(tree);
+#endif /* ifdef BPLUS_TREE_GATHER_STATS */
+
+    bplus_foreach_node_in_tree(tree, &bplus_foreach_node_destroy, NULL);
+    free(tree);
+}
+
+void bplus_tree_destroy_each(BplusTree* tree, BplusForeachItemFunc* foreach, void* argument)
+{
+    bplus_foreach_item_in_tree(tree, foreach, argument);
+    bplus_tree_destroy(tree);
+}
+
+#ifdef BPLUS_TREE_GATHER_STATS
+
+void bplus_tree_print_stats(BplusTree* tree)
+{
+    printf("tree height: %zu\n", tree->height);
+    printf("node count: %zu\n", tree->node_count);
+    printf("leaf count: %zu\n", tree->leaf_count);
+    printf("underflow count: %zu\n", tree->underflow_count);
+    printf("overflow count: %zu\n", tree->overflow_count);
+}
+
+#endif /* ifdef BPLUS_TREE_GATHER_STATS */
+
+BplusValue bplus_tree_get(BplusTree* tree, BplusKey key)
+{
+    BplusPath path;
+    bplus_tree_get_path_to_key(tree, key, &path);
+
+    size_t const     index = path.index[0];
+    BplusNode const* node  = path.leaf;
+    BplusValue       value = NULL;
+
+    if ((index < node->length) && bplus_key_eq(tree, bplus_key_at(node, index), key))
+        value = bplus_value_at(node, index);
+
+    return value;
+}
+
+BplusValue bplus_tree_get_first(BplusTree const* tree)
+{
+    if (tree->first->node.length == 0)
+        return NULL;
+
+    return tree->first->node.items[0].value;
+}
+
+BplusValue bplus_tree_get_nth(BplusTree const* tree, size_t position)
+{
+    BplusLeaf* leaf = tree->first;
+    if (leaf->node.length == 0)
+        return NULL;
+
+    while (leaf != NULL && position >= leaf->node.length)
+    {
+        position -= leaf->node.length;
+        leaf      = leaf->right;
+    }
+
+    if (leaf != NULL)
+        return leaf->node.items[position].value;
+
+    return NULL;
+}
+
+void bplus_value_print(BplusNode* node, size_t const index, BplusKey key, BplusValue value, int depth)
+{
+    static char const* indent = "                                                                   ";
+
+    fprintf(stderr, "%*.s n%p_%zu[label=\"%lu\",fontcolor=\"#000099\"];", 0, indent, node, index, key);
+    fprintf(stderr, "%*.s n%p->n%p_%zu;", 0, indent, node, node, index);
+}
+
+void bplus_node_print(BplusNode* parent, BplusKey key, BplusNode* node, int depth)
+{
+    static char const* indent = "                                                                   ";
+
+    fprintf(stderr, "%*.s n%p[label=\"%lu\"];", 0, indent, node, key);
+    fprintf(stderr, "%*.s n%p->n%p;", 0, indent, parent, node);
+
+    if (node->is_leaf)
+    {
+        if (((BplusLeaf*) node)->right != NULL)
+            fprintf(stderr, "n%p->n%p[constraint=false];", node, ((BplusLeaf*) node)->right);
+        if (((BplusLeaf*) node)->left != NULL)
+            fprintf(stderr, "n%p->n%p[constraint=false];", node, ((BplusLeaf*) node)->left);
+    }
+
+    for (size_t i = 0; i < node->length; ++i)
+    {
+        if (node->is_leaf)
+            bplus_value_print(node, i, bplus_key_at(node, i), bplus_value_at(node, i), 2);
+        else
+            bplus_node_print(node, bplus_key_at(node, i), bplus_node_at(node, i), depth + 2);
+
+    }
+}
+
+int bplus_tree_print(BplusTree const* const tree, char const* format, ...)
+{
+    static int count = 0;
+
+    fprintf(stderr, "echo 'digraph {");
+    fprintf(stderr, "graph[ordering=\"out\"];\n");
+    fprintf(stderr, "node[width=0.2,height=0.2,fixedsize=true,fontsize=6,fontcolor=\"#990000\",shape=plaintext];");
+    fprintf(stderr, "edge[arrowsize=0.1,fontsize=6];");
+
+    BplusNode* node = tree->root;
+    fprintf(stderr, "n%p[label=\"0\"];", node);
+    if (node->is_leaf)
+    {
+        if (((BplusLeaf*) node)->right != NULL)
+            fprintf(stderr, "n%p->n%p[constraint=false];", node, ((BplusLeaf*) node)->right);
+        if (((BplusLeaf*) node)->left != NULL)
+            fprintf(stderr, "n%p->n%p[constraint=false];", node, ((BplusLeaf*) node)->left);
+    }
+
+    for (size_t i = 0; i < node->length; ++i)
+    {
+        if (node->is_leaf)
+            bplus_value_print(node, i, bplus_key_at(node, i), bplus_value_at(node, i), 2);
+        else
+            bplus_node_print(node, bplus_key_at(node, i), bplus_node_at(node, i), 2);
+
+    }
+
+    va_list vargs;
+    va_start(vargs, format);
+    vfprintf(stderr, format, vargs);
+    va_end(vargs);
+
+    fprintf(stderr, "}'| dot -T png -o tree-%d.png\n", count);
+    count++;
+    return 0;
+}
+
+int bplus_iterator_print(BplusTree const* tree, BplusIterator const* iterator)
+{
+    bplus_tree_print(tree,
+                     "label=\"iterator\"; i[fontcolor=\"#009900\",label=\"i\"];"
+                     "n%p_%zu->i[label=\"from\"];"
+                     "n%p_%zu->i[color=\"#009900\"];"
+                     "n%p_%zu->i[label=\"to\"];",
+                     iterator->leaf_from, iterator->item_from - iterator->leaf_from->node.items,
+                     iterator->leaf, iterator->item - iterator->leaf->node.items,
+                     iterator->leaf_to, iterator->item_to - iterator->leaf_to->node.items - 1);
+
+    return 0;
+}
diff --git a/Algorithms/bplus-tree/src/bplus_tree_private.h b/Algorithms/bplus-tree/src/bplus_tree_private.h
new file mode 100644
index 0000000..97b873f
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_tree_private.h
@@ -0,0 +1,53 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#ifndef __BPLUS_TREE_PRIVATE_H__
+#define __BPLUS_TREE_PRIVATE_H__
+
+#include "bplus_tree.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif // ifdef __cplusplus
+
+#ifndef BPLUS_TREE_ORDER
+# define BPLUS_TREE_ORDER 32
+#endif /* ifndef BPLUS_TREE_ORDER */
+
+typedef struct _BplusNode BplusNode;
+typedef struct _BplusLeaf BplusLeaf;
+typedef struct _BplusPath BplusPath;
+
+struct _BplusPath
+{
+    size_t     length;
+    size_t     index[16];
+    BplusNode* leaf;
+};
+
+struct _BplusTree
+{
+    BplusNode* root;
+
+    BplusLeaf* first;
+    BplusLeaf* last;
+
+    size_t   height;
+    gboolean allow_duplicate_keys;
+
+#ifdef BPLUS_TREE_GATHER_STATS
+    size_t node_count;
+    size_t leaf_count;
+    size_t underflow_count;
+    size_t overflow_count;
+#endif /* ifdef BPLUS_TREE_GATHER_STATS */
+};
+
+#ifdef __cplusplus
+}
+#endif // ifdef __cplusplus
+
+#endif // ifndef __BPLUS_TREE_PRIVATE_H__