B-Tree is a specialized m-way tree that can be widely used for disk access. A B-Tree of order m can have at most m-1 keys and m children. One of the main reason of using B-Tree is its capability to store large number of keys in a single node and large key values by keeping the height of the tree relatively small.
Properties of B-Tree –
- A B-Tree is defined by the term minimum degree ‘t’
- Every node except root must contain at least (t – 1) keys. Root may contain minimum 1 key.
- All nodes (including root) may contain at most (2t – 1) keys.
- Number of children of a node is equal to the number of keys in it plus 1.
- All keys of a node are sorted in increasing order. The child between two keys k1 and k2 contains all keys in the range from k1 and k2.
B-Tree Insertion
Let us understand the algorithm with an example tree of minimum degree ‘t’ as 3 and a sequence of integers 10, 20, 30, 40, 50, 60, 70, 80 and 90 in an initially empty B-Tree.
Initially root is NULL. Let us first insert 10.
Let us now insert 20, 30, 40 and 50. They all will be inserted in root because maximum number of keys a node can accommodate is 2*t – 1 which is 5.
Let us now insert 60. Since root node is full, it will first split into two, then 60 will be inserted into the appropriate child.
Let us now insert 70 and 80. These new keys will be inserted into the appropriate leaf without any split.
Let us now insert 90. This insertion will cause a split. The middle key will go up to the parent.
Initial Tree
After delete 60 the Tree will be
After delete 20 the Tree will be
After delete 30 the Tree will be
