Algorithm to insert a key in b-tree, Computer Engineering

Assignment Help:

Algorithm to insert a key in B-tree is as follows:

1.  First search is completed for the place where the new record must be put. As the keys are inserted, they are sorted into the proper order.

2.  If the node can contain the new record, insert the new record at the appropriate pointer so that number of pointers remains one more than the number of records.

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

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

 


Related Discussions:- Algorithm to insert a key in b-tree

Cohesion, Identify the type of cohesion in the following statements: 1. ...

Identify the type of cohesion in the following statements: 1. Compute average daily temperatures at various sites 2. Initialize sums and open files 3. Create new temperature rec

Find the shortest path, The following is the required interface for the mou...

The following is the required interface for the mouse and cheese problem. Your program is required to read its input from a file named 'maze.txt' In the maze.txt

Background and foreground colors can be interchanged, Background and foregr...

Background and foreground colors can be interchanged using the command?? Format Inverse command.

Sorting, Different sorting algorithm will be discussed in the lecutres. The...

Different sorting algorithm will be discussed in the lecutres. The task in this worksheet is to write a funtions based on the Quicksort algorithm. When sorting an array of objec

Unlike ipv4 & ipv6 which field in base header not include, Unlike Ipv4, Ipv...

Unlike Ipv4, Ipv6 does not include which field in the base header? Unlike Ipv4, Ipv6 does not contain the Field for Fragmentation information into the base header.

Effective branching rate - heuristic searches, Effective Branching Rate: ...

Effective Branching Rate: Assessing heuristic functions is an important part of "AI" research: a particular heuristic function may sound such a good idea, but in practice give

Over fitting considerations, Over fitting Considerations : Hence in le...

Over fitting Considerations : Hence in left unchecked there backpropagation in multi-layer networks can be highly susceptible to overfitting itself to the training examples. B

Give explanation of user datagram protocol, Explain UDP (User Datagram Prot...

Explain UDP (User Datagram Protocol). UDP utilizes a connectionless communication paradigm. It is an application of using UDP doesn't require preestablishing a connection befor

Operating system, explain the various types of computer systems

explain the various types of computer systems

Explain about cluster computing, The idea of clustering is defined as use o...

The idea of clustering is defined as use of multiple computers naturally multiple storage devices, PCs or UNIX workstations and their interconnections to make what emerges to users

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