Algorithm


Deletion in a B+ tree involves removing a key and its associated value from the tree while maintaining the properties of a B+ tree. The process can be a bit involved, and I'll outline the general steps for deleting a key from a B+ tree:

  1. Search for the Key: Start by searching for the key you want to delete in the B+ tree. If the key is not present in the tree, the deletion operation is complete.

  2. Locate the Key in a Leaf Node: Once you find the key, locate the leaf node containing the key. If the key appears multiple times, choose one occurrence.

  3. Remove the Key from the Leaf Node: Delete the key and its associated value from the leaf node. Adjust the pointers accordingly.

  4. Check Underflow: After deleting the key from the leaf node, check if the node becomes underflowed (has fewer keys than the minimum required). If underflow occurs, take corrective actions to rebalance the tree.

  5. Underflow Handling: If underflow occurs in a leaf node, borrow a key from its adjacent sibling or merge with the sibling. If underflow occurs in an internal node, borrow a key from an adjacent sibling or rotate keys among siblings. If borrowing is not possible, merge the nodes.

  6. Update Parent Nodes: After handling underflow, update the parent nodes to reflect the changes. If merging occurred, delete the key from the parent node. If borrowing occurred, update the key in the parent node.

  7. Check Root Node: If the root node becomes empty due to merging, update the root to be the merged child.

  8. Rebalance the Tree: If any underflow propagates up to the root, rebalance the tree accordingly.

  9. Adjust Tree Height: If the deletion causes the height of the tree to decrease, update the height of the tree.

It's important to note that the specifics of the deletion process can vary based on the implementation details of the B+ tree. Also, some variations in the process might be needed based on the specific characteristics of the tree and the application.

 

Code Examples

#1 Deletion from a B+ Tree implement in Python

Code - Python Programming

class BPlusTree:
    def __init__(self, order):
        self.root = BPlusNode(order)
        
    def insert(self, key, value):
        # Implement insertion logic here
    
    def delete(self, key):
        # Implement deletion logic here
    
class BPlusNode:
    def __init__(self, order, is_leaf=True):
        self.order = order
        self.keys = []
        self.values = []  # For leaf nodes
        self.children = []  # For internal nodes
        self.is_leaf = is_leaf
    
    def insert_key_value(self, key, value=None):
        # Implement logic to insert key and value into the node
    
    def delete_key_value(self, key):
        # Implement logic to delete key and corresponding value from the node

    def borrow_key_from_sibling(self, sibling, parent, index):
        # Implement logic to borrow a key from a sibling node
    
    def merge_with_sibling(self, sibling, parent, index):
        # Implement logic to merge with a sibling node
    
    def redistribute_keys_with_sibling(self, sibling, parent, index):
        # Implement logic to redistribute keys with a sibling node
Copy The Code & Try With Live Editor

#2 Deletion from a B+ Tree implement in Java

Code - Java Programming

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

class BPlusTree {
    private Node root;
    private int order; // Order of the B+ tree

    // Constructor
    public BPlusTree(int order) {
        this.root = null;
        this.order = order;
    }

    // Method to delete a key from the B+ tree
    public void delete(int key) {
        if (root == null) {
            System.out.println("Tree is empty");
            return;
        }

        root = delete(root, key);

        // If root has only one child, make the child the new root
        if (root instanceof InternalNode && ((InternalNode) root).getChildren().size() == 1) {
            root = ((InternalNode) root).getChildren().get(0);
        }
    }

    // Recursive method to delete a key from the B+ tree
    private Node delete(Node node, int key) {
        if (node instanceof LeafNode) {
            // Delete the key from the leaf node
            ((LeafNode) node).delete(key);
        } else {
            InternalNode internalNode = (InternalNode) node;
            int index = 0;

            // Find the index of the child to go to
            while (index  <  internalNode.getKeys().size() && key > internalNode.getKeys().get(index)) {
                index++;
            }

            // Recursively delete the key from the child
            Node child = internalNode.getChildren().get(index);
            Node newChild = delete(child, key);
            internalNode.getChildren().set(index, newChild);

            // If the child is an internal node and has less than half full, fix it
            if (newChild instanceof InternalNode && ((InternalNode) newChild).getKeys().size()  <  order / 2) {
                fixInternalNode(internalNode, index);
            }
        }

        // If the root is an internal node and has only one child, make that child the new root
        if (node instanceof InternalNode && ((InternalNode) node).getChildren().size() == 1) {
            node = ((InternalNode) node).getChildren().get(0);
        }

        return node;
    }

    // Fix an internal node that has less than half full after deletion
    private void fixInternalNode(InternalNode parent, int index) {
        InternalNode child = (InternalNode) parent.getChildren().get(index);

        if (index > 0) {
            // Try to borrow a key from the left sibling
            InternalNode leftSibling = (InternalNode) parent.getChildren().get(index - 1);
            if (leftSibling.getKeys().size() > order / 2) {
                int borrowedKey = leftSibling.getKeys().remove(leftSibling.getKeys().size() - 1);
                List < Node> borrowedChildren = leftSibling.getChildren().remove(leftSibling.getChildren().size() - 1);

                child.getKeys().add(0, borrowedKey);
                child.getChildren().add(0, borrowedChildren.get(borrowedChildren.size() - 1));

                parent.getKeys().set(index - 1, borrowedKey);
                return;
            }
        }

        if (index  <  parent.getChildren().size() - 1) {
            // Try to borrow a key from the right sibling
            InternalNode rightSibling = (InternalNode) parent.getChildren().get(index + 1);
            if (rightSibling.getKeys().size() > order / 2) {
                int borrowedKey = rightSibling.getKeys().remove(0);
                List < Node> borrowedChildren = rightSibling.getChildren().remove(0);

                child.getKeys().add(borrowedKey);
                child.getChildren().add(borrowedChildren.get(0));

                parent.getKeys().set(index, rightSibling.getKeys().get(0));
                return;
            }
        }

        // Merge with a sibling since borrowing is not possible
        if (index > 0) {
            // Merge with the left sibling
            InternalNode leftSibling = (InternalNode) parent.getChildren().get(index - 1);
            leftSibling.getKeys().addAll(parent.getKeys().remove(index - 1));
            leftSibling.getChildren().addAll(child.getChildren());
            parent.getChildren().remove(index);
        } else {
            // Merge with the right sibling
            InternalNode rightSibling = (InternalNode) parent.getChildren().get(index + 1);
            child.getKeys().addAll(parent.getKeys().remove(index));
            child.getChildren().addAll(rightSibling.getChildren());
            parent.getChildren().remove(index + 1);
        }
    }

    // Other methods (insert, search, display) can be added as needed

    // Example usage
    public static void main(String[] args) {
        BPlusTree tree = new BPlusTree(3);

        // Insert keys into the tree
        int[] keysToInsert = {10, 20, 5, 6, 12, 30, 7, 17};
        for (int key : keysToInsert) {
            tree.insert(key);
        }

        // Display the tree
        tree.display();

        // Delete a key from the tree
        int keyToDelete = 12;
        tree.delete(keyToDelete);

        // Display the tree after deletion
        tree.display();
    }
}

// Node class (abstract class)
abstract class Node {
    // Common methods for LeafNode and InternalNode can be added here
}

// LeafNode class
class LeafNode extends Node {
    private List < Integer> keys;

    public LeafNode() {
        this.keys = new ArrayList<>();
    }

    public List < Integer> getKeys() {
        return keys;
    }

    public void insert(int key) {
        keys.add(key);
        keys.sort(null); // Sort the keys
    }

    public void delete(int key) {
        keys.remove(Integer.valueOf(key));
    }
}

// InternalNode class
class InternalNode extends Node {
    private List < Integer> keys;
    private List children;

    public InternalNode() {
        this.keys = new ArrayList < >();
        this.children = new ArrayList<>();
    }

    public List < Integer> getKeys() {
        return keys;
    }

    public List getChildren() {
        return children;
    }

    public void insert(int key, Node child) {
        int index = 0;
        while (index  <  keys.size() && key > keys.get(index)) {
            index++;
        }

        keys.add(index, key);
        children.add(index + 1, child);
    }
}
Copy The Code & Try With Live Editor

#3 Deletion from a B+ Tree implement in C

Code - C Programming

#include <stdio.h>
#include <stdlib.h>

// Define the order of the B+ tree
#define ORDER 3

