B Tree of order m
A balanced multiway search tree of order m in which each nonroot node contains at least m/2 keys is called a B-Tree of order m. where order means maximum number of sub-trees
A B-Tree of order m is either the empty tree or it is an m-way search tree T with the following properties:
(i) The root of T has at least two subtrees and at most m subtrees.
(ii) All internal nodes of T (other than its root) have between [m / 2] and m subtrees.
(iii)All external nodes of T are at the same level.
Algorithm to search for a key in B-tree is as follows:
B-tree search makes an n-way choice. By performing the linear search in a node, correct child Ci of that node is chosen. Once the value is greater than or equal to the desired value is obtained, the child pointer to the immediate left of the value is followed. Otherwise rightmost child pointer is followed. If desired value is obtained, the search is terminated.
B-tree search (x, k) This function searches the key from the given B-tree
The Disk_Read operation indicates that all references to a given node be preceded by a read operation.
Algorithm to insert a key in B-tree is as follows:
1. First search is done for the place where the new record must be put. As the keys are inserted, they are sorted into the proper order.
2. If the node can accommodate the new record, insert the new record at the appropriate pointer so that number of pointers remains one more than the number of records.
3. If the node overflows because there is an upper bound on the size of a node, splitting is required. The node is split into three parts; the middle record is passed upward and inserted into parent, leaving two children behind. If n is odd (n-1 keys in full node and the new target key), median key int(n/2)+1 is placed in parent node, the lower n/2 keys are put in the left leaf and the higher n/2 keys are put in the right leaf. If n is even, we may have left biased or right biased means one key may be more in left child or right child respectively.
4. Splitting may propagate up the tree because the parent, into which splitted record is added, may overflow then it may be split. If the root is required to be split, a new record is created with just two children.
