Operations on b-trees, Data Structure & Algorithms

Assignment Help:

Operations on B-Trees

Given are various operations which can be performed on B-Trees:

  • Search
  • Create
  • Insert

B-Tree does effort to minimize disk access and the nodes are usually stored on disk

All the nodes are supposed to be stored into secondary storage instead of primary storage. All references to a given node are preceded through a read operation. Likewise, once a node is changed and it is no longer required, it has to be written out to secondary storage with write operation.

Given is the algorithm for searching a B-tree:

B-Tree Search (x, k)

i < - 1

while i < = n [x] and k > keyi[x]

do i ← i + 1

if i < = n [x] and k = key1 [x]

then return (x, i)

if leaf [x]

then return NIL

else Disk - Read (ci[x])

return B - Tree Search (Ci[x], k)

The search operation is alike to binary tree. Instead of selecting between a left and right child as in binary tree, a B-tree search have to make an n-way choice.

The right child is selected by performing a linear search of the values into the node. After determining the value greater than or equal to desired value, the child pointer to the instantaneous left to that value is followed.

The exact running time of search operation based upon the height of the tree. Given is the algorithm for the creation of a B-tree:

B-Tree Create (T)

x ← Allocate-Node ( )

 Leaf [x] ← True

n [x] ← 0

Disk-write (x)

root [T] ← x

 

The above denoted algorithm creates an empty B-tree through allocating a new root which has no keys and is a leaf node.

Given is the algorithm for insertion into a B-tree:

B-Tree Insert (T,K)

r ← root (T)

if n[r] = 2t - 1

then S ← Allocate-Node ( )

root[T] ← S

leaf [S] ← FALSE

n[S] ← 0

C1 ← r

B-Tree-Split-Child (s, I, r)

B-Tree-Insert-Non full (s, k)

else

B - Tree-Insert-Non full (r, k)

To carry on an insertion on B-tree, the proper node for the key has to be located. Next, the key has to be inserted into the node.

If the node is not full prior to the insertion, then no special action is needed.

If node is full, then the node has to be split to make room for the new key. As splitting the node results in moving one key to the parent node, the parent node ha not be full. Else, another split operation is required.

This procedure may repeat all the way up to the root and may need splitting the root node.


Related Discussions:- Operations on b-trees

What is called the basic operation of an algorithm, What is called the basi...

What is called the basic operation of an algorithm? The most significant operation of the algorithm is the operation contributing the most to the total running time is known as

Reverse order of elements on a slack, Q. Reverse the order of the elements ...

Q. Reverse the order of the elements on a stack S    (i) by using two additional stacks (ii) by using one additional queue. Ans :      L e t S be the stac

What is bubble sort, What is bubble sort? Bubble Sort: The basic ide...

What is bubble sort? Bubble Sort: The basic idea in bubble sort is to scan the array to be sorted sequentially various times. Every pass puts the largest element in its corr

Define chaining process of hashing, Chaining In this method, instead of...

Chaining In this method, instead of hashing function value as location we use it as an index into an array of pointers. Every pointer access a chain that holds the element havi

Calculate the k-th power and recursive algorithem, 1. The following is a r...

1. The following is a recursive algorithm to calculate the k -th power of 2. Input k a natural number Output kth power of 2 Algorithem: If k =0then return 1 Else return 2* po

Four applications or implementation of the stack, Q. Write down any four ap...

Q. Write down any four applications or implementation of the stack.                                     Ans. (i)       The Conversion of infix to postfix form (ii)

Splay trees, Addition of new records in a Binary tree structure always occu...

Addition of new records in a Binary tree structure always occurs as leaf nodes, which are further away from the root node making their access slower. If this new record is to be ac

Program segment for insertion of an element into the queue, Program: Progra...

Program: Program segment for insertion of an element into the queue add(int value) { struct queue *new; new = (struct queue*)malloc(sizeof(queue)); new->value = val

Example which cause problems for hidden-surface algorithms, Example which c...

Example which cause problems for some hidden-surface algorithms Some special cases, which cause problems for some hidden-surface algorithms, are penetrating faces and cyclic ov

Random searching, write aprogram for random -search to implement if a[i]=x;...

write aprogram for random -search to implement if a[i]=x;then terminate other wise continue the search by picking new randon inex into a

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