// Define a structure for B+ tree nodes
typedef struct Node {
    int isLeaf; // 1 if the node is a leaf, 0 otherwise
    int numKeys; // Number of keys in the node
    int keys[ORDER - 1]; // Keys in the node
    struct Node* children[ORDER]; // Pointers to children nodes
} Node;

// Function to create a new B+ tree node
Node* createNode(int isLeaf) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->isLeaf = isLeaf;
    newNode->numKeys = 0;
    for (int i = 0; i  <  ORDER - 1; i++) {
        newNode->keys[i] = 0;
    }
    for (int i = 0; i  <  ORDER; i++) {
        newNode->children[i] = NULL;
    }
    return newNode;
}

// Function to search for a key in the B+ tree
Node* search(Node* root, int key) {
    if (root == NULL) {
        return NULL;
    }

    int i = 0;
    while (i  <  root->numKeys && key > root->keys[i]) {
        i++;
    }

    if (i < root->numKeys && key == root->keys[i]) {
        return root; // Key found
    } else if (root->isLeaf) {
        return NULL; // Key not found in a leaf node
    } else {
        return search(root->children[i], key); // Recursively search in the appropriate child
    }
}

// Function to delete a key from the B+ tree
Node* deleteKey(Node* root, int key) {
    // Implement the deletion algorithm here
    // ...
    return root;
}

// Function to print the B+ tree (inorder traversal)
void inorderTraversal(Node* root) {
    if (root != NULL) {
        for (int i = 0; i  <  root->numKeys; i++) {
            inorderTraversal(root->children[i]);
            printf("%d ", root->keys[i]);
        }
        inorderTraversal(root->children[root->numKeys]);
    }
}

// Function to free the memory allocated for the B+ tree nodes
void freeTree(Node* root) {
    if (root != NULL) {
        for (int i = 0; i  <  ORDER; i++) {
            freeTree(root->children[i]);
        }
        free(root);
    }
}

int main() {
    Node* root = createNode(1); // Create a root node (leaf node)
    
    // Insert keys into the B+ tree
    // ...

    printf("Original B+ tree: ");
    inorderTraversal(root);
    printf("\n");

    // Delete a key from the B+ tree
    int keyToDelete = 5;
    root = deleteKey(root, keyToDelete);

    printf("B+ tree after deleting key %d: ", keyToDelete);
    inorderTraversal(root);
    printf("\n");

    // Free the memory allocated for the B+ tree nodes
    freeTree(root);

    return 0;
}
Copy The Code & Try With Live Editor

#4 Deletion from a B+ Tree implement in C++

Code - C++ Programming

Assuming you have a B+ tree node structure like this:

struct Node {
    // For internal nodes
    vector<KeyType> keys;
    vector < Node*> children;

    // For leaf nodes
    Node* nextLeaf;
    vector < KeyType> values;
};
 < /code>
Here are the general steps for deleting a key from a B+ tree: Locate the Key: Traverse the tree to find the node containing the key to be deleted. Delete the Key: If the key is in a leaf node, remove it from the node. If the key is in an internal node, replace it with the predecessor or successor key from the leaf nodes. Update Parent Nodes: If the deletion causes the number of keys in a node to fall below the minimum, perform node splitting or merging to ensure that all nodes meet the B+ tree properties. Update the keys in the parent nodes accordingly. Update Root Node: If the root node becomes empty after deleting a key, update the root to be its only child. Handle Underflow: If the deletion causes underflow in a node, borrow a key from a neighboring node or merge with a neighboring node.

Here's a simple example implementation of the deletion process in C++:

#include <iostream>
#include <vector>

using namespace std;

const int MIN_KEYS = 2; // Adjust this based on your B+ tree properties

struct Node {
    vector<int> keys;
    vector < Node*> children;

    Node() {
        // Initialize your node
    }
};

void deleteKey(Node* root, int key) {
    // Implement the deletion process here
}

int main() {
    // Sample usage
    Node* root = new Node(); // Initialize your B+ tree

    // Insert keys into the tree

    // Delete a key
    int keyToDelete = 10;
    deleteKey(root, keyToDelete);

    // Print the updated tree or perform other operations

    return 0;
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Deletion from a B+ Tree-DevsEnv