Facebook

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),
Fig 1 : Insertion in B-Tree

 

  • 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.

 

Fig 2 : Insert 1,13,2

 

  • 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.

 

Fig 3 : Insert 7,10,12

 

  • 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.
Fig 4 : Insert 4,8

 

Rate this post

Comments

This post currently has one response

Leave a Reply

Your email address will not be published. Required fields are marked *

Sidebar