B-Trees

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.

Example

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.

Rate this post

• Chef Melinda says: