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

Program, insertion and deletion in a tree

insertion and deletion in a tree

What do you understand by structured programming, What do you understand by...

What do you understand by structured programming Structured Programming  This term is used for programming design that emphasizes:- (1) Hierarchical design of programmi

Explain the interfaces in ruby, Explain the Interfaces in Ruby Recall...

Explain the Interfaces in Ruby Recall that in object-oriented programming, an interface is a collection of abstract operations that cannot be instantiated. Even though Ruby i

Algorithms, write short note on algorithms

write short note on algorithms

Define the term ''complexity of an algorithm, Define the term 'complexity o...

Define the term 'complexity of an algorithm; Complexity of an algorithm is the calculate of analysis of algorithm. Analyzing an algorithm means predicting the resources that th

State cmy model, CMY Model  The cyan, magenta, yellow (CMY) colour mode...

CMY Model  The cyan, magenta, yellow (CMY) colour model is a subtractive model based on the colour absorption properties of paints and inks. As such it has become the standard

Binary search trees, In this unit, we discussed Binary Search Trees, AVL tr...

In this unit, we discussed Binary Search Trees, AVL trees and B-trees. The outstanding feature of Binary Search Trees is that all of the elements of the left subtree of the root

Algorithm, Write an algorithm for compound interest.

Write an algorithm for compound interest.

Stacks, Q. Explain w hat are the stacks? How can we use the stacks  to chec...

Q. Explain w hat are the stacks? How can we use the stacks  to check whether an expression is correctly parentheses or not. For example (()) is well formed but (() or )()( is not w

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