B Tree

  1. All leaves are at the same level.
  2. A B-Tree is defined by the term minimum degree ‘t’. The value of t depends upon disk block size.
  3. Every node except root must contain at least t-1 keys. The root may contain minimum 1 key.
  4. All nodes (including root) may contain at most 2*t — 1 keys.
  5. Number of children of a node is equal to the number of keys in it plus 1.
  6. All keys of a node are sorted in increasing order. The child between two keys k1 and k2 contains all keys in the range from k1 and k2.
  7. B-Tree grows and shrinks from the root which is unlike Binary Search Tree. Binary Search Trees grow downward and also shrink from downward.
  8. Like other balanced Binary Search Trees, time complexity to search, insert and delete is O(log n).
  9. Insertion of a Node in B-Tree happens only at Leaf Node.

Operations on a B-tree

Searching an element in a B-tree

Searching for an element in a B-tree is the generalized form of searching an element in a Binary Search Tree. The following steps are followed.

  1. Starting from the root node, compare k with the first key of the node.
    If k = the first key of the node, return the node and the index.
  2. If k.leaf = true, return NULL (i.e. not found).
  3. If k < the first key of the root node, search the left child of this key recursively.
  4. If there is more than one key in the current node and k > the first key, compare k with the next key in the node.
    If k < next key, search the left child of this key (ie. k lies in between the first and the second keys).
    Else, search the right child of the key.
  5. Repeat steps 1 to 4 until the leaf is reached.

Searching Example

1. Let us search key k = 17 in the tree below of degree 3.

Algorithm for Searching an Element

BtreeSearch(x, k)
i = 1
while i ≤ n[x] and k ≥ keyi[x]
do i = i + 1
if i n[x] and k = keyi[x]
then return (x, i)
if leaf [x]
then return NIL
else
return BtreeSearch(ci[x], k)

B-tree operations code in Python and C/C++

Python

# Searching a key on a B-tree in Python# Create a node
class BTreeNode:
def __init__(self, leaf=False):
self.leaf = leaf
self.keys = []
self.child = []
# Tree
class BTree:
def __init__(self, t):
self.root = BTreeNode(True)
self.t = t
# Insert node
def insert(self, k):
root = self.root
if len(root.keys) == (2 * self.t) - 1:
temp = BTreeNode()
self.root = temp
temp.child.insert(0, root)
self.split_child(temp, 0)
self.insert_non_full(temp, k)
else:
self.insert_non_full(root, k)
# Insert nonfull
def insert_non_full(self, x, k):
i = len(x.keys) - 1
if x.leaf:
x.keys.append((None, None))
while i >= 0 and k[0] < x.keys[i][0]:
x.keys[i + 1] = x.keys[i]
i -= 1
x.keys[i + 1] = k
else:
while i >= 0 and k[0] < x.keys[i][0]:
i -= 1
i += 1
if len(x.child[i].keys) == (2 * self.t) - 1:
self.split_child(x, i)
if k[0] > x.keys[i][0]:
i += 1
self.insert_non_full(x.child[i], k)
# Split the child
def split_child(self, x, i):
t = self.t
y = x.child[i]
z = BTreeNode(y.leaf)
x.child.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.child = y.child[t: 2 * t]
y.child = y.child[0: t - 1]
# Print the tree
def print_tree(self, x, l=0):
print("Level ", l, " ", len(x.keys), end=":")
for i in x.keys:
print(i, end=" ")
print()
l += 1
if len(x.child) > 0:
for i in x.child:
self.print_tree(i, l)
# Search key in the tree
def search_key(self, k, x=None):
if x is not None:
i = 0
while i < len(x.keys) and k > x.keys[i][0]:
i += 1
if i < len(x.keys) and k == x.keys[i][0]:
return (x, i)
elif x.leaf:
return None
else:
return self.search_key(k, x.child[i])

