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

Aussie wine tours awt, Business Narrative Aussie Wine Tours (AWT) condu...

Business Narrative Aussie Wine Tours (AWT) conduct tours of the wineries of Victoria's Yarra Valley wine region. The tours take place on the last Sunday of each month. Currentl

Define point-to-point communication, Q. Define Point-to-point Communication...

Q. Define Point-to-point Communication? The simplest form of message is a point to point communication. A message is sent from the transmitting processor to a receiving process

Logic-based expert systems - , Logic-based Expert Systems - Artificial inte...

Logic-based Expert Systems - Artificial intelligence: Expert systems are agents which are programmed to make decisions about real world situations. They are put together by uti

The concept of thread-parallel computing, The Concept of Thread Thread ...

The Concept of Thread Thread is a chronological flow of control within a process. A process can include one or more threads. Threads have their own register values and program

What is recursion, What is recursion?  A recursive procedure should have tw...

What is recursion?  A recursive procedure should have two properties.  What are they? Recursion means function call itself repeatedly.         Properties : (1) There

What is the purpose of reserved word using in c#, A keyword that states the...

A keyword that states the types in a particular namespace can be referred to without requiring their full qualified type names. 'using' reserved word always come with namespace

How many input ANDand OR gates are required, How many two input AND gates a...

How many two input AND gates and two input OR gates are required to realize Y = BD+CE+AB ? Ans. Here three product terms, therefore three AND gates of two inputs are needed.

Describe about the embedded applications assembly, Describe about the Embed...

Describe about the Embedded applications assembly Embedded applications assembly and C programs are developed since embedded programs aren't large. For all others high-level an

Explain the process of skolemization., Problem 1. Explain briefly the p...

Problem 1. Explain briefly the process of matching production rules against working memory 2. What are the different kinds of knowledge that need to be represented in AI? Ex

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