1.
Introduction
2.
Searching an element
3.
Inserting an element
4.
Deleting an element
5.
Applications
6.
FAQs
7.
Key Takeaways
Last Updated: Mar 27, 2024

# Introduction to B-Tree

## Introduction

The tree is one of the most commonly used data structures in computer science. As a result, numerous alternative variants have been created. We'll get a deeper understanding of the so-called B-trees in this blog. To accomplish so, we must first comprehend its various components and structure. Following that, we'll look at their various operations, such as searching, insertion, and deletion. Finally, we'll go over the advantages and disadvantages of using B-trees for data storage.

A B-tree of order m, according to Knuth's definition, is a tree that satisfies the following properties:

• A maximum of m children can be found in each node.
• Except for root, every non-leaf node has at least m/2 child nodes.
• There are at least two children if the root is not a leaf node.
• There are k-1 keys in a non-leaf node with k children.
• All of the leaves are on the same level and are devoid of any information.

The keys of each internal node serve as separation values, dividing its subtrees. For example, if an internal node has three subtrees, it must have two keys: a1 and a2. All values in the leftmost subtree will be less than a1, all values in the middle subtree will be between a1 and a2, and all values in the rightmost subtree will be greater than a2. Internal nodes

source: cpp.edu

Must Recommended Topic, Generalization in DBMS and Recursive Relationship in DBMS.

## Searching an element

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

1. Starting with the root node, compare k to the node's first key. Return the node and the index if k is the node's first key.
3. If k is the root node's initial key, recursively search the left child of this key.
4. Compare k to the node's next key if the current node contains more than one key and k is greater than the first key. If k is the following key, look for the key's left child (i.e., k lies between the first and the second keys). Otherwise, look for the key's right child.
5. Repeat steps 1â€“4 until you reach the leaf.

Example:

source: iq.opengenus.org

## Inserting an element

At the leaf node level, insertions are made. The following algorithm must be followed to place an item into B Tree.

1. Navigate the B Tree until you find the suitable leaf node to insert the node.
2. If there are fewer than m-1 keys in the leaf node, insert the element in ascending order.
3. Else, it should proceed to the next step if the leaf node contains m-1 keys.
1. In the rising sequence of elements, add the new element.
2. In the middle, divide the node into two nodes.
3. The median element should be pushed up to its parent node.
4. If the parent node has the same m-1 number of keys as the child node, split it.

Example:

source: staff.ustc.edu.cn

Recommended Topic - Specialization and Generalization in DBMS and  Checkpoint in DBMS.

## Deleting an element

At the leaf nodes, deletion is also conducted. It can be a leaf node or an inside node that must be destroyed. To delete a node from a B tree, use the following algorithm.

1. Find the position of the leaf node.
2. If the leaf node has more than m/2 keys, delete the required key from the node.
3. If the leaf node lacks m/2 keys, fill in the gaps with the eighth or left sibling element.
1. If the left sibling has more than m/2 elements, shift the intervening element down to the node where the key is deleted and push the largest element up to its parent.
2. If the right sibling has more than m/2 items, shift the intervening element down to the node where the key is deleted and push the smallest element up to the parent.
4. Create a new leaf node by merging two leaf nodes and the parent node's intervening element if neither sibling has more than m/2 elements.
5. If the parent has less than m/2 nodes, repeat the operation on the parent as well.

If the node to be destroyed is an internal node, its in-order successor or predecessor should be used instead. Because the successor or predecessor will always be on the leaf node, the operation will be similar to deleting the node from the leaf node.

Example:

source: staff.ustc.edu.cn

## Applications

• Because accessing values held in a vast database saved on a disc is a very time-consuming activity, the B tree is used to index the data and enable fast access to the actual data stored on the discs.
• In the worst situation, searching an unindexed and unsorted database with n key values takes O(n) time. In the worst-case scenario, if we use B Tree to index this database, it will be searched in O(log n) time.
• A B-tree, in particular:
• keeps keys sorted for sequential traversal and uses a hierarchical index to reduce disc reads
• insertions and deletions are sped up by using partially filled blocks.
• a recursive algorithm that keeps the index balanced

Recommended Topic, Schema in DBMS

## FAQs

1. What is B-tree?
A B-tree, is a tree data structure, that allows for logarithmic amortized searches, insertions, and removals while keeping data sorted.
2. Where is B-tree mainly used?
It's most typically found in database and file management systems.
3. What is the time-complexity of standard operations in B-tree?
The time-complexity of standard operations in B-tree is as follows:

## Key Takeaways

We learned that a B-tree is a tree data structure that keeps data sorted and permits logarithmic operations. We learned algorithms of standard operations for B-tree like searching, inserting, and deletion with examples, and then we learned applications of B-tree as well.
Check out this problem - Largest BST In Binary Tree

Also, try Coding Ninjas Studio to practice programming problems for your complete interview preparation.

Live masterclass