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

Tree traversal, Q. What do you understand by the tree traversal? Write down...

Q. What do you understand by the tree traversal? Write down the procedure for traversing a binary tree in preorder and execute it on the following tree.    Ans: Th

Use a random number generator to create 10 numbers, Use a random number gen...

Use a random number generator to create 10 numbers between 1 and 1000 and store them in 2 different arrays.  The first array should contain the numbers as they are generated.  The

Process of channel access, Channel access In first generation systems, ...

Channel access In first generation systems, every cell supports a number of channels. At any given time a channel is allocated to only one user. Second generation systems also

Define binary tree, Define Binary Tree  A binary tree T is explained as...

Define Binary Tree  A binary tree T is explained as a finite set of nodes that is either empty or having of root and two disjoint binary trees TL, and TR known as, respectively

An algorithm to insert a node in beginning of linked list, Q. Write down an...

Q. Write down an algorithm to insert a node in the beginning of the linked list.                         Ans: /* structure containing a link part and link part

Hasing and indexing, differentiate between indexing and hashing in file org...

differentiate between indexing and hashing in file organization

Implementation of a binary tree, Like general tree, binary trees are implem...

Like general tree, binary trees are implemented through linked lists. A typical node in a Binary tree has a structure as follows struct NODE { struct NODE *leftchild; i

Insert function, INSERT FUNCTION /*prototypes of insert & find function...

INSERT FUNCTION /*prototypes of insert & find functions */ list * insert_list(list *); list * find(list *, int); /*definition of  anyinsert function */ list * inser

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