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

Time complexity, The  total  of  time  needed  by  an algorithm to run to i...

The  total  of  time  needed  by  an algorithm to run to its completion is termed as time complexity. The asymptotic running time of an algorithm is given in terms of functions. Th

Implementation of tree, The most common way to insert nodes to a general tr...

The most common way to insert nodes to a general tree is to first discover the desired parent of the node you desire to insert, and then insert the node to the parent's child list.

Non-recursive algorithm, Q .  Write down the non-recursive algorithm to tra...

Q .  Write down the non-recursive algorithm to traverse a tree in preorder. Ans: T he Non- Recursive algorithm for preorder traversal is written below: Initially i

Graph terminologies, Graph terminologies : Adjacent vertices: Two vert...

Graph terminologies : Adjacent vertices: Two vertices a & b are said to be adjacent if there is an edge connecting a & b. For instance, in given Figure, vertices 5 & 4 are adj

Splaying algorithm, Insertion & deletion of target key requires splaying of...

Insertion & deletion of target key requires splaying of the tree. In case of insertion, the tree is splayed to find the target. If, target key is found out, then we have a duplicat

Binary trees, A binary tree is a special tree where each non-leaf node can ...

A binary tree is a special tree where each non-leaf node can have atmost two child nodes. Most important types of trees which are used to model yes/no, on/off, higher/lower, i.e.,

Interest, I=PR/12 numbers of years : Interest Rate up to 1 years : 5...

I=PR/12 numbers of years : Interest Rate up to 1 years : 5.50 Up to 5 years : 6.50 More than 5 year : 6.75 please design an algorithm based on the above information

Determine yiq colour model, Determine YIQ Colour Model Whereas an RGB m...

Determine YIQ Colour Model Whereas an RGB monitor requires separate signals for the red, green, and blue components of an image, a television monitor uses a single composite si

Enumerate about the carrier set members, Enumerate about the carrier set me...

Enumerate about the carrier set members Ruby is written in C, so carrier set members (which is, individual symbols) are implemented as fixed-size arrays of characters (which is

Implement the physat algorithm, The first assignment in this course require...

The first assignment in this course required you to acquire data to enable you to implement the PHYSAT algorithm (Alvain et al. 2005, Alvain et al. 2008) in this second assignment

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