B-Tree

Complexity in Big O Notation:

1. B-tree is tree data structure that allows insertion,deletion and sequential access in logarithmic time 
2. It is similar to the red black tree but the height is smaller than the red black tree because its  branching factor can be much larger.
3. It generalizes binary search tree in a natural manner, its just that a node has more than two children.
4. It can be used to implement many dynamic set operation in time O(logn)
5. B-tree is optimized for systems that use read and write operations on huge blocks of data.
6. Applications:  

• Databases
• File systems.

   7. In  a typical B-tree application, the amount of data handled is so large that all the data do not fits into the main memory at once. The B-tree algorithms copy the selected pages from the disk into the main memory as needed and write back onto the disk pages that have changed at any time, thus the size of the main memory does not limits the size of the B-tree that can be handled.

  8. The B-tree grows logarithmically with the number of nodes it contains.

Properties of B Tree:


     1.Every node x has the following fields:

• n[x] , the number of keys currently stored in node x.
• the n[x] keys themselves, stored in non-decreasing order. key1[x]<=key2[x]<=...<=keyn[x][x]
• leaf[x], a boolean value that is TRUE if x is a leaf and FALSE if x is an internal node.

1. If x is an internal node, it also contains n[x]+1 pointers c1[x],c2[x],...,cn[x]+1[x] to its children.Leaf nodes have no children, so their ci fields are undefined.
2. The keys keyi[x] separate the ranges of keys stored in each subtree: if ki is any key stored in the subtree with root ci[x],then : k1<=key1[x]<=k2<=key2[x]<=...<=keyn[x][x]<=kn[x]+1
3. Every leaf has the same depth, which is the tree's height h.
4. There are lower and upper bounds on the number of keys a node can contain.The bounds can be expressed in terms of fixed integer t>=2 called the minimum degree of the B tree

• Every node other than the root must have at least t-1 keys.Every internal node other than the root thus has at least t children. If the is nonempty , the root must have at least one key.
• Every node can contain atmost 2t-1 keys. Therefore, an internal node can have at most 2t children.We say that a node is full if it contains exactly 2t-1 keys.
• The simplest B tree occurs when t=2.Every Initial node then has either 2,3 or 4 children and we have a 2-3-4 tree.In practice, however, much larger values of t are typically used.

B-Tree Delete operation:

assume that we have a procedure of B-Tree-Delete to delete key k from the subtree rooted at x.This procedure should guarantee that whenever B-Tree-Delete is called recursively on a node x the number of keys in x is atleast the minimum degree t.

Various cases of Deletion:

1. If key k is a node x and x is leaf node, then delete key k from x.
2. If node k is in node x and x is an internal node do the following

(a)If the children y that precedes k in node x has t keys then find the predecessor k' of k in the subtree rooted at y .Recursively delete k' and replace k by k' in x.

(b)If the child z that follows k in the node x has atleast t keys then find the successor k' of k in the subtree rooted at z, recursively delete k' and by k' in x.

(c)otherwise,if y and z have only t-1 keys merge k and all of z into y , so that x uses both k and pointer z and y now contains 2t-1 keys, then free z and recursively delete k from y.

    3.If key k is not present in internal node x, determine the root ci[x] of the appropiate subtree that must contain k,if k is the tree at all.

(a)If ci[x] has only t-1 keys but has a sibling with t keys, give ci[x] an extra key by moving a key from x down into ci[x], moving a key from ci[x]'s immediately left or right sibling up into x, and moving the appropriate child from the sibling into ci[x].

(b)  If ci[x] and all of ci[x]'s sibling have t-1 keys, merge ci with one sibling which involves moving a key from x down into the new merged node to become the median key for that node.

B-Tree Insert operation:

When inserting an item, first do a search for it in the B-tree. If the item is not already in the B-tree, this unsuccessful search will end at a leaf. If there is room in this leaf, just insert the new item here. Note that this may require that some existing keys be moved one to the right to make room for the new item. If instead this leaf node is full so that there is no room to add the new item, then the node must be "split" with about half of the keys going into a new node to the right of this one. The median (middle) key is moved up into the parent node. (Of course, if that node has no room, then it may have to be split as well.) Note that when adding to an internal node, not only might we have to move some keys one position to the right, but the associated pointers have to be moved right as well. If the root node is ever split, the median key moves up into a new root node, thus causing the tree to increase in height by one.