Insertion of a key into a b-tree, Data Structure & Algorithms

Assignment Help:

Example: Insertion of a key 33 into a B-Tree (w/split)

Step 1: Search first node for key closet to 33. Key 30 was determined.

632_Insertion of a key into a B-Tree.png

Step 2: Node pointed through key 30, is searched for inserting 33. Node is split and 36 is shifted upwards.

932_Insertion of a key into a B-Tree1.png

Step 3: Key 33 is inserted among 32 and 35.

1604_Insertion of a key into a B-Tree2.png

                                      Figure: A B-tree

Deletion of key from B-tree is not impossible, but care have to be taken to make sure that the properties of b-tree are maintained if the deletion decrease the number of keys into a node below the minimum degree of tree, this violation has to be connected by combining various nodes and possibly decreasing the height if the tree. If the key contain children, the children have to be rearranged.

Example (Searching of a B - Tree for key 21)

Step 1: Search for key 21 in first node. 21 are among 20 & 30.

1068_Insertion of a key into a B-Tree3.png

Step2: Searching is conducted onto the nodes linked by 30.

1784_Insertion of a key into a B-Tree4.png

                                Figure: A B-tree


Related Discussions:- Insertion of a key into a b-tree

Quick sort, This is the most extensively used internal sorting algorithm. I...

This is the most extensively used internal sorting algorithm. In its fundamental form, it was invented by C.A.R. Hoare in the year of 1960. Its popularity lies in the easiness of i

Complexity of an algorithm, compare two functions n and 2n for various valu...

compare two functions n and 2n for various values of n. determine when second becomes larger than first

Applications of the queue, Write down any four applications of the queues. ...

Write down any four applications of the queues.                                                            Ans. A pp li cation of Queue is given below (i)  Queue is

Polynomials, Polynomials like  5x 4    +  2x 3    +  7x 2     +  10x  -  8...

Polynomials like  5x 4    +  2x 3    +  7x 2     +  10x  -  8  can  be  represented by using arrays. Arithmetic operations such as addition & multiplication of polynomials are com

Binary search tree in ascending order, In order to get the contents of a Bi...

In order to get the contents of a Binary search tree in ascending order, one has to traverse it in In-order

State the example of pre- and post-conditions, State the example of pre- an...

State the example of pre- and post-conditions Suppose that function f(x) should have a non-zero argument and return a positive value. We can document these pre- and post-condit

Explain the halting problem, Explain the halting problem Given a comput...

Explain the halting problem Given a computer program and an input to it, verify whether the program will halt on that input or continue working indefinitely on it.

Binary tree, A binary tree is a tree data structures in which each node hav...

A binary tree is a tree data structures in which each node have at most two child nodes, generally distinguished as "right" and "left". Nodes with children are called parent nodes,

STACK, 5. Implement a stack (write pseudo-code for STACK-EMPTY, PUSH, and P...

5. Implement a stack (write pseudo-code for STACK-EMPTY, PUSH, and POP) using a singly linked list L. The operations PUSH and POP should still take O(1) time.

Describe commonly used asymptotic notations, Q.1 Compare two functions n 2 ...

Q.1 Compare two functions n 2 and 2 n for various values of n. Determine when second becomes larger than first. Q.2 Why do we use asymptotic notation in the study of algorit

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