B-TREE | ANALYSIS DESIGN OF ALGORITHM (ADA)

📌Hi Friends ! In this post I am going to explain about B-TREE.What is B-Tree ? How we create B-Tree?A complete procedure about B-Tree by taking an example.

Let we understand What is B-Tree:

B-Tree  is a multi way search tree of order 'm' which satisfy the following conditions.

1. All leafs are at same level.

2. All intermediate nodes except the roots can have at most 'm' non-empty children and can have as few as integer value of m/2.

3. Each node of B-tree has one less key than its number of children and key are inserted in a search tree fission.

4. The root of B-Tree can have at most 'm' non-empty children and can have as few as two , if root is alone.

Let we understand B-Tree by taking an example:

Example:

Create a B-Tree for following series 

a , g , f , b , k , d , h , m , l , r , n , t , u , p , e

where order is 4.

INSERT a ➜

INSERT g ➜

INSERT f ➜ f lies between a & g , put f in between a & g.

INSERT b ➜

INSERT k ➜ here we have order 4 B-tree so here if we insert k than order exceed the limit of order 4. so we break series into two part in such a way that left pointer point to smaller element to key element and right pointer point to the bigger element to key element. here f is a key element.

INSERT d ➜ d is come before f so it will come left side of f.

INSERT h ➜ h is come after f so it will come right side of f and also after g.

INSERT m ➜ m is come after k which right side of tree.

INSERT l ➜ Note here order=4 that means every node have at most 4 elements. So in this case the right side of f having 4 elements and now we want to insert fifth element i.e l so we break it into two parts and the middle element goes to upward i.e k and add to the parent list.

INSERT r ➜ It comes left side of k

INSERT n ➜ It comes left side of k.

INSERT t ➜ Note here order=4 that means every node have at most 4 elements. So in this case the right side of k having 4 elements and now we want to insert fifth element i.e t so we break it into two parts and the middle element goes to upward i.e n and add to the parent list.

INSERT u ➜ It comes left of n.

INSERT p ➜ It comes left of n.

INSERT e ➜ It comes after d

📌Friends ! This is all about B-Tree, I hope you all understand how to create a B-Tree.The above example explain how we insert elements in a B-Tree.We will meet in next post till continue reading...