Explain insertion procedure into a b-tree, Data Structure & Algorithms

Assignment Help:

Ans:

Insertion into the B-tree:

1.  First search is made for the place where the new record must be positioned. As soon as the keys are inserted, they are sorted into the appropriate order.

2.  If the node can contain the new record, insert the new record at the suitable pointer so that number of pointers happens to be one more than the number of records.

3.  If the node overflows because of an upper bound on the size of the node, splitting is needed. The node is divided into three parts; the middle record is passed up and inserted into parent, leaving two children at the back. If n is odd (n-1 keys in full node and the new target key), the median key int(n/2)+1 is placed into the parent node, the lower n/2 keys are placed in the left leaf and the higher n/2 keys are placed in the right leaf. If n is even, we may have left biased or right biased means one key can be more in left child or right child respectively.

4.  Splitting may propagate up the tree because the parent, into which the divided record is added, it may overflow then it may be split.  If the root is required to be divided, a new record is created with only two children.

 

 


Related Discussions:- Explain insertion procedure into a b-tree

The number of different directed trees with 3 nodes, The number of differen...

The number of different directed trees with 3 nodes are ?? The number of disimilar directed trees with three nodes are 3

Sorting algorithm is best if the list is already sorted, Which sorting algo...

Which sorting algorithm is best if the list is already sorted? Why? Insertion sort as there is no movement of data if the list is already sorted and complexity is of the order

Define the term - array, Define the term - Array A fixed length, ord...

Define the term - Array A fixed length, ordered collection of values of same type stored in contiguous memory locations; collection may be ordered in several dimensions.

Perform breadth -first search, You are given two jugs, a 4-gallon one and a...

You are given two jugs, a 4-gallon one and a 3-gallon one. Neither has any measuring marker on it. There is a tap that can be used to fill the jugs with water. How can you get exac

Explain the term group support system, (a) Explain the term Group Support S...

(a) Explain the term Group Support System and elaborate on how it can improve groupwork. (b) Briefly explain three advantages of simulation. (c) Explain with the help of a

Define about the inheritance hierarchy, Define about the inheritance hierar...

Define about the inheritance hierarchy Languages Eiffel and D provide constructs in language for invariants and pre- and post conditions which are compiled into the code and ar

Addressing modes, Compare zero-address, one-address, two-address, and three...

Compare zero-address, one-address, two-address, and three-address machines by writing programs to compute: Y = (A – B X C) / (D + E X F) for each of the four machines. The inst

Explain class p problems, Explain class P problems Class  P  is  a  cla...

Explain class P problems Class  P  is  a  class  of  decision  problems  that  can  be  solved  in  polynomial time  by(deterministic) algorithms. This class of problems is kno

Algorithm for determining who won rock paper scissors game, Suppose you are...

Suppose you are given the results of 5 games of rock-paper-scissors. The results are given to you on separate pieces of paper; each piece says either 'A' if the first person won, o

Write down the procedure to reverse a singly linked list. , Ans: A pr...

Ans: A procedure to reverse the singly linked list: reverse(struct node **st) { struct node *p, *q, *r; p = *st; q = NULL; while(p != NULL) { r =q;

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd