The B-tree is a generalization of a binary search tree in which a node can have more than two children .The B-tree is optimized for systems that read and write large blocks of data.It has following properties
- The data items are stored at leaves.
- Every node has between M/2 and M children where M is a positive integer greater than 1.
- M is the order as well as height of tree.
- The non leaf nodes store up to M-1 keys.
- The root is either a leaf or has between two and M children.
- All leaves are at the same depth and have between [L/2] and L children.
Insertion in B-Tree
The insertion in b-tree is done such that they satisfy all the properties listed above.
Consider a B-Tree of order 4 and we need to insert 5,3,21,9,1,13,2,7,10,12,4,8.Each node can have at most 4 pointers and 3 keys (M-1) or at least 2 pointers and 1 key.Since it is a binary search tree the keys of left subtree will be less than the root value and keys of right subtree will be greater than root value.
- Create a node a and insert 5.(Fig 1)
- Insert 3 to the left of 5 (3<5).
- Insert 21 to the right of 5(21 >5).
- In order to insert 9 split node a into b and c as 9 cannot be accommodated in node a(Max keys =3).The left pointer of 9 points to 3 and 5 ((3 ,5) <9)and the right pointer points to 21(21 >9),
- Insert 1 in node b (1<3)(Fig 2).
- Insert 13 in node c(13>9 and 13 <21).
- 2 cannot be directly inserted in node b
- In order to insert 2 split b into b and d.
- 3 gets stored in node a.
- Store 1 and 2 in node b.
- Store 5 in node d.
- Insert 7 in node dÂ .(7 >5 and 7<9)(Fig 3)
- Insert 10 in node c(10 >9 and 10 <13).
- Now 12 cannot be directly inserted in node c.
- Split c into c and e.
- 12 is then inserted in node Â c.
- 21 is stored in e.
- Insert 4 in node d(4 >3 and 4 <5).(Fig 4)
- 8 cannot be inserted in d directly.
- Split d into f and g
- Split f into f and h.
- 8 is inserted in h.