Introduction:

The number of values that a particular node of a binary tree or an AVL tree can hold is 1.

The height of a tree needs to be reduced to increase the efficiency of operations.

Also, when the data is stored in secondary medium, the time required to access is high.

To address these issues, B-Trees were introduced.

Rudolf Bayer is the creator of B-Tree.

Explanation:

A B-tree operates closely with secondary storage and can be tuned to reduce the impleiments imposed by this storage.

A B-tree of order m is a multiway search tree with the following properties:

The root has at least two subtrees unless it is a leaf.

Each nonroot and each nonleaf node holds k – 1 keys and k pointers to subtrees where [m/2] ≤ k ≤ m.

Each leaf node holds k – 1 keys where [m/2] ≤ k ≤ m.

All leaves are on the same level.

The idea behind B-Trees is that inner nodes can have variable number of child nodes within some predefined range.

Hence, B Trees do not need rebalancing as frequently as other self balancing binary search trees.

Like other balanced Binary Search Trees, time complexity to search, insert and delete is O(log(n)).

All keys are unique and appear only once in the tree.

Example:

Figure 1: B-Tree

In the above mentioned diagram, since the root has 3 keys, it has 3+1 children nodes. Within a node, the keys are sorted in ascending order.

B Tree - A search tree of order P is a tree such that each node contains almost P - 1 search values and P points in the order < P1, K1, P2, K2 .... Pq + +kq-1 , pq > where q < = p

• Each P1 is pointer to a child node and each K is a search value from some ordered set of values.

• B Tree is a balanced search tree.

• A B Tree allows search key value to appear only one.

However, since search key that appear in no next nodes appear, now where else in the B tree, we are forced to include as additional pointer field for each search key in a non lead node.

These additional pointer to either file record or bucket for the associated search key.

Typical nodes of B tree are :