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.