else:
return self.search_key(k, self.root)
def main():
B = BTree(3)
for i in range(10):
B.insert((i, 2 * i))
B.print_tree(B.root)if B.search_key(8) is not None:
print("\nFound")
else:
print("\nNot Found")
if __name__ == '__main__':
main()
// Searching a key on a B-tree in C#include <stdio.h>
#include <stdlib.h>
#define MAX 3
#define MIN 2
struct BTreeNode {
int val[MAX + 1], count;
struct BTreeNode *link[MAX + 1];
};
struct BTreeNode *root;// Create a node
struct BTreeNode *createNode(int val, struct BTreeNode *child) {
struct BTreeNode *newNode;
newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
newNode->val[1] = val;
newNode->count = 1;
newNode->link[0] = root;
newNode->link[1] = child;
return newNode;
}
// Insert node
void insertNode(int val, int pos, struct BTreeNode *node,
struct BTreeNode *child) {
int j = node->count;
while (j > pos) {
node->val[j + 1] = node->val[j];
node->link[j + 1] = node->link[j];
j--;
}
node->val[j + 1] = val;
node->link[j + 1] = child;
node->count++;
}
// Split node
void splitNode(int val, int *pval, int pos, struct BTreeNode *node,
struct BTreeNode *child, struct BTreeNode **newNode) {
int median, j;
if (pos > MIN)
median = MIN + 1;
else
median = MIN;
*newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
j = median + 1;
while (j <= MAX) {
(*newNode)->val[j - median] = node->val[j];
(*newNode)->link[j - median] = node->link[j];
j++;
}
node->count = median;
(*newNode)->count = MAX - median;
if (pos <= MIN) {
insertNode(val, pos, node, child);
} else {
insertNode(val, pos - median, *newNode, child);
}
*pval = node->val[node->count];
(*newNode)->link[0] = node->link[node->count];
node->count--;
}
// Set the value
int setValue(int val, int *pval,
struct BTreeNode *node, struct BTreeNode **child) {
int pos;
if (!node) {
*pval = val;
*child = NULL;
return 1;
}
if (val < node->val[1]) {
pos = 0;
} else {
for (pos = node->count;
(val < node->val[pos] && pos > 1); pos--)
;
if (val == node->val[pos]) {
printf("Duplicates are not permitted\n");
return 0;
}
}
if (setValue(val, pval, node->link[pos], child)) {
if (node->count < MAX) {
insertNode(*pval, pos, node, *child);
} else {
splitNode(*pval, pval, pos, node, *child, child);
return 1;
}
}
return 0;
}
// Insert the value
void insert(int val) {
int flag, i;
struct BTreeNode *child;
flag = setValue(val, &i, root, &child);
if (flag)
root = createNode(i, child);
}
// Search node
void search(int val, int *pos, struct BTreeNode *myNode) {
if (!myNode) {
return;
}
if (val < myNode->val[1]) {
*pos = 0;
} else {
for (*pos = myNode->count;
(val < myNode->val[*pos] && *pos > 1); (*pos)--)
;
if (val == myNode->val[*pos]) {
printf("%d is found", val);
return;
}
}
search(val, pos, myNode->link[*pos]);
return;
}
// Traverse then nodes
void traversal(struct BTreeNode *myNode) {
int i;
if (myNode) {
for (i = 0; i < myNode->count; i++) {
traversal(myNode->link[i]);
printf("%d ", myNode->val[i + 1]);
}
traversal(myNode->link[i]);
}
}
int main() {
int val, ch;
insert(8);
insert(9);
insert(10);
insert(11);
insert(15);
insert(16);
insert(17);
insert(18);
insert(20);
insert(23);
traversal(root);printf("\n");
search(11, &ch, root);
}
// Searching a key on a B-tree in C++#include <iostream>
using namespace std;
class TreeNode {
int *keys;
int t;
TreeNode **C;
int n;
bool leaf;
public:
TreeNode(int temp, bool bool_leaf);
void insertNonFull(int k);
void splitChild(int i, TreeNode *y);
void traverse();
TreeNode *search(int k);friend class BTree;
};
class BTree {
TreeNode *root;
int t;
public:
BTree(int temp) {
root = NULL;
t = temp;
}
void traverse() {
if (root != NULL)
root->traverse();
}
TreeNode *search(int k) {
return (root == NULL) ? NULL : root->search(k);
}
void insert(int k);
};
TreeNode::TreeNode(int t1, bool leaf1) {
t = t1;
leaf = leaf1;
keys = new int[2 * t - 1];
C = new TreeNode *[2 * t];
n = 0;
}
void TreeNode::traverse() {
int i;
for (i = 0; i < n; i++) {
if (leaf == false)
C[i]->traverse();
cout << " " << keys[i];
}
if (leaf == false)
C[i]->traverse();
}
TreeNode *TreeNode::search(int k) {
int i = 0;
while (i < n && k > keys[i])
i++;
if (keys[i] == k)
return this;
if (leaf == true)
return NULL;
return C[i]->search(k);
}
void BTree::insert(int k) {
if (root == NULL) {
root = new TreeNode(t, true);
root->keys[0] = k;
root->n = 1;
} else {
if (root->n == 2 * t - 1) {
TreeNode *s = new TreeNode(t, false);
s->C[0] = root;s->splitChild(0, root);int i = 0;
if (s->keys[0] < k)
i++;
s->C[i]->insertNonFull(k);
root = s;
} else
root->insertNonFull(k);
}
}
void TreeNode::insertNonFull(int k) {
int i = n - 1;
if (leaf == true) {
while (i >= 0 && keys[i] > k) {
keys[i + 1] = keys[i];
i--;
}
keys[i + 1] = k;
n = n + 1;
} else {
while (i >= 0 && keys[i] > k)
i--;
if (C[i + 1]->n == 2 * t - 1) {
splitChild(i + 1, C[i + 1]);
if (keys[i + 1] < k)
i++;
}
C[i + 1]->insertNonFull(k);
}
}
void TreeNode::splitChild(int i, TreeNode *y) {
TreeNode *z = new TreeNode(y->t, y->leaf);
z->n = t - 1;
for (int j = 0; j < t - 1; j++)
z->keys[j] = y->keys[j + t];
if (y->leaf == false) {
for (int j = 0; j < t; j++)
z->C[j] = y->C[j + t];
}
y->n = t - 1;
for (int j = n; j >= i + 1; j--)
C[j + 1] = C[j];
C[i + 1] = z;for (int j = n - 1; j >= i; j--)
keys[j + 1] = keys[j];
keys[i] = y->keys[t - 1];
n = n + 1;
}
int main() {
BTree t(3);
t.insert(8);
t.insert(9);
t.insert(10);
t.insert(11);
t.insert(15);
t.insert(16);
t.insert(17);
t.insert(18);
t.insert(20);
t.insert(23);
cout << "The B-tree is: ";
t.traverse();
int k = 10;
(t.search(k) != NULL) ? cout << endl
<< k << " is found"
: cout << endl
<< k << " is not Found";
k = 2;
(t.search(k) != NULL) ? cout << endl
<< k << " is found"
: cout << endl
<< k << " is not Found\n";
}

Searching Complexity on B Tree

  • Worst case Time complexity: Θ(log n)
  • Average case Time complexity: Θ(log n)
  • Best case Time complexity: Θ(log n)
  • Average case Space complexity: Θ(n)
  • Worst case Space complexity: Θ(n)

B Tree Applications

  • databases and file systems
  • to store blocks of data (secondary storage media)
  • multilevel indexing

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Atharv Sharma

Atharv Sharma

9 Followers

PENETRATION TESTING ENTHUSIAST ETHICAL HACKER BTECH (CSE) STUDENT