B-TREE

If you have any queries please leave a message here
Your Message
×


B-Tree is a specialized m-way tree that can be widely used for disk access. A B-Tree of order m can have at most m - 1 keys and m children. One of the main reason of using B-Tree is its capability to store large number of keys in a single node and large key values by keeping the height of the tree relatively small.


Why use B-Tree


History of B Tree




B-Tree Insertion

Let us understand the algorithm with an example tree of minimum order m as 6 and a sequence of integers 10, 20, 30, 40, 50, 60, 70, 80 and 90 in an initially empty B-Tree.

Initially root is NULL. Let us first insert 10.



Let us now insert 20, 30, 40 and 50. They all will be inserted in root because maximum number of keys a node can accommodate is m – 1 which is 5.



Let us now insert 60. Since root node is full, it will first split into two, then 60 will be inserted into the appropriate child.



Let us now insert 70 and 80. These new keys will be inserted into the appropriate leaf without any split.



Let us now insert 90. This insertion will cause a split. The middle key will go up to the parent.







B-Tree Deletion

Initial Tree



After delete 60 the Tree will be



After delete 20 the Tree will be



After delete 30 the Tree will be





Question 1 : Show the stages in growth of 4 order B-Tree when the following keys are inserted in the given order : 74, 72, 19, 87, 51, 10, 35, 18, 39, 60, 76, 58, 29, 45

Answer : -

Step 1 - First we insert 74, 72 and 19. They all will be inserted in root because maximum number of keys a node can accommodate is 4 – 1 which is 3.



Step 1 - Ascending order rule is violated. In order to fix this we need to sorted the keys.



Step 2 - Now insert 87. Since root node is full, it will first split into two, then 87 will be inserted into the appropriate child.





Step 3 - Insert 51 and 10 in the appropriate leaf without any split.



Step 4 - Again ascending order rule is violated. In order to fix this we need to sorted the keys.



Step 5 - Next insert 35. Its require to split the child. The middle key will go up to the parent.





Step 6 - Ascending order rule is violated. Need to sorted the keys.



Step 7 - Next insert 18 and 39 in the appropriate position without any split.



Step 8 - Ascending order rule is violated again. So need to sorted the keys.



Step 9 - Next insert 60. Its require to again split the child. The middle key will go up to the parent.





Step 10 - Insert 76 in the appropriate leaf without any split and sort the keys.





Step 11 - Insert 58 in the appropriate position without any split and sort the keys.





Step 12 - Insert 29 in the appropriate position without any split and sort the keys.





Step 13 - Next insert 45. Its require to split the child again.





Step 14 - Ascending order rule is violated again. So need to sorted the keys.





Question 2 : Constract a B-Tree of order 5 from the following key values : A, G, F, B, K, D, H, M, J, E, S, I, R, X, C, L, N, T, U, P.
Also delete H, R, P, D.

Answer : -

Step 1 - First we insert A, G, F and B. They all will be inserted in root because maximum number of keys a node can accommodate is 5 – 1 which is 4.



Step 1 - Ascending order rule is violated. In order to fix this we need to sorted the keys.



Step 2 - Insert K. Since root node is full, it will first split into two, then K will be inserted into the appropriate child.

Note - In case of even number of keys, the middle node will be selected by left bias or right bias. [In this example I take right bias]





Step 3 - Insert D and H in the appropriate position without any split and sort the keys.





Step 4 - Insert M in the appropriate position without any split.



Step 5 - Insert J. Its require to split the child again.





Step 6 - Insert E, S and I in the appropriate position without any split and sort the keys.





Step 7 - Insert R in the appropriate position without any split and sort the keys.





Step 8 - Insert X in the appropriate position without any split.



Step 9 - Insert C. Its require to split the child.





Step 10 - Insert L. Its require to split the child.





Step 11 - Sorted the keys.



Step 12 - Insert N in the appropriate position without any split and sort the keys.





Step 13 - Insert T in the appropriate position without any split and sort the keys.





Step 14 - Insert U in the appropriate position without any split and sort the keys.





Step 15 - Insert P. Its require to split the child.





Step 16 - Sorted the keys.





Delete Operation

Step 1 - Delete H



Step 2 - Delete R



Step 3 - Delete P



Step 4 - Delete D




ABOUT US

QuestionSolves.com is an educational website that helps worldwide students in solving computer education related queries.

Also, different software like Visual Studio, SQL Server, Oracle etc. are available to download in different versions.

Moreover, QuestionSolves.com provides solutions to your questions and assignments also.


MORE TOPIC


Windows Command

UNIX Command

IGNOU Assignment Solution

IGNOU Question Paper Solution


WHAT WE DO


Website Devlopment

Training

Home Learning

Provide BCA, MCA Projects

Provide Assignment & Question Paper Solution


CONTACT US


Follow Us