summaryrefslogtreecommitdiff
path: root/Algorithms/bplus-tree/src/bplus_rebalance.c
diff options
context:
space:
mode:
Diffstat (limited to 'Algorithms/bplus-tree/src/bplus_rebalance.c')
-rw-r--r--Algorithms/bplus-tree/src/bplus_rebalance.c279
1 files changed, 279 insertions, 0 deletions
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);
+}
generated by cgit v1.2.3 (git 2.25.1) at 2026-06-13 10:35:07 +0000