A B-tree is an extended version of m-way. There are some drawbacks with the m way tree is, in the worst case, it may behave like a linked list because it has no rule over the number of keys in node. To resolve this B-tree is introduced which is balanced. Here balanced means all leaf nodes should be at the same level which is not in the m-way tree and also each node can have some minimum and a maximum number of keys.
Here, Key in node = Order of B tree – 1
B-tree of Order m has the following
Property
- All leaf node must be at the same level,
- All nodes except root must have at least m/2 – 1 key and a maximum of m-1 one key.
- Each node of B-Tree has a maximum of m children and a minimum of m/2 children.
- All the key values in a node must be in ascending order.
- B Tree grows bottom to top.
Properties of B-trees
- Balanced: Every path from the root (the top of the tree) to the leaves (the bottom) is the same length. This keeps the tree balanced, like a seesaw that’s perfectly level.
- Multiple Keys in a Node: Unlike other trees, where each spot can hold only one key, B-tree nodes can hold many keys, making them more efficient.
- Sorted Order: Keys in B-trees are always sorted, making it easy to search for information.
- Variable Node Sizes: The nodes can adjust, becoming bigger or smaller as needed, which helps keep the tree balanced.
B-Tree was developed in the year 1972 by Bayer and McCreight. At first its name was Height Balanced m-way Search Tree but later it was changed as B-Tree.
Because of the balance property of B-Tree it allows searches, insertions, and deletions in logarithmic time.
And More benefits of its over self-balancing binary search trees(AVL Tree), It can store multiple keys at each node.
B-Tree is mostly used to optimized systems that read and write because every node contains more keys so that we can transfer large blocks of data at on reading or write operation. And Also searching in log n times. It is mostly used in database and file systems to perform read and write operations.
Time Complexity of B-Tree
S. No. | ALGORITHM | TIME COMPLEXITY |
1 | Search | O(log n) |
2 | Insert | O(log n) |
3 | Delete | O(log n) |
ānā is the total number of elements in the B-tree.
Insertion Operation in B-trees
Adding new information to a B-tree is like adding a new book to our magical bookshelf.
Here’s how it works:
- Find the Right Spot: First, we find where the new book (or piece of information) should go, keeping everything in sorted order.
- Add If There’s Space: If there’s room on the shelf (node), we just put the book there.
- Split if Needed: If the shelf is full, we split it into two. We take the middle book and move it up a level (or create a new level if necessary). This split keeps the tree balanced and makes sure there’s room for everything.
- Repeat as Necessary: If moving a book up causes the shelf it moves to become too full, we split that shelf too, and so on, until everything is neatly organized again.
Example of Insertion in B Tree
We have an B Tree of order 3 means a node can have maximum 2 keys and 3 children.
And we have to insert value 1,2,3,4,5,6,7,8 in B tree.
So Lets see how to perform insertion in B tree.
First we will insert 1 in B tree.

Now we will insert 2 in the B tree.

Now we have to insert 3 but as per B tree property, a node can have maximum m-1 keys where m is order of tree.
In our case a node can have maximum 2 keys. So we have to spilt the node to insert 3 in B tree.
We can insert 4 without any problem.

Now again we have 5 to insert but right child node is filled with 2 elements. So here we will again split it.

Now we can insert 6 without any problem.

Here again we have 7 to insert but right most child node is filled with 2 elements. So here we will again split it.

Now we can insert 8 without any problem.

Similar Reads
-
Multiplications of Two variable polynomial
Polynomial multiplication is a common operation in algebra, used in areas such as scientific computing, engineering simulations, and symbolic algebra… -
Subtraction of Two-Variable Polynomial in C
Polynomials with two variables are common in engineering, graphics, and scientific computation. While addition is frequently discussed, subtraction is equally… -
Explain the Addition of Two variable polynomial
Polynomials are fundamental in mathematics, and their use extends into computer science, engineering, physics, and more. While single-variable polynomials are… -
Reverses the Doubly Circular Linked List
Algorithm to Reverse a Doubly Circular Linked List Check if the List is Empty or Has Only One Node: If… -
Algorithm and Program in C to traverse Doubly Circular Linked List
A doubly circular linked list is a special type of linked list in which every node is connected to both… -
Polynomial representation Using Array
Polynomials are fundamental mathematical expressions used extensively in various fields. Representing them efficiently in programming is crucial for calculations and… -
Multiplication of Single Variable Polynomial : Algorithm and Program
Multiplication of single-variable polynomials is a fundamental operation in polynomial algebra. The process involves multiplying each term of one polynomial… -
Subtraction of Single variable Polynomial : Algorithm and Program
Subtracting single-variable polynomials involves reducing each corresponding term of the polynomials from each other. This process is similar to addition,… -
Addition of Single variable Polynomial : Program and Algorithm
The addition of single-variable polynomials is a fundamental concept in algebra, often encountered in mathematics and computer science. Let's break… -
Polynomial Representation Using Linked List
Polynomial representation using linked lists is a critical concept in computer science and mathematics. In this guide, we explore how…