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

Ruby implementation of the symbol abstract data type, Ruby implementation o...

Ruby implementation of the Symbol ADT Ruby implementation of the Symbol ADT, as mentioned, hinges on making Symbol class instances immutable that corresponds to the relative la

Write an algorithm for binary search, Q.1 Write procedures/ Algorithm to in...

Q.1 Write procedures/ Algorithm to insert and delete an element in to array. Q.2. Write an algorithm for binary search. What are the conditions under which sequential search of

Graph, multilist representation of graph

multilist representation of graph

Doubly linked list, How does operations like insertion, deletion occur?

How does operations like insertion, deletion occur?

Create accessors for this data structure, Create a Money data structure tha...

Create a Money data structure that is made up of amount and currency. (a) Write a constructor for this data structure (b) Create accessors for this data structure (c) Writ

Explain what is stack. describe ways to execute stack. , ST AC K is ...

ST AC K is explained as follows : A stack is one of the most usually used data structure. A stack is also called a Last-In-First-Out (LIFO) system, is a linear list in

Green computing, In the present scenario of global warming, the computer ha...

In the present scenario of global warming, the computer hard ware and software are also contributing for the increase in the temperature in the environment and contributing for the

Consistent heuristic function - graph search, Consistent Heuristic Function...

Consistent Heuristic Function - Graph Search Recall the notions of consistency and admissibility for an A* search heuristic. a. Consider a graph with four nodes S, A, B, C,

Multiple queue, What is multiple queue and explain them

What is multiple queue and explain them

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