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

What is the dissimilarity between dynamic strain aging, Q. What is the diss...

Q. What is the dissimilarity between dynamic strain aging and strain aging? Answer:- Strain aging could be explains as "normal wear and tear" or the fatigue that is experi

Subtract the numbers using 1's complements, Subtraction 11001-10110 using 1...

Subtraction 11001-10110 using 1's complement Ans. 11001 - 10110 01001 is 1' s Compliment of 10110, so     1 1 0 0 1 +  0 1 0 0 1 ------------------    1 0 0 0 1 0    Add 1

Program size for different instruction set approaches, Q. Program size for ...

Q. Program size for different Instruction Set Approaches? Assumptions: Complex Instruction is: Add C, A, B having 16 bit addresses and 8 bit data operands All opera

Define hit ratio, Define Hit ratio. The performance of cache memory is ...

Define Hit ratio. The performance of cache memory is frequently measured in terms of quantity called hit ratio. Hit-Find a word in cache. Miss-Word is not found in cache.

Dfd, Give a 5-minute presentation on your team''s solution

Give a 5-minute presentation on your team''s solution

Explain the working principle of hard disk, Question : a) Hard disk is ...

Question : a) Hard disk is an important component of a computer. What type of memory is it? b) With the help of a diagram describe its features. c) Explain its working pr

In 8085 which is called as high order / low order register, Flag is known a...

Flag is known as Low order register & Accumulator is known as High order Register.

Compare hypertext versus hypermedia, Compare hypertext versus hypermedia.  ...

Compare hypertext versus hypermedia.  Hypertext is basically similar as regular text - it can be stored, read, searched, or edited - with a significant except ion: hyper text h

Expert systems, An expert systems is software that contains a knowledge ...

An expert systems is software that contains a knowledge base of facts and relationships and has the ability to make inferences based on that knowledge base. An experts sys

8259 PIC, plz expalain interfacing of 8259 with 8085 step wise

plz expalain interfacing of 8259 with 8085 step wise

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