## Algorithm

A B-tree, short for "balanced tree," is a self-balancing tree data structure that maintains sorted data and allows for efficient search, insertion, deletion, and sequential access. B-trees are commonly used in databases and file systems where large amounts of data need to be stored and accessed quickly.

Here are some key characteristics and features of B-trees:

1. Balanced Structure: B-trees are balanced, meaning that all leaf nodes of the tree are at the same level. This balance is maintained during insertions and deletions, ensuring that the height of the tree remains relatively small, leading to efficient operations.

2. Node Structure: Each node in a B-tree contains a certain number of keys and pointers to child nodes. The number of keys in a node is within a specified range, and it is designed to optimize disk I/O by accommodating a large number of keys in each node.

3. Sorted Order: The keys within each node are stored in sorted order, allowing for efficient search operations using a binary search. This sorting property extends to all the nodes of the tree.

4. Search Operation: Searching in a B-tree is similar to searching in a binary search tree. Starting from the root, comparisons are made to determine the path to follow down the tree until the desired key is found or a leaf node is reached.

5. Insertion and Deletion: Inserting or deleting a key in a B-tree involves maintaining the balance of the tree. The tree is modified to ensure that it remains balanced, and nodes are split or merged as needed.

6. Use Cases: B-trees are commonly used in scenarios where large amounts of data need to be stored and efficiently accessed, such as in databases and file systems. They are well-suited for applications that involve frequent insertions and deletions.

7. Variants: There are variations of B-trees, including B+ trees and B* trees, each with specific characteristics. B+ trees, for example, store keys only in the leaf nodes, which simplifies range queries.

## Code Examples

### #1 B-tree implement in Python

```Code - Python Programming```

``````class BTreeNode:
def __init__(self, leaf=True):
self.leaf = leaf
self.keys = []
self.children = []

class BTree:
def __init__(self, t):
self.root = BTreeNode()
self.t = t  # Minimum degree

def insert(self, key):
root = self.root
if len(root.keys) == (2 * self.t) - 1:
new_root = BTreeNode(leaf=False)
new_root.children.append(self.root)
self.split(new_root, 0)
self.root = new_root
self.insert_non_full(self.root, key)

def insert_non_full(self, x, key):
i = len(x.keys) - 1
if x.leaf:
x.keys.append(None)
while i >= 0 and key < x.keys[i]:
x.keys[i + 1] = x.keys[i]
i -= 1
x.keys[i + 1] = key
else:
while i >= 0 and key < x.keys[i]:
i -= 1
i += 1
if len(x.children[i].keys) == (2 * self.t) - 1:
self.split(x, i)
if key > x.keys[i]:
i += 1
self.insert_non_full(x.children[i], key)

def split(self, x, i):
t = self.t
y = x.children[i]
z = BTreeNode(leaf=y.leaf)
x.children.insert(i + 1, z)
x.keys.insert(i, y.keys[t - 1])
z.keys = y.keys[t:(2 * t) - 1]
y.keys = y.keys[0:t - 1]
if not y.leaf:
z.children = y.children[t:2 * t]
y.children = y.children[0:t - 1]

def print_tree(self, x, l=0):
print("Level ", l, ":", len(x.keys), end=" ")
for key in x.keys:
print(key, end=" ")
print()
l += 1
if len(x.children) > 0:
for child in x.children:
self.print_tree(child, l)

# Example usage:
if __name__ == "__main__":
b_tree = BTree(t=3)
keys = [3, 7, 1, 8, 2, 6, 4, 10, 9, 5]

for key in keys:
b_tree.insert(key)

print("B-tree after insertion:")
b_tree.print_tree(b_tree.root)
``````
Copy The Code &

### #2 B-tree implement in Java

```Code - Java Programming```

``````class BTreeNode {
int[] keys;
int t; // Minimum degree
BTreeNode[] children;
int n; // Current number of keys
boolean leaf;

public BTreeNode(int t, boolean leaf) {
this.t = t;
this.leaf = leaf;
this.keys = new int[2 * t - 1];
this.children = new BTreeNode[2 * t];
this.n = 0;
}
}

public class BTree {
private BTreeNode root;
private int t; // Minimum degree

public BTree(int t) {
this.root = null;
this.t = t;
}

public void insert(int key) {
if (root == null) {
root = new BTreeNode(t, true);
root.keys[0] = key;
root.n = 1;
} else {
if (root.n == 2 * t - 1) {
BTreeNode newRoot = new BTreeNode(t, false);
newRoot.children[0] = root;
splitChild(newRoot, 0);
root = newRoot;
}
insertNonFull(root, key);
}
}

private void insertNonFull(BTreeNode x, int key) {
int i = x.n - 1;
if (x.leaf) {
while (i >= 0 && key  <  x.keys[i]) {
x.keys[i + 1] = x.keys[i];
i--;
}
x.keys[i + 1] = key;
x.n++;
} else {
while (i >= 0 && key  <  x.keys[i]) {
i--;
}
i++;
if (x.children[i].n == 2 * t - 1) {
splitChild(x, i);
if (key > x.keys[i]) {
i++;
}
}
insertNonFull(x.children[i], key);
}
}

private void splitChild(BTreeNode x, int i) {
BTreeNode y = x.children[i];
BTreeNode z = new BTreeNode(t, y.leaf);
x.children[x.n + 1] = null;
x.n++;
for (int j = t - 1; j  <  2 * t - 2; j++) {
z.keys[j - t + 1] = y.keys[j];
}
y.n = t - 1;
z.n = t - 1;
for (int j = t - 2; j >= 0; j--) {
y.keys[j] = 0;
}
for (int j = x.n - 1; j > i; j--) {
x.keys[j] = x.keys[j - 1];
x.children[j + 1] = x.children[j];
}
x.keys[i] = y.keys[t - 1];
x.children[i + 1] = z;
y.keys[t - 1] = 0;
}

public boolean search(int key) {
return search(root, key);
}

private boolean search(BTreeNode x, int key) {
int i = 0;
while (i  <  x.n && key > x.keys[i]) {
i++;
}
if (i < x.n && key == x.keys[i]) {
return true;
} else if (x.leaf) {
return false;
} else {
return search(x.children[i], key);
}
}

public static void main(String[] args) {
BTree bTree = new BTree(3);

// Insert keys
int[] keys = {3, 7, 1, 5, 11, 8, 14, 2, 6, 9, 13, 15};
for (int key : keys) {
bTree.insert(key);
}

// Search for keys
System.out.println(bTree.search(6)); // true
System.out.println(bTree.search(10)); // false
}
}
``````
Copy The Code &

### #3 B-tree implement in C

```Code - C Programming```

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

// B-tree node structure
typedef struct BTreeNode {
int *keys;    // Array of keys
struct BTreeNode **children;  // Array of child pointers
int n;        // Current number of keys
int leaf;     // 1 if the node is a leaf, 0 otherwise
} BTreeNode;

// Function to create a new B-tree node
BTreeNode *createNode(int leaf) {
BTreeNode *newNode = (BTreeNode *)malloc(sizeof(BTreeNode));
newNode->keys = (int *)malloc(sizeof(int) * 2);  // Assuming a B-tree of order 2
newNode->children = (BTreeNode **)malloc(sizeof(BTreeNode *) * 3);  // Assuming a B-tree of order 2
newNode->n = 0;
newNode->leaf = leaf;
return newNode;
}

// Function to split a full child of a node
void splitChild(BTreeNode *parent, int index, BTreeNode *child) {
BTreeNode *newChild = createNode(child->leaf);
newChild->n = 1;

// Move the middle key to the parent node
parent->keys[index] = child->keys[1];

// Move the second half of the keys to the new child
newChild->keys[0] = child->keys[2];
newChild->children[0] = child->children[2];
newChild->children[1] = child->children[3];

child->n = 1;

// Update the parent's children array
for (int i = parent->n; i > index + 1; i--) {
parent->children[i] = parent->children[i - 1];
}

// Insert the new child in the parent's children array
parent->children[index + 1] = newChild;
parent->n++;
}

// Function to insert a key into the B-tree
void insert(BTreeNode *root, int key) {
if (root->n == 2) {
BTreeNode *newRoot = createNode(0);
newRoot->children[0] = root;
splitChild(newRoot, 0, root);
root = newRoot;
}

insertNonFull(root, key);
}

// Function to insert a key into a non-full node
void insertNonFull(BTreeNode *node, int key) {
int i = node->n - 1;

if (node->leaf) {
while (i >= 0 && key  <  node->keys[i]) {
node->keys[i + 1] = node->keys[i];
i--;
}

node->keys[i + 1] = key;
node->n++;
} else {
while (i >= 0 && key  <  node->keys[i]) {
i--;
}

i++;

if (node->children[i]->n == 2) {
splitChild(node, i, node->children[i]);
if (key > node->keys[i]) {
i++;
}
}

insertNonFull(node->children[i], key);
}
}

// Function to search for a key in the B-tree
BTreeNode *search(BTreeNode *root, int key) {
int i = 0;

while (i  <  root->n && key > root->keys[i]) {
i++;
}

if (i < root->n && key == root->keys[i]) {
return root;
} else if (root->leaf) {
return NULL;
} else {
return search(root->children[i], key);
}
}

// Function to print the B-tree in-order
void inOrderTraversal(BTreeNode *root) {
if (root != NULL) {
for (int i = 0; i  <  root->n; i++) {
inOrderTraversal(root->children[i]);
printf("%d ", root->keys[i]);
}
inOrderTraversal(root->children[root->n]);
}
}

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

int main() {
BTreeNode *root = createNode(1);  // Creating a B-tree with a leaf node

int keys[] = {3, 8, 2, 7, 6, 1, 5, 4};
int numKeys = sizeof(keys) / sizeof(keys[0]);

for (int i = 0; i  <  numKeys; i++) {
insert(root, keys[i]);
}

printf("In-order traversal of the B-tree: ");
inOrderTraversal(root);
printf("\n");

int searchKey = 5;
BTreeNode *result = search(root, searchKey);
if (result != NULL) {
printf("Key %d found in the B-tree.\n", searchKey);
} else {
}

// Free the allocated memory for the B-tree
freeBTree(root);

return 0;
}
``````
Copy The Code &

### #4 B-tree implement in C++

```Code - C++ Programming```

``````#include <iostream>
#include <vector>

const int T = 2; // Degree of the B-tree

// Node structure for the B-tree
template  < typename KeyType, typename ValueType>
struct BTreeNode {
bool isLeaf;
std::vector<KeyType> keys;
std::vector < ValueType> values;
std::vector<BTreeNode*> children;

BTreeNode(bool leaf = true) : isLeaf(leaf) {}

~BTreeNode() {
for (auto child : children) {
delete child;
}
}
};

// B-tree class
template  < typename KeyType, typename ValueType>
class BTree {
private:
BTreeNode* root;

public:
BTree() : root(nullptr) {}

~BTree() {
delete root;
}

// Function to search for a key in the B-tree
ValueType search(const KeyType& key) {
return searchKey(root, key);
}

// Function to insert a key-value pair into the B-tree
void insert(const KeyType& key, const ValueType& value) {
if (root == nullptr) {
root = new BTreeNode < KeyType, ValueType>(true);
root->keys.push_back(key);
root->values.push_back(value);
} else {
if (root->keys.size() == 2 * T - 1) {
BTreeNode < KeyType, ValueType>* newRoot = new BTreeNode(false);
newRoot->children.push_back(root);
splitChild(newRoot, 0);
root = newRoot;
}
insertNonFull(root, key, value);
}
}

private:
// Function to search for a key in a B-tree node
ValueType searchKey(BTreeNode < KeyType, ValueType>* node, const KeyType& key) {
if (node != nullptr) {
size_t i = 0;
while (i < node->keys.size() && key > node->keys[i]) {
i++;
}
if (i  <  node->keys.size() && key == node->keys[i]) {
return node->values[i];
} else if (node->isLeaf) {
} else {
return searchKey(node->children[i], key);
}
}
}

// Function to insert a key-value pair into a non-full B-tree node
void insertNonFull(BTreeNode < KeyType, ValueType>* node, const KeyType& key, const ValueType& value) {
int i = node->keys.size() - 1;
if (node->isLeaf) {
node->keys.push_back(KeyType());
node->values.push_back(ValueType());
while (i >= 0 && key  <  node->keys[i]) {
node->keys[i + 1] = node->keys[i];
node->values[i + 1] = node->values[i];
i--;
}
node->keys[i + 1] = key;
node->values[i + 1] = value;
} else {
while (i >= 0 && key  <  node->keys[i]) {
i--;
}
i++;
if (node->children[i]->keys.size() == 2 * T - 1) {
splitChild(node, i);
if (key > node->keys[i]) {
i++;
}
}
insertNonFull(node->children[i], key, value);
}
}

// Function to split a full child of a B-tree node
void splitChild(BTreeNode < KeyType, ValueType>* parent, int index) {
BTreeNode* child = parent->children[index];
BTreeNode* newChild = new BTreeNode(child->isLeaf);

parent->keys.insert(parent->keys.begin() + index, child->keys[T - 1]);
parent->values.insert(parent->values.begin() + index, child->values[T - 1]);

newChild->keys.assign(child->keys.begin() + T, child->keys.end());
newChild->values.assign(child->values.begin() + T, child->values.end());
child->keys.resize(T - 1);
child->values.resize(T - 1);

if (!child->isLeaf) {
newChild->children.assign(child->children.begin() + T, child->children.end());
child->children.resize(T);
}

parent->children.insert(parent->children.begin() + index + 1, newChild);
}
};

int main() {
BTree < int, std::string> btree;

// Inserting key-value pairs into the B-tree
btree.insert(3, "Apple");
btree.insert(7, "Banana");
btree.insert(12, "Cherry");
btree.insert(5, "Date");
btree.insert(20, "Fig");
btree.insert(15, "Grapes");

// Searching for keys in the B-tree
std::cout << "Value for key 7: " << btree.search(7) << std::endl;
std::cout << "Value for key 15: " << btree.search(15) << std::endl;
std::cout << "Value for key 10: " << btree.search(10) << std::endl;

return 0;
}
``````
Copy The Code &