BTree is a specialized mway tree that can be widely used for disk access. A BTree of order m can have at most m  1 keys and m children. One of the main reason of using BTree 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 BTree
History of B Tree
BTree 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 BTree.
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.
BTree 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 BTree 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 BTree 